简单的`foldM`示例

Question

看foldM:

foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a

我试图创建一个foldM简单地将列表的每个元素附加[1,2,3]到自身的示例.

基于我最初的(错误的)理解foldM,我期望[[1], [2], [3]]作为以下的输出:

ghci> let f = (\xs x -> [x] : [xs])

但是我错了:

ghci> foldM f [] [1,2,3]
[[3],[2],[3],[1],[3],[2],[3],[]]

请解释一下这个例子中发生了什么.

Answer 1

在阅读文档并foldM在GHCi中稍微调整一下后,我想我可以解释一下你的例子中发生了什么.让我们重新检查一下类型签名foldM:

foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a

从这种类型的签名,我们可以得出结论,它foldM接受一个函数(a -> b -> m a)并将其应用于list([b])的每个元素.第二个参数是在"第一次调用"中传递给函数的初始值.后续调用使用应用函数的结果值(从中"提取" m a).

因此,当你这样做时:

ghci> let f = (\xs x -> [x] : [xs])
ghci> foldM f [] [1,2,3]
[[3],[2],[3],[1],[3],[2],[3],[]]

它相当于:

ghci> ([] `f` 1) >>= (`f` 2) >>= (`f` 3)
ghci> [[3],[2],[3],[1],[3],[2],[3],[]]

如果我们将上面的行划分为以下子表达式,我们可以更清楚地看到发生了什么:

ghci> ([] `f` 1)
ghci> [[1],[]]
ghci> ([] `f` 1) >>= (`f` 2)
ghci> [[2],[1],[2],[]]
...

该函数f将列表和值作为参数,创建单个列表(将值放在其自己的列表中)并将其添加到列表列表中.最初,当我们有一个空列表时,结果很明显:( [[1],[]]这是我们"m a"的类型签名).现在,正如我之前所说,为了f再次调用,必须"a"从该结果中获取新值.这次,我们调用f提取的值和提供的列表中的下一个值(即2from [1,2,3]).问题是,考虑到我们"m a"是什么[[1],[]],我们应该将哪个列表作为第一个参数传递给f:[1]或[]？答案依赖于>>=运算符对列表的行为,可以将其视为非确定性计算,将给定函数应用于给定列表中的每个元素并组合结果.对于示例中的这个特定步骤,f将针对两个不同的第一个参数调用两次:f [1] 2和f [] 2.

我试图根据作者给出的例子回答这个问题,但是用于显示foldM这个特定情况下的行为的monadic链可以用来推理任何Monad.