35

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

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

我了解此功能如何为Listof Maybes 工作。例如,应用sequenceon[Just 3, Just 9]给出Just [3, 9].

我注意到应用sequenceon Listof Lists 给出了它的笛卡尔积。有人可以帮我理解这是如何/为什么会发生的吗?

4

3 回答 3

34

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

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

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

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

只需将其阅读为“首先在 1 和 2 之间进行选择,然后在 3 和 4 之间进行选择”。list monad 现在将累积所有可能的结果 - 因此是答案[[1,3],[1,4],[2,3],[2,4]]

(有关更模糊的示例,请参见此处

于 2011-03-14T14:33:25.997 回答
21

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
    ]
于 2011-03-14T13:52:40.320 回答
5

只是为了解释一下,为什么将序列应用于列表列表与将序列应用于可能值列表有很大不同:

当您应用于sequence列表列表时,序列的类型专门来自

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

to(类型构造函数 m 设置为 [])

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

(与 相同sequence :: [[a]] -> [[a]]

在内部,序列使用 (>>=) - 即一元绑定函数。对于列表,此绑定函数的实现与将 m 设置为 Maybe!

于 2011-03-14T21:38:40.037 回答