为什么在列表列表中应用`sequence`会导致其笛卡尔积的计算？

Question

我的问题是关于sequence功能Prelude,其签名如下:

sequence :: Monad m => [m a] -> m [a]

我理解这个函数是如何工作的List的Maybe秒.例如,将sequence上[Just 3, Just 9]给人Just [3, 9].

我注意到,应用sequence上List的Lists给出了笛卡尔乘积.有人可以帮我理解这是怎么回事？

Answer 1

这是有效的,因为在Haskell中使用列表作为monad使得它们成为模型的不确定性.考虑:

sequence [[1,2],[3,4]]

根据定义,这与以下相同:

do x <- [1,2]
   y <- [3,4]
   return [x,y]

只需将其读作"首先选择1和2之间,然后选择3到4".列表monad现在将累积所有可能的结果 - 因此答案[[1,3],[1,4],[2,3],[2,4]].

(对于一个更加模糊的例子,请看这里)

Answer 2

sequence 表现得像是这样定义的.

sequence [] = return []
sequence (m:ms) = do
    x <- m
    xs <- sequence ms
    return (x:xs)

(或者sequence = foldr (liftM2 (:)) (return [])无论如何......)

试想一下应用于列表列表时会发生什么.

sequence [] = [[]]
sequence (list : lists) =
    [ x : xs
    | x <- list
    , xs <- sequence lists
    ]

Answer 3

只是解释一下，为什么将序列应用于列表列表与将序列应用于可能值列表如此不同：

当您应用sequence到列表列表时，序列的类型是从

sequence :: Monad m => [m a] -> m [a]

to（类型构造函数 m 设置为 []）

sequence :: [[] a] -> [] [a] 

（与 相同sequence :: [[a]] -> [[a]]）

在内部，序列使用 (>>=) —— 即 monadic 绑定函数。对于列表，此绑定函数的实现与将 m 设置为 Maybe 完全不同！