一个任意monad的组成是否可以遍历一个monad？ [英] Is the composition of an arbitrary monad with a traversable always a monad?

问题描述

如果我有两个monad m 和 n ，并且 n 是可遍历的，是否必须有一个复合 m -over - n monad？

更正式地说，这是我想到的：

  import Control.Monad 
 import Data.Functor.Compose 
 
 prebind ::（Monad m，Monad n）=> 
 m（n a） - > （a→m（n b））→> m（n（m（nb）））
 mnx`prebind` f = do nx<  -  mnx 
 return $ do x<  -  nx 
 return $ fx 
 
实例（Monad m，Monad n，Traversable n）=> Monad（Compose m n）其中
 return =撰写。返回。返回
撰写mnmnx>> = f =撰写$ do nmnx<  -  mnmnx`prebind`（getCompose。f）
 nnx<  -  sequence nmnx 
 return $ join nnx 
  

当然，这种类型检查，我相信适用于我检查过的一些案例（Reader over List，在列表中列出状态） - 与之相似，组成的monad符合monad法则 - 但我不确定这是否是一种通用的方法，用于将任何monad层叠到可遍历的monad上。

解决方案

不，它并不总是一个monad。您需要关于两个monad的monad操作和分配律 sequence :: n（m a） - >的额外兼容性条件。 m（na），例如维基百科中所述。

您以前的问题给出了一个不满足兼容性条件的例子，即

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

n =（ - >）Bool ，或等价地TX = X×X，单位X - > TX发送x到（x，x）。

维基百科页面右下图确实不是通勤，因为组合S→TS→ST将 xs :: [a] 发送给（xs，xs），然后到从 xs 中绘制的所有对的笛卡尔乘积;而右边的地图S - > ST将 xs 发送给仅由（x，x） for x 在 xs 中。这是同样的问题，导致你提出的单子不符合单位法之一。

If I have two monads m and n, and n is traversable, do I necessarily have a composite m-over-n monad?

More formally, here's what I have in mind:

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

Naturally, this type-checks, and I believe works for a few cases that I checked (Reader over List, State over List) -- as in, the composed 'monad' satisfies the monad laws -- but I'm unsure if this is a general recipe for layering any monad over a traversable one.

解决方案

No, it's not always a monad. You need extra compatibility conditions relating the monad operations of the two monads and the distributive law sequence :: n (m a) -> m (n a), as described for example on Wikipedia.

Your previous question gives an example in which the compatibility conditions are not met, namely

S = m = [], with unit X -> SX sending x to [x];

T = n = (->) Bool, or equivalently TX = X × X, with unit X -> TX sending x to (x,x).

The bottom right diagram on the Wikipedia page does not commute, since the composition S -> TS -> ST sends xs :: [a] to (xs,xs) and then to the Cartesian product of all pairs drawn from xs; while the right-hand map S -> ST sends xs to the "diagonal" consisting of only the pairs (x,x) for x in xs. It is the same problem that caused your proposed monad to not satisfy one of the unit laws.

这篇关于一个任意monad的组成是否可以遍历一个monad？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！