Происходят ли вообще монадные трансформаторы из присоединений?

Ответ 1

Три конструкции в этом ответе также доступны в воспроизводимой форме в этом Гисте.

Саймон С строительство...

newtype Three u f m a = Three { getThree :: u (m (f a)) }

... полагается на то, что f и u являются присоединенными эндофункторами Hask. Хотя это работает в случае StateT, есть две взаимосвязанные проблемы, с которыми мы должны иметь дело, если мы хотим сделать его более общим:

• Во-первых, нам нужно найти подходящие дополнения для "функциональных монад", на которых будут построены трансформаторы; а также

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

Есть довольно много интересных дополнений, с которыми мы могли бы поэкспериментировать. В частности, для каждой монады доступны два дополнения: присоединение Клейсли и присоединение Эйленберга-Мура (для их точного категориального представления см. Эмили Риль, " Теория категорий в контексте", раздел 5.2). В категоричном отрывке, который занимает примерно половину этого ответа, я остановлюсь на присоединении Клейсли, просто потому, что в псевдо-Хаскеле удобнее шататься.

(Под псевдо-Хаскеллом я подразумеваю, что в последующем будет широко распространено злоупотребление нотацией. Чтобы упростить глаза, я буду использовать некоторые специальные соглашения: |-> означает отображение между вещами, которые не обязательно являются типами; аналогичным образом, : то значит, что напоминает сигнатуру типа; ~> означает не-HASK морфизм, фигурные и угловые скобки выделить объекты в отдельных категориях, не HASK; . также означает композицию функтора, а F -| U означает F и U являются сопряженными функторы.)

Клейсли примыкание

Если g является Hask Monad, есть соответствующий Клейсли примыкание FK g -| UK g FK g -| UK g между FK g, что приводит нас к категории g Клейсли...

-- Object and morphism mappings.
FK g : a          |-> {a}
       f : a -> b |-> return . f : {a} ~> {b} ~ a -> g b
-- Identity and composition in Kleisli t are return and (<=<)

... и UK g, которая возвращает нас в Хаск:

UK g : {a}            |-> g a
       f : {a} -> {b} |-> join . fmap f : g a -> g b  -- that is, (>>= f)

-- The adjunction isomorphism:
kla : (FK g a ~> {b}) -> (a -> UK g {b})
kra : (a -> UK g {b}) -> (FK g a ~> {b})
-- kla and kra mirror leftAdjunct and rightAdjunct from Data.Functor.Adjunction.
-- The underlying Haskell type is a -> g b on both sides, so we can simply have:
kla = id
kra = id

В соответствии с Simon C Three, пусть g будет монадой функций, на которой будет построен трансформатор. Трансформатор будет каким - то образом включить эффекты другого HASK монады, m, которые я иногда называют как "базовой" монады, следуя обычной терминологии Haskell.

Если мы попытаемся сжать m между FK g и UK g, мы столкнемся со вторым вопросом, упомянутым выше: нам понадобится эндофунктор Kleisli- g, а не Hask. Больше нечего делать, кроме как сделать это. Под этим я подразумеваю, что мы можем определить функтор для функторов (точнее, функтор между двумя категориями эндофункторов), который, мы надеемся, превратит m в то, что мы сможем использовать. Я назову этот "высший" функтор HK g. Применение этого к m должно дать что-то вроде этого:

-- Keep in mind this is a Kleisli-g endofunctor.
HK g m : {a}                |-> {m a}
         f : {a} ~> {b}     |-> kmap f : {m a} ~> {m b} ~ m a -> g (m b)
-- This is the object mapping, taking functors to functors.
-- The morphism mapping maps natural transformations, a la Control.Monad.Morph:
         t : ∀x. m x -> n x |-> kmorph t : ∀x. {m x} ~> {n x} ~ ∀x. m x -> g (n x)
-- I won't use it explicitly, but it is there if you look for it.

Клейсли на Клейсли

(Примечание: впереди настойчивый категорический поворот. Если вы спешите, смело переходите к подразделу "Сводка".)

