通常说来，monad变压器是否由附加条件产生？

Question

在“ 伴随函子”中确定monad变压器，但升降机在哪里？，西蒙C向我们展示了该结构...

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

...，作为那里讨论的答案，可以给instance Adjunction f u => MonadTrans (Three u f)（附加语将其提供为AdjointT）。因此，任何Hask / Hask附加都将导致monad变压器。尤其StateT s是通过(,) s和之间的临时连接以这种方式产生(->) s。

我的后续问题是：此构造是否可以推广到其他monad变压器？是否有办法从合适的附件中从变压器包中衍生出其他变压器？

---

Meta备注：我的回答最初是为Simon C的问题写的。我选择将其分解为一个自我回答的问题，因为在重读该问题时，我注意到我所谓的回答与该评论中的讨论有关，而与问题本身无关。这个问答可能还会跟进另外两个密切相关的问题：是否有一个单声道没有相应的单声道转换器（IO除外）？并且具有可遍历的任意单子的组合是否总是单子？

Answer 1

此答案中的三个构造也可以在Gist中以可复制的形式使用。

西蒙C的建筑 ...

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

...依赖f并且u是Hask的终结者。虽然在的情况下StateT可以解决问题，但要使其更笼统，我们必须处理两个相关的问题：

• 首先，我们需要为变压器所基于的“特征单子”找到合适的附加条件。和

• 其次，如果这样的附加条件使我们脱离了Hask，我们将不得不以某种方式解决无法m直接使用Hask monad的事实。

我们可以尝试许多有趣的附加功能。特别是，每个单核都可以使用两种附加语：Kleisli附加语和Eilenberg-Moore附加语（有关它们的详细分类，请参见Emily Riehl，上下文中的范畴论，第5.2节）。在占该答案前半部分的分类偏移中，我将重点介绍Kleisli附加语，只是因为在伪Haskell中摆动比较容易。

（通过伪哈斯克尔，我的意思是会出现在下面的符号的大肆滥用为了使它更容易对眼睛，我将用一些特别约定：|->指东西不一定类型之间的映射;同样，:手段类似于类型签名的东西; ~>意味着非Hask形态;卷曲和尖括号突出显示了选定的非Hask类别中的对象; .也意味着函子组成;并且F -| U意味着F并且U是伴随函子。）

克莱斯里附加语

如果g是Hask Monad，则FK g -| UK g之间有一个对应的Kleisli附加语FK g，将我们带到g的Kleisli类别...

-- 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，这使我们回到Hask：

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将monad作为特征，在其上构建变压器。m遵循常规的Haskell术语，转换器将以某种方式合并另一个Hask monad的效果，有时我将其称为“基本monad”。

如果试图m在FK g和之间进行挤压UK g，则会遇到上述第二个问题：我们将需要一个Kleisli- gendofunctor，而不是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 g m . FK g将是Hask endofunctor，与Three建筑相对应。我们进一步希望它成为Hask上的单子。我们可以通过HK g m在Kleisli- g类别上设置为monad 来确保这一点。这意味着我们需要弄清楚同行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 (g a)而不是g (m a)，因此我们需要一种方法将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 g m . FK gmonad可以通过拆分HK g m为Kleisli附件从我们已经拥有的片段中获得，该附件与我们开始时使用的Kleisli附件完全相似，只是我们从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

现在，我们已经在手中有两张adjunctions，我们可以撰写他们，导致变压器红利和，终于，以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

（有关单元和协同单元组成的分类解释，请参见Emily Riehl，“上下文中的分类理论”，命题4.4.4。）

至于lift，kmap (return @g)听起来像是一个明智的定义。那达distribute . fmap return（与比较lift从本杰明·霍奇森的回答西蒙C'S问题），它通过条件＃1变为简单：

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

这些MonadLift定律tklift一定是单子态，这确实符合join定律，而定律依赖于分配条件＃1：

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

综上所述

克莱斯里（Kleisli）附加功能使我们可以通过将任何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是函数函子。组成另一个monad的外面给出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的。

翻转变压器和Eilenberg-Moore附加

在上面的推导中，我们将基本monad Klesli附件叠加在特征monad附件之上。可以想象，我们可以反过来做，从基本monad附加函数开始。定义时将会发生至关重要的变化kmap。由于基本monad原则上可以是任何monad，因此我们不希望对其施加任何Distributive约束，以便可以像g上面派生的那样将其向外拉。双重需要Traversable功能monad，这是更适合我们游戏计划的一项，以便可以使用将该功能推入其中sequenceA。这将导致一个在内部而不是外部构成特征单子的变压器。

