Пытаясь композировать некомпозируемое: монады

Сколько раз вы слышали эту мантру «монады не композируются»? Я потратил достаточно много времени, чтобы попробовать опровергнуть это утверждение, пытаясь решить проблему в лоб. Но как и многие вещи в математике, порой, чтобы попробовать что-то понять, иногда стоит сменить масштаб.

Рекомендуется прочитать первую и вторую части этой серии, если вы еще этого не сделали.

Когда мы хотим слить два эффекта в один, то есть сцепить их в трансформер, у нас есть два варианта: вложить левый в правый, либо правый в левый. Эти два варианты определены со схемами TU и UT:

newtype TU t u a = TU (t :. u := a) newtype UT t u a = UT (u :. t := a)

Как нам уже известно из предыдущих частей этого цикла, для вычислений с неизменяемым окружением (Reader) достаточно прямой композиции функторов, а для эффектов обработки ошибок (Maybe и Either) подходит схема с обратной композицией UT.

type instance Schema (Reader e) = TU ((->) e) type instance Schema (Either e) = UT (Either e) type instance Schema Maybe = UT Maybe

Экземпляры обычного ковариантного и аппликативного функтора выглядят тривиально, так как это все еще функтор, а функторы композируются:

(<$$>) :: (Functor t, Functor u) => (a -> b) -> t :. u := a -> t :. u := b (<$$>) = (<$>) . (<$>)  (<**>) :: (Applicative t, Applicative u) => t :. u := (a -> b) -> t :. u := a -> t :. u := b f <**> x = (<*>) <$> f <*> x  instance (Functor t, Functor u) => Functor (TU t u) where     fmap f (TU x) = TU $ f <$$> x  instance (Applicative t, Applicative u) => Applicative (TU t u) where     pure = TU . pure . pure     TU f <*> TU x = TU $ f <**> x  instance (Functor t, Functor u) => Functor (UT t u) where     fmap f (UT x) = UT $ f <$$> x  instance (Applicative t, Applicative u) => Applicative (UT t u) where     pure = UT . pure . pure     UT f <*> UT x = UT $ f <**> x

Проблемы возникают, если мы попробуем описать монады. Непонятно, как найти обобщенный способ, учитывая, что оба эффекта нам неизвестны:

instance (Monad t, Monad u) => Monad (TU t u) where   x >>= f = ???  instance (Monad t, Monad u) => Monad (UT t u) where   x >>= f = ???

Возможно, пока что нам это не по плечу. Давайте попробуем определить отдельные экземпляры для отдельных комбинаций с одним определенным эффектом:

instance Monad u => Monad (TU ((->) e) u) where     TU x >>= f = TU $ \e -> x e >>= ($ e) . run . f  instance Monad u => Monad (UT (Either e) u) where     UT x >>= f = UT $ x >>= \case         Left e -> pure $ Left e         Right r -> run $ f r  instance Monad u => Monad (UT Maybe u) where     UT x >>= f = UT $ x >>= \case         Nothing -> pure Nothing         Just r -> run $ f r

В случае обработки ошибок (Maybe и Either), мы можем увидеть похожее поведение: если инвариант содержит параметр a, тогда цепочка вычислений продолжается. Это невероятно похоже на Traversable! Вот так он выглядит:

class (Functor t, Foldable t) => Traversable t where     traverse :: Applicative f => (a -> f b) -> t a -> f (t b)  instance Traversable Maybe where     traverse _ Nothing = pure Nothing     traverse f (Just x) = Just <$> f x  instance Traversable (Either a) where     traverse _ (Left x) = pure (Left x)     traverse f (Right y) = Right <$> f y

Давайте попробуем его использовать:

instance (Traversable t, Monad t, Monad u) => Monad (UT t u) where     UT x >>= f = UT $ x >>= \i -> join <$> traverse (run . f) i

Работает! То есть, мы можем применять связывание для трансформера с известным нам Traversable эффектом.

А что нам делать с TU, для которого подходит эффект неизменяемого окружения — Reader? Я правда не знаю. Но мы можем кое-что попробовать — возьмём класс антипод Traversable — Distributive. И какое счастье, для него может быть определен Reader (точнее, его внутренняя часть — (->) e)!

class Functor g => Distributive g where     collect :: Functor f => (a -> g b) -> f a -> g (f b)  instance Distributive ((->) e) where     collect f q e = flip f e <$> q

Но почему именно эти два класса функторов и почему они антиподы по отношению друг к другу? Понять это помогут модификации их методов, где вместо функций a -> t b мы подставляем функцию, которая ничего не меняет — id:

sequence :: (Traversable t, Applicative u) => t (u a) -> u (t a) sequence = traverse id  distribute :: (Distributive t, Functor u) => u (t a) -> t (u a) distribute = collect id