UK g. HK gm. FK g UK g. HK gm. FK g будет эндофунктором Hask, аналогом конструкции Three. Далее мы хотим, чтобы это была монада на Хаске. Мы можем убедиться в этом, настроив HK gm в качестве монады в категории Kleisli- g. Это означает, что нам нужно выяснить аналоги для fmap, return и join на Kleisli- g:

kmap : {a} ~> {b} |-> {m a} ~> {m b}
       (a -> g b)  ->  m a -> g (m b)

kreturn : {a} ~> {m a}
          a -> g (m a)

kjoin : {m (m a)} ~> {m a}
        m (m a) -> g (m a) 

Для kreturn и kjoin, давайте попробуем простейшие вещи, которые могли бы сработать:

kreturn :: (Monad g, Monad m) => a -> g (m a)
kreturn = return . return 

kjoin :: (Monad g, Monad m) => m (m a) -> g (m a)
kjoin = return . join

kmap несколько сложнее. fmap @m выдаст m (ga) вместо g (ma), поэтому нам нужен способ вытащить g слой наружу. Как это бывает, есть удобный способ сделать это, но он требует, чтобы g был Distributive функтором:

kmap :: (Monad g, Distributive g, Monad m) => (a -> g b)  ->  m a -> g (m b)
kmap f = distribute . fmap f  -- kmap = collect

Законы и условия дистрибуции

Эти предположения, конечно, ничего не значат, если мы не докажем, что они законны:

-- Functor laws for kmap
kmap return = return
kmap g <=< kmap f = kmap (g <=< f)

-- Naturality of kreturn
kmap f <=< kreturn = kreturn <=< f

-- Naturality of kjoin
kjoin <=< kmap (kmap f) = kmap f <=< kjoin

-- Monad laws
kjoin <=< kreturn = return
kjoin <=< kmap kreturn = return
kjoin <=< kmap kjoin = kjoin <=< kjoin

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

-- dist :: t (g a) -> g (t a)
-- I'm using 'dist' instead of 'distribute' and 't' instead of 'm' here for the
-- sake of notation neutrality. 
dist . fmap (return @g) = return @g                 -- #1
dist . return @t = fmap (return @t)                 -- #2
dist . fmap (join @g) = join @g . fmap dist . dist  -- #3
dist . join @t = fmap (join @t) . dist . fmap dist  -- #4
-- In a nutshell: dist must preserve join and return for both monads.

В нашем случае условие # 1 дает kmap идентичность, kjoin правильной личности и kjoin ассоциативности; # 2 дает kreturn; № 3, функторная композиция; # 4, kjoin (левая идентичность kjoin не зависит ни от одного из четырех условий). Окончательная проверка вменяемости устанавливает, что требуется для выполнения самих условий. В конкретном случае distribute его очень сильные свойства естественности означают, что четыре условия обязательно выполняются для любого законного Distributive, поэтому мы готовы идти вперед.

Завершение

Вся UK g. HK gm. FK g UK g. HK gm. FK g Монада UK g. HK gm. FK g может быть получена из частей, которые у нас уже есть, путем разбиения HK gm на присоединение Клейсли, которое полностью аналогично присоединению Клейсли, с которого мы начинали, за исключением того, что мы начинаем с Klesili -g, а не с Hask:

HK g m = UHK g m . FHK g m

FHK g m : {a}        |-> <{a}>
      f : {a} ~> {b} |-> fmap return . f : <{a}> ~> <{b}> ~ a -> g (m b)
-- kreturn <=< f = fmap (return @m) . f
-- Note that m goes on the inside, so that we end up with a morphism in Kleisli g.

UHK g m : <{a}>          |-> {m a}
      f : <{a}> ~> <{b}> |-> fmap join . distribute . fmap f : {m a} ~> {m b} ~ m a -> g (m b)
-- kjoin <=< kmap f = fmap (join @m) . distribute . fmap f

-- The adjunction isomorphism:
hkla : (FHK g m {a} ~> <{b}>) -> ({a} ~> UHK g m <{b}>)
hkra : ({a} ~> UHK g m <{b}>) -> (FHK g m {a} ~> <{b}>)
-- Just like before, we have:
hkla = id
hkra = id

