任意 monad 与 traversable 的组合总是 monad 吗? [英] Is the composition of an arbitrary monad with a traversable always a monad?

问题描述

如果我有两个单子 m 和 n，并且 n 是可遍历的，我是否一定有一个复合 m-over-n monad?

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

自然，这种类型检查，我相信适用于我检查过的一些情况(读者超过列表，状态超过列表)——例如，组合的monad"满足 monad 法则——但我不确定这是否是一个通用方法，用于在可遍历的单子上分层.

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.

推荐答案

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

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 = [], 单元 X -> SX 发送 x 给 [x];

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

T = n = (->) Bool，或者等价于 TX = X × X，单位 X -> TX 发送 x 到 (x,x).

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

维基百科页面右下图不通勤，因为组合S -> TS -> ST将xs :: [a]发送到(xs,xs)，然后是从 xs 中提取的所有对的笛卡尔积；而右侧映射 S -> ST 将 xs 发送到仅由 x 的对 (x,x) 组成的对角线"在 xs 中.这与导致您提议的 monad 不满足其中一项单位定律的问题相同.

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 与 traversable 的组合总是 monad 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！