下面是整体内部结构的构造。我ThreeEM之所以这样称呼它，是因为它也可以通过使用Eilenberg-Moore附加语（而不是Kleisli附加语）并将它们与基础monad堆叠在一起而获得，如Simon C的用法Three。这个事实可能与Eilenberg-Moore附加物和Klesili附加物之间的对偶有关。

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。如果我们将return视为从的自然转换Identity，那将立即成立。

• 但是，条件＃3不能得到保证。这将举行，如果join @m，作为从改造自然Compose m m，保留(<*>)，但可能并非如此。如果sequenceA实际对效果进行排序（即，如果可遍历可以保存一个以上的值），则由于基本单声道的执行顺序join和(<*>)执行顺序所引起的任何差异都将导致违反条件。顺便说一句，这是臭名昭著的“ ListT做错了”问题的一部分：ListT按照这种结构制造的in变压器只有与可换基本单子一起使用才合法。

• 最后，条件＃4仅在join @t从中作为的自然转换Compose t t保留时才成立toList（也就是说，如果不删除，重复或重新排列元素）。一个结果是，即使我们试图通过限制自己来覆盖条件＃3，但这种构造对于join嵌套结构“取对角线”的特征单子将不起作用（通常也是Distributive实例的单子）。交换基本单子。

这些限制意味着该构造并未像人们希望的那样广泛适用。最终，Traversable约束范围太广。我们真正需要的是使monad功能具有仿射可遍历的能力（也就是说，一个容器最多可容纳一个元素- 有关有关镜头的讨论，请参见Oleg Grenrus的这篇文章）；据我所知，虽然没有规范的Haskell类。

其他可能性

到目前为止描述的结构要求特征monad 分别为Distributive或Traversable。但是，总体策略并非完全针对Kleisli和Eilenberg-Moore附加语，因此可以想象在使用其他附加语时尝试使用它。尽管Since StateTC的Three/ 既不是也不是，AdjointT但导致了这种令人发指的附加语的事实，这可能表明这种尝试可能是富有成果的。但是，我对此并不乐观。StateDistributiveTraversable

在其他地方的相关讨论中，本杰明·霍奇森（Benjamin Hodgson）猜想，所有诱导一个monad的附加语都指向同一个变压器。考虑到所有这些附加语都通过唯一的函子与Kleisli和Eilenberg-Moore附加语相关联，这听起来很合理（有关信息，请参见上下文中的范畴论，命题5.2.12）。举个例子：如果我们尝试List进行ThreeK构造，但使用自由/健忘的附加词组而不是Kleisli- []，则最终得到的m []变压器是ThreeEM/ feature-on-the-inside构造可以给我们的， “ ListT做错了问题”需要join是一个应用同态的。

那么State，它产生变压器的第三附加呢？虽然我还没有详细的工作了，我怀疑它更拨付想distribute和sequenceA，如这里的结构中，属于左右伴随矩阵，分别，而不是给整体特征单子。在的情况下distribute，就等于超越了Haskell类型签名...

distribute :: (Distribute g, Functor m) => m (g a) -> g (m a)

...了解Kleisli g-to-Hask函子之间的自然转换：

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

如果我对此表示正确，则可以改掉这个答案，并根据功能单子的Kleisli附加词重新解释Three/ AdjointT构造。如果是这种情况，请State不要告诉我们很多既不是Distributive也不是的其他功能单子Traversable。

ListT做对了

还值得注意的是，并非所有的变压器都是通过按这里所看到的方式通过附加成分的组合来混合单调效果而产生的。在变压器中，ContT和[ SelectT不遵循模式；但是，我要说的是，它们太古怪了，因此无法在这种情况下进行讨论（文档指出，“不是monads类的仿函数” ）。各种“正确完成ListT”的实现方式提供了一个更好的示例，该实现方式sequenceA通过将基本monad效果啮合在一起而避免了与之相关的非法问题（以及流问题的损失），而这种效果不需要在序列中对它们进行排序。变压器的绑定。这是一个实现的草图，用于说明目的：

-- 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。

以类似方式构建的相关转换器包括free-monad转换器FreeT以及有效的流库中的核心monad转换器（我在上面提到的指向管道文档的“ ListT done right”链接并非偶然）。

这种变压器可以与此处描述的附加堆叠策略相关吗？我还没有足够努力地解决这个问题。它看起来是一个值得思考的有趣问题。