-- And, for the sake of completeness, a Kleisli composition operator:
-- g <~< f = kjoin <=< kmap g <=< f
(<~<) :: (Monad g, Distributive g, Monad m)
    => (b -> g (m c)) -> (a -> g (m b)) -> (a -> g (m c))
g <~< f = fmap join . join . fmap (distribute . fmap g) . f

Теперь, когда у нас есть два присоединения, мы можем составить их, что приведет к присоединению трансформатора и, наконец, к return и join для преобразователя:

-- The composition of the three morphism mappings in UK g . HK g m . FK g
-- tkmap f = join . fmap (kjoin <=< kmap (kreturn <=< return . f))
tkmap :: (Monad g, Distributive g, Monad m) => (a -> b) -> g (m a) -> g (m b)
tkmap = fmap . fmap

-- Composition of two adjunction units, suitably lifted through the functors.
-- tkreturn = join . fmap (hkla hkid) . kla kid = join . fmap kreturn . return
tkreturn :: (Monad g, Monad m) => a -> g (m a)
tkreturn = return . return

-- Composition of the adjunction counits, suitably lifted through the functors.
-- tkjoin = join . fmap (kjoin <=< kmap (hkra kid <~< (kreturn <=< kra id)))
--    = join . fmap (kjoin <=< kmap (return <~< (kreturn <=< id)))
tkjoin :: (Monad g, Distributive g, Monad m) => g (m (g (m a))) -> g (m a)
tkjoin = fmap join . join . fmap distribute

(Для категорического объяснения состава единиц и количеств см. Эмили Рил, Теория категорий в контексте, предложение 4.4.4.)

Что касается lift, kmap (return @g) звучит как разумное определение. Это равносильно distribute. fmap return distribute. fmap return (сравните с lift от Benjamin Ходжсон ответа на вопрос Simon C), которая по условию # 1 становится просто:

tklift :: m a -> g (m a)
tklift = return

Законы MonadLift, которые означают, что tklift должен быть морфизмом монады, действительно выполняются, а закон join зависит от условия дистрибутива # 1:

tklift . return = tkreturn
tklift . join = tkjoin . tkmap tklift . tklift

В итоге

Присоединение Клейсли позволяет нам создавать трансфомер из любой Distributive монады, составляя его снаружи любой другой монады. Собрав все это вместе, мы имеем:

-- This is still a Three, even though we only see two Hask endofunctors.
-- Or should we call it FourK?
newtype ThreeK g m a = ThreeK { runThreeK :: g (m a) }

instance (Functor g, Functor m) => Functor (ThreeK g m) where
    fmap f (ThreeK m) = ThreeK $ fmap (fmap f) m

instance (Monad g, Distributive g, Monad m) => Monad (ThreeK g m) where
    return a = ThreeK $ return (return a)
    m >>= f = ThreeK $ fmap join . join . fmap distribute 
        $ runThreeK $ fmap (runThreeK . f) m

instance (Monad g, Distributive g, Monad m) => Applicative (ThreeK g m) where
    pure = return
    (<*>) = ap

instance (Monad g, Distributive g) => MonadTrans (ThreeK g) where
    lift = ThreeK . return

Наиболее существенным примером Distributive является функтор функции. Составление этого снаружи другой монады выдает ReaderT:

newtype KReaderT r m a = KReaderT { runKReaderT :: r -> m a }
    deriving (Functor, Applicative, Monad) via ThreeK ((->) r) m
    deriving MonadTrans via ThreeK ((->) r)

Экземпляры ThreeK полностью согласуются с каноническими ReaderT.

Перевернутые трансформаторы и присоединение Эйленберга-Мура

В приведенном выше выводе мы уложили базовую монаду примыкание Клесли поверх присоединения монады признаков. Мы могли бы сделать это наоборот и начать с присоединения базовой монады. kmap изменение, которое произойдет, произойдет при определении kmap. Поскольку базовая монада может быть в принципе любой монадой, мы бы не хотели накладывать на нее Distributive ограничение, чтобы ее можно было вытянуть наружу, как мы делали с g в приведенном выше выводе. Лучше всего подойдет для нашего игрового плана двойное требование Traversable из монады функций, чтобы его можно было вставить внутрь sequenceA. Это приведет к преобразователю, который будет составлять монаду изнутри, а не снаружи.

