Haskell:理解折叠函数

Question

我正在从米兰·利波瓦卡(Miran Lipovaca(的《学习你一个哈斯克尔的伟大善！》中学习折叠。

对于以下使用foldl的示例：

sum' :: (Num a) => [a] -> a
sum' xs = foldl (acc x -> acc + x) 0 xs 
ghci> sum' [3,5,2,1]
11

我知道acc是累加器，x是起始值(列表中的第一个值xs(。我不太明白 0 和 xs 是如何作为参数传递到 lambda 函数中的 - 函数如何知道 acc 的值为 0，x 的值为 3？任何见解都值得赞赏。

Answer 1

回想一下foldl的定义：

foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

现在，理解褶皱的最好方法是浏览评估。因此，让我们从：

sum [3,5,2,1]
== foldl (acc x -> acc + x) 0 [3,5,2,1]

foldl函数定义的第二行意味着这等效于以下内容：

== foldl (acc x -> acc + x) ((acc x -> acc + x) 0 3) [5,2,1]

现在，由于 lambda 表达式应用于参数，因此0和3作为acc和x传入：

== foldl (acc x -> acc + x) (0+3) [5,2,1]

这个过程重复：

== foldl (acc x -> acc + x) ((acc x -> acc + x) (0+3) 5) [2,1]
== foldl (acc x -> acc + x) ((0+3)+5) [2,1]
== foldl (acc x -> acc + x) ((acc x -> acc + x) ((0+3)+5) 2) [1]
== foldl (acc x -> acc + x) (((0+3)+5)+2) [1]
== foldl (acc x -> acc + x) ((acc x -> acc + x) (((0+3)+5)+2) 1) []
== foldl (acc x -> acc + x) ((((0+3)+5)+2)+1) []

此时，根据foldl定义的第一行继续评估：

== ((((0+3)+5)+2)+1)

所以直接回答你的问题：函数知道acc和x的值，仅仅是因为foldl的定义将它们的值作为参数传递给函数。

Answer 2

看看如何定义foldl函数会很有帮助：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

因此，如果输入列表为空，则我们只需返回累加器值a 。但是，如果它不为空，那么我们循环。在循环中，我们将累加器值更新为 f a x(即我们将 lambda 函数f应用于当前累加器值和列表的当前元素(。结果是新的累加器值。

我们还通过删除它的第一个元素来更新循环中列表的值(因为我们刚刚处理了第一个元素(。我们继续处理列表中的其余元素，直到没有剩余元素，此时我们返回累加器的值。

foldl 函数等效于命令式语言中的 for 循环。例如，以下是我们如何在 JavaScript 中实现foldl：

const result = foldl((acc, x) => acc + x, 0, [3,5,2,1]);
console.log(result);
function foldl(f, a, xs) {
    for (const x of xs) a = f(a, x);
    return a;
}

希望阐明foldl功能。