Вот оно! Мы можем увидеть, что эти методы позволяют нам менять порядок эффектов. Раз уж сработал Traversable для обратной композиции, может Distributive подойдет для прямой?

instance (Monad t, Distributive t, Monad u) => Monad (TU t u) where     TU x >>= f = TU $ x >>= \i -> join <$> collect (run . f) i

Тоже работает! Значит у нас уже есть определенный алгоритм, как определять монады для таких трансформеров:

• Обратная схема UT — полагайся на Traversable.

• Прямая схема TU — полагайся на Distributive.

Но у нас есть также схема посложнее, которая используется в монаде State и комонаде Store:

newtype TUT t t' u a = TUT (t :. u :. t' := a)  newtype State s a = State ((->) s :. (,) s := a) newtype Store s a = Store ((,) s :. (->) s := a)  type instance Schema (State s) = TUT ((->) s) ((,) s) type instance Schema (Store s) = TUT ((,) s) ((->) s)

Выглядит так, что не подступиться. Композиция обычных ковариантный функторов все еще работает, а вот для аппликативных уже нет — мы не можем просто отобразить функцию в композиции стрелки и запятой, потому что они связаны. То есть, содержимое кортежа зависит от аргумента стрелки, и нужно выполнить применение функции, чтобы получить обновленное значение.

instance (Functor t, Functor t', Functor u) => Functor (TUT t t' u) where     fmap f (TUT x) = TUT $ f <$$$> x

Так, стрелка ( (->) s) является Distributive, а запятая ((,) s) — Traversable… Но между этими двумя эффектами также существует связь посильнее, которая называется сопряжением (подробнее можно почитать здесь):

class Functor t => Adjunction t u where     leftAdjunct  :: (t a -> b) -> a -> u b     rightAdjunct :: (a -> u b) -> t a -> b     unit :: a -> u :. t := a     unit = leftAdjunct id     counit :: t :. u := a -> a     counit = rightAdjunct id  instance Adjunction ((,) s) ((->) s) where     leftAdjunct :: ((s, a) -> b) -> a -> (s -> b)      leftAdjunct f a s = f (s, a)     rightAdjunct :: (a -> s -> b) -> (s, a) -> b     rightAdjunct f (s, a) = f a s     unit :: a -> s -> (s, a)     unit x = \s -> (s, x)     counit :: (s, (s -> a)) -> a     counit (s, f) = f s

Попробуем сначала разобраться с эффектом состояния. Погружение в эффект State полностью идентичен методу unit, а сопряжение справа используется, чтобы связать два эффекта в монадной цепочке:

instance Monad (State s) where     State x >>= f = State $ rightAdjunct (run . f) <$> x     -- Или так: State x >>= f = State $ counit <$> ((run . f) <$$> x)     return = State . unit

А как быть в случае с трансформером? Тут у нас меж двух функторов ((->) s) и ((,) s) есть произвольный эффект, который надо учитывать. Для погружения в трансформер нам понадобится сопряжение слева, а для связывания — сопряжение справа:

instance (Adjunction t' t, Monad u) => Monad (TUT t t' u) where     x >>= f = TUT $ (>>= rightAdjunct (run . f)) <$> run x     return = TUT . (leftAdjunct pure)

Поразительно, но для того чтобы описать экземпляр комонады для этой же схемы, нам нужно сделать все в точности наоборот:

instance (Adjunction t' t, Comonad u) => Comonad (TUT t' t := u) where     extend f x = TUT $ (=>> leftAdjunct (f . TUT)) <$> run x     extract = rightAdjunct extract . run

А что, если нам нужно не только погружать значение в трансформер, но еще и поднимать произвольный эффект до уровня трансформера? И тут нам понадобятся сопряжения! Причем, для монадных и комонадных трансформеров результаты невероятно симметричны…

instance (Adjunction t' t, Distributive t) => MonadTrans (TUT t t') where     lift = TUT . collect (leftAdjunct id)  instance (Adjunction t' t, Applicative t, forall u . Traversable u) => ComonadTrans (TUT t' t) where     lower = rightAdjunct (traverse id) . run

Из этого всего, мы можем сделать выводы:

• Если эффект имеет экземпляр Traversable — подходит обратная схема UT.

• Если эффект имеет экземпляр Distributive — подходит прямая схема TU.

• Если компоненты эффекта образуют сопряжение (Adjunction) — подходит схема TUT.

Выходит, что монады все-таки могут собираться в определенные трансформеры, исходя из свойств известных эффектов.

Исходники с определениями можно найти здесь. Примеры применения описанной системы эффектов можно посмотреть тут.