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

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

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

Когда мы хотим слить два эффекта в один, то есть сцепить их в трансформер, у нас есть два варианта: вложить левый в правый, либо правый в левый. Эти два варианты определены со схемами 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.

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

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