Сколько раз вы слышали эту мантру "монады не композируются"? Я потратил достаточно много времени, чтобы попробовать опровергнуть это утверждение, пытаясь решить проблему в лоб. Но как и многие вещи в математике, порой, чтобы попробовать что-то понять, иногда стоит сменить масштаб.
Рекомендуется прочитать первую и вторую части этой серии, если вы еще этого не сделали.
Когда мы хотим слить два эффекта в один, то есть сцепить их в трансформер, у нас есть два варианта: вложить левый в правый, либо правый в левый. Эти два варианты определены со схемами 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.
Выходит, что монады все-таки могут собираться в определенные трансформеры, исходя из свойств известных эффектов.
Исходники с определениями можно найти здесь. Примеры применения описанной системы эффектов можно посмотреть тут.