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

我的问题是关于Prelude中的sequence函数，其签名如下：

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

我理解这个功能如何适用于List的Maybes。例如，在[Just 3, Just 9]上应用sequence给出Just [3, 9]。我注意到在List的Lists上应用sequence给出了它的笛卡尔积。有人可以帮我理解这是怎么回事？

已邀请:

3 个回复

这是有效的，因为在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]]。（对于一个更加模糊的例子，请看这里）

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
    ]

只是为了解释一下，为什么将序列应用到列表列表与序列应用到Maybe-values列表有很大不同：当您将sequence应用于列表列表时，序列的类型将专门用于

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

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

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

（与sequence :: [[a]] -> [[a]]相同）在内部，序列使用（>> =） - 即monadic绑定函数。对于列表，这个绑定函数的实现完全不同于m设置为Maybe！

要回复问题请先登录或注册