haskell - 简单的 `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)并将其应用于列表的每个元素( [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"该结果的值(value)。这一次，我们调用f在提供的列表中传递提取的值和下一个值(即 2 中的 [1,2,3] )。问题是，考虑到我们的 "m a"是 [[1],[]] ，我们应该将哪个列表作为第一个参数传递给 f : [1]或 [] ?答案取决于 >>= 的行为。列表运算符，可以被视为非确定性计算，它将给定函数应用于给定列表中的每个元素并组合结果。对于示例中的这个特定步骤，f将针对两个不同的第一个参数调用两次:f [1] 2和 f [] 2 .

我试图根据作者给出的例子来回答这个问题，但是一元链用来明确 foldM 的行为在这种特殊情况下，可以用来推理任何 Monad。