Ниже приведена общая внутренняя конструкция. Я назвал его ThreeEM потому что он также может быть получен с помощью дополнений Эйленберга-Мура (вместо Клейсли) и сложения их с базовой монадой сверху, как в Simon C Three. Этот факт, вероятно, имеет отношение к двойственности между присоединениями Эйленберга-Мура и Клесили.

newtype ThreeEM t m a = ThreeEM { runThreeEM :: m (t a) }

instance (Functor t, Functor m) => Functor (ThreeEM t m) where
    fmap f (ThreeEM m) = ThreeEM $ fmap (fmap f) m

instance (Monad t, Traversable t, Monad m) => Monad (ThreeEM t m) where
    return a = ThreeEM $ return (return a)
    m >>= f = ThreeEM $ fmap join . join . fmap sequenceA 
      $ runThreeEM $ fmap (runThreeEM . f) m

instance (Monad t, Traversable t, Monad m) => Applicative (ThreeEM t m) where
    pure = return
    (<*>) = ap

-- In terms of of the Kleisli construction: as the bottom adjunction is now the
-- base monad one, we can use plain old fmap @m instead of kmap to promote return. 
instance (Monad t, Traversable t) => MonadTrans (ThreeEM t) where
    lift = ThreeEM . fmap return

Обычные трансформаторы, которые возникают таким образом, включают MaybeT и ExceptT.

Есть одна потенциальная ловушка с этой конструкцией. sequenceA должно следовать условиям дистрибутивности, чтобы экземпляры были законными. Его Applicative ограничение, однако, делает его свойства естественности намного слабее, чем у distribute, и поэтому не все условия выполняются бесплатно:

• Условие № 1 действительно: оно является следствием законов идентичности и естественности Traversable.

• Условие № 2 также выполняется: sequenceA сохраняет естественные преобразования на toList пока эти преобразования сохраняют toList. Если мы рассматриваем return как естественную трансформацию от Identity, это сразу же имеет место.

• Условие № 3, однако, не гарантируется. Он сохранится, если join @m, взятый как естественное преобразование из Compose mm, сохранится (<*>), но это может быть не так. Если sequenceA фактически выполняет последовательность эффектов (то есть, если traversable может содержать более одного значения), любые различия, возникающие из порядка, в котором выполняются join и (<*>) в базовой монаде, приведут к нарушению условия. Это, кстати, является частью пресловутой проблемы "ListT сделано неправильно": ListT в трансформаторах, построенный в соответствии с этой конструкцией, является законным, только если используется с коммутативными базовыми монадами.

• Наконец, условие # 4 выполняется только в том случае, если join @t, взятый как естественное преобразование из Compose tt, сохраняет toList (то есть, если он не toList, не дублирует или не переставляет элементы). Одним из следствий этого является то, что эта конструкция не будет работать для монад объектов, чье join "принимает диагональ" вложенной структуры (как в общем случае для монад, которые также являются Distributive экземплярами), даже если мы попытаемся описать условие # 3 ограничивая себя коммутативными базовыми монадами.

Эти ограничения означают, что конструкция не так широко применима, как хотелось бы. В конечном итоге ограничение Traversable слишком широкое. Что нам действительно нужно, так это, вероятно, иметь монаду функций в качестве аффинно-проходимого (то есть контейнера, содержащего не более одного элемента - см. Этот пост Олега Гренруса для некоторого обсуждения со вкусом объектива); Насколько я знаю, для этого нет канонического класса Haskell.

Другие возможности

Конструкции, описанные до настоящего времени, требуют, чтобы монада функции была Distributive или Traversable, соответственно. Общая стратегия, однако, совсем не специфична для присоединений Клейсли и Эйленберга-Мура, поэтому вполне возможно попробовать ее, используя другие дополнения. Тот факт, что StateT каррирование приводит к StateT через Simon C Three/AdjointT, даже если State является ни Distributive ни Traversable, может указывать на то, что такие попытки могут быть плодотворными. Однако я не настроен оптимистично.

