具有遍历的任意monad的构成是否始终为monad？

Question

如果我有两个单子m和n,和n是穿越,我一定有复合m-over- n单子？

更正式的,这就是我的想法:

import Control.Monad
import Data.Functor.Compose

prebind :: (Monad m, Monad n) =>
         m (n a) -> (a -> m (n b)) -> m (n (m (n b)))
mnx `prebind` f = do nx <- mnx
                     return $ do x <- nx
                                 return $ f x

instance (Monad m, Monad n, Traversable n) => Monad (Compose m n) where
  return = Compose . return . return
  Compose mnmnx >>= f = Compose $ do nmnx <- mnmnx `prebind` (getCompose . f)
                                     nnx  <- sequence nmnx
                                     return $ join nnx

当然,这种类型检查,我认为适用于我检查的一些案例(读者列表,状态列表) - 如同,组成的'monad'满足monad法则 - 但我不确定这是否是一个通用的配方,用于将任何monad分层到可遍历的monad上.

Answer 1

不,它并不总是一个单子.您需要与两个monad的monad操作和分配法相关的额外兼容性条件sequence :: n (m a) -> m (n a),如维基百科上所述.

您之前的问题给出了一个不符合兼容性条件的示例,即

S = m = [],单位X - > SX将x发送到[x];

T = n = (->) Bool,或等效TX = X×X,单位X - > TX将x发送到(x,x).

维基百科页面上的右下图不通勤,因为组合S - > TS - > ST发送xs :: [a]给(xs,xs)然后发送到所有对的笛卡尔积xs; 而右侧的映射图S - > ST发送xs到"对角线"仅由对(x,x)用于x在xs.同样的问题导致你提出的monad不满足单位法之一.

Answer 2

一些补充说明，以使里德·巴顿的一般答案和您的具体问题之间的联系更加明确。

Monad在这种情况下，根据以下方面计算实例确实值得join：

join' ::  m (n (m (n b))) -> m (n b)
join' = fmap join . join . fmap sequence

通过在适当的位置重新引入compose/并使用，您可以验证这确实相当于您的定义（请注意，您相当于该等式中的 ）。getComposem >>= f = join (fmap f m)prebindfmap f

这个定义使得用图表验证定律变得很容易¹。这是join . return = idie的一个(fmap join . join . fmap sequence) . (return . return) = id：

3210
  MT id MT id MT id MT
     ----> ----> ---->
 rT2 | | rT1 | | rT1 | | ID
 RM3 VV RM3 VVVV
     ----> ----> ---->
MTMT SM2 MMTT jM2 MTT jT0 MT

整个矩形就是单子定律：

中号
    ---->     
rM1 | | ID
    维维  
    ---->     
 MM jM0 M

忽略正方形两侧必然相同的部分，我们看到最右边的两个正方形符合相同的定律。（当然，将这些称为“正方形”和“矩形”有点愚蠢，因为id它们具有所有边，但它更适合我有限的 ASCII 艺术技能。）不过，第一个正方形相当于 ，sequence . return = fmap return它是较低的维基百科页面右图 Reid Barton 提到...

中号
    ---->     
rT1 | | 时间T0
    维维  
    ---->     
 TM sM1 MT  

...正如里德·巴顿的回答所示，这并不是一个既定的事实。

如果我们对定律应用相同的策略join . fmap return = id，就会出现右上图sequence . fmap return = return，然而，这本身并不是问题，因为这只是 的恒等律（的直接结果）Traversable。最后，用定律做同样的事情，join . fmap join = join . join就会产生另外两个图表——sequence . fmap join = join . fmap sequence . sequence并且sequence . join = fmap join . sequence . fmap sequence——出现。

脚注：

1. 速记图例：ris return、sissequence和jis join。函数缩写后面的大写字母和数字消除了所涉及的 monad 的歧义以及其引入或更改的层最终所处的位置- 在 的情况下s，它指的是最初的内层，因为在这种情况下我们知道外层始终是T. 这些层从下到上编号，从零开始。通过在第一个函数下方写下第二个函数的简写来表示组合。