Traversable

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

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

Когда мы хотим слить два эффекта в один, то есть сцепить их в трансформер, у нас есть два варианта: вложить левый в правый, либо правый в левый. Эти два варианты определены со схемами 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 := bf <**> x = (<*>) <$> f <*> xinstance (Functor t, Functor u) => Functor (TU t u) where    fmap f (TU x) = TU $ f <$$> xinstance (Applicative t, Applicative u) => Applicative (TU t u) where    pure = TU . pure . pure    TU f <*> TU x = TU $ f <**> xinstance (Functor t, Functor u) => Functor (UT t u) where    fmap f (UT x) = UT $ f <$$> xinstance (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 . finstance Monad u => Monad (UT (Either e) u) where    UT x >>= f = UT $ x >>= \case        Left e -> pure $ Left e        Right r -> run $ f rinstance 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 xinstance 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 iddistribute :: (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 idinstance 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.

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

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