В связанном обсуждении в другом месте Бенджамин Ходжсон предполагает, что все присоединения, вызывающие монаду, приводят к одному и тому же трансформатору. Это звучит очень правдоподобно, учитывая, что все такие присоединения через уникальные функторы связаны как с добавками Клейсли, так и с Эйленбергом-Муром (см. "Теория категорий в контексте", предложение 5.2.12). ThreeK пример: если мы попытаемся использовать List с конструкцией ThreeK но с использованием свободного/забывчивого присоединения к категории моноидов вместо Kleisli- [], мы получим преобразователь m [] ThreeEM/feature-on-the- внутренняя конструкция дала бы нам, вплоть до "ListT сделали неправильно" необходимости join чтобы быть аппликативным гомоморфизмом.

А как насчет State и его третьего производящего трансформатора? Хотя я не проработал это подробно, я подозреваю, что более уместно думать о distribute и sequenceA A, используемых в конструкциях здесь, как о принадлежности к правой и левой смежным операциям, соответственно, а не ко всей монаде объектов. В случае distribute это будет означать выход за пределы сигнатуры типа Haskell...

distributive :: (Distribute g, Functor f) => f (g a) -> g (f a)

... чтобы увидеть естественное преобразование между функторами Kleisli- g -to-Hask:

distribute  : m . UK g |-> UK g . HK g m

Если я прав в этом, можно будет перевернуть этот ответ и переосмыслить конструкцию Three/AdjointT в терминах присоединения Клейсли к монаде объектов. Если это так, State не сообщает нам много о других монадах функций, которые не являются ни Distributive ни Traversable.

ListT сделано правильно

Стоит также отметить, что не все трансформаторы возникают из-за смешивания монадических эффектов с составом соединений, как мы видели здесь. В трансформаторах ContT и [ SelectT не следуют шаблону; однако, я бы сказал, что они слишком дурацкие, чтобы обсуждать их в этом контексте ("как не указывается в категории монад", как отмечают документы). Лучший пример представлен различными реализациями "ListT сделано правильно", которые позволяют избежать проблем незаконности, связанных с sequenceA (а также потери потоковой передачи), объединяя эффекты базовой монады так, чтобы не требовалось упорядочивать их в привязка трансформатора. Вот эскиз реализации, в иллюстративных целях:

-- A recursion-schemes style base functor for lists.
data ListF a b = Nil | Cons a b
    deriving (Eq, Ord, Show, Functor)

-- A list type might be recovered by recursively filling the functorial
-- position in ListF.
newtype DemoList a = DemoList { getDemoList :: ListF a (DemoList a) }

-- To get the transformer, we compose the base monad on the outside of ListF.
newtype ListT m a = ListT { runListT :: m (ListF a (ListT m a)) }
    deriving (Functor, Applicative, Alternative) via WrappedMonad (ListT m)

-- Appending through the monadic layers. Note that mplus only runs the effect
-- of the first ListF layer; everything eslse can be consumed lazily.
instance Monad m => MonadPlus (ListT m) where
    mzero = ListT $ return Nil
    u 'mplus' v = ListT $ runListT u >>= \case
        Nil -> runListT v
        Cons a u' -> return (Cons a (u' 'mplus' v))

-- The effects are kept apart, and can be consumed as they are needed.
instance Monad m => Monad (ListT m) where
    return a = ListT $ pure (Cons a mzero)
    u >>= f = ListT $ runListT u >>= \case
        Nil -> return Nil
        Cons a v -> runListT $ f a 'mplus' (v >>= f)

instance MonadTrans ListT where
    lift m = ListT $ (\a -> Cons a mzero) <$> m

В этом ListT базовые эффекты монады не находятся ни внутри, ни снаружи списка. Скорее, они прикреплены болтами к корешку списка и становятся материальными благодаря определению типа в терминах ListF.

Связанные трансформаторы, которые построены подобным образом, включают в себя трансформатор свободной монады FreeT, а также основные монадные трансформаторы из эффективных потоковых библиотек (не случайно, что приведенная выше ссылка "ListT сделано правильно" указывает на документацию по каналам),

Может ли этот тип трансформатора быть как-то связан со стратегией стека присоединения, описанной здесь? Я не выглядел достаточно усердно, чтобы рассказать об этом; это выглядит как интересный вопрос для размышления.