了解 foldr 和 foldl 函数

Question

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

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

我正在努力思考这两个函数。我有两个问题。一个关于函数 f。一般来说，

foldr f v xs

f 可以访问到 xs 的第一个元素和递归处理的尾部。这里：

foldl f v xs

f可以访问xs的最后一个元素和递归处理的tail。

这是一种有用（且正确）的思考方式吗？

我的第二个问题与折叠“右”或“左”有关。在许多地方，他们说 foldr “从右边开始”。例如，如果我扩展表达式

foldr (+) 0 [1,2,3]

我明白了

(+) 1 (foldr (+) 0 [2,3])

所以，我看到它是列表的“从左开始”。第一个元素和递归处理的尾部是函数的参数。有人可以解释一下这个问题吗？

编辑：我的问题之一是传递给 fold 的函数 f；链接的答案没有解决这一点。

Answer 1

“从右开始”是很好的基本直觉，但它也可能会产生误导，正如您刚刚发现的那样。事情的真相是 Haskell 中的列表是单链接的，我们只能直接访问一侧，所以在某种意义上每个列表操作 Haskell从左边“开始”。但它从那里所做的才是重要的。让我们完成扩展您的 foldr 示例。

foldr (+) 0 [1, 2, 3]
1 + foldr 0 [2, 3]
1 + (2 + foldr 0 [3])
1 + (2 + (3 + foldr 0 []))
1 + (2 + (3 + 0))

foldl现在也一样了。

foldl (+) 0 [1, 2, 3]
foldl (+) (0 + 1) [2, 3]
foldl (+) ((0 + 1) + 2) [3]
foldl (+) (((0 + 1) + 2) + 3) []
((0 + 1) + 2) + 3

在foldr的情况下，我们直接进行递归调用，所以我们将head作为我们累加函数的参数，然后我们将另一个参数作为我们的递归调用。

在 foldl 的情况下，我们通过更改累加器参数来进行递归调用。由于我们更改的是论点而不是结果，因此评估的顺序被颠倒了。

区别在于括号“关联”的方式。在 foldr 的情况下，括号关联到右侧，而在 foldl 的情况下，它们关联到左侧。同样，“初始”值在 foldr 的右侧和 foldl.

的左侧

在 Haskell 中对列表使用折叠的一般建议是这样的。

如果您想要遵循列表结构的惰性求值，请使用foldr。由于 foldr 在函数调用内部进行递归，因此如果折叠函数恰好是 guarded （即通过数据构造函数），那么我们的 foldr 调用就会受到保护。例如，我们可以使用 foldr 从另一个无限列表中高效地构造一个无限列表。
使用foldl'（注意末尾的'），严格左折叠，用于希望操作严格的情况。 foldl' 在继续之前强制折叠的每个步骤到 weak head normal form，以防止 thunk 累积。因此，虽然 foldl 将构建 entire 内部表达式，并且 then 可能会在最后对其进行评估，但 foldl' 会做边走边做，这会在大型列表中节省大量内存。
不要在列表中使用 foldl。 foldl 带来的惰性几乎没有用，因为从左侧折叠中获得任何有用信息的唯一方法就是强制整个折叠，在内部建立 thunks 是没有用的。

对于不是right-biased的其他数据结构，规则可能不同。所有这些都是运行假设您的 Foldable 是一个 Haskell 列表。

Understanding foldr and foldl functions