Haskell 的 foldr/foldl 定义绊倒新手？对于 foldl 实际函数采用 f(默认情况)x 而对于 foldr 函数采用 f x(默认情况)？

Question

首先，我了解(几乎)折叠函数。鉴于该功能，我可以很容易地计算出会发生什么以及如何使用它。

问题是关于它的实现方式，这导致函数定义略有不同，需要一些时间才能理解。更糟糕的是，大多数折叠示例具有相同类型的列表和默认情况，这无济于事在理解中，因为它们可能不同。

Usage: 
  foldr f a xs
  foldl f a xs
where a is the default case 
definition:
  foldr: (a -> b -> b) -> b -> [a] -> b
  foldl: (a -> b -> a) -> a -> [b] -> a

在定义中，我理解 a 是要传递的第一个变量，b 是要传递给函数的第二个变量。

最终我明白这是因为当 f 最终在 foldr 中被评估时它被实现为 f x a (即默认大小写作为第二个参数传递)。但对于 foldl，它被实现为 f a x(即默认大小写作为第一个参数传递)。

如果我们在两种情况下都将默认情况传递为相同(两者中的第一个参数或第二个参数)，函数定义是否相同？这个选择有什么特别的原因吗？

Answer 1

为了让事情更清楚一些，我将重命名您的 foldl 签名中的几个类型变量...

foldr: (a -> b -> b) -> b -> [a] -> b
foldl: (b -> a -> b) -> b -> [a] -> b

...所以在这两种情况下，a 代表列表元素的类型，b 代表折叠结果的类型。

foldr 和 foldl 之间的主要区别可以通过扩展它们的递归定义来看出。 foldr中f的应用向右关联，初始值显示在元素右侧:

foldr f a [x,y,z] = x `f` (y `f` (z `f` a))

对于 foldl，情况正好相反:关联在左边，初始值显示在左边(正如 Silvio Mayolo 在 his answer 中强调的，这就是它的方式使得初始值在最里面的子表达式中):

foldl f a [x,y,z] = ((a `f` x) `f` y) `f` z

这就解释了为什么列表元素是 foldr 函数的第一个参数，而 foldl 函数的第二个参数。 (当然，可以给 foldl 一个与 foldr 相同的签名，然后使用 flip f 而不是 f定义它时，但这只会造成混淆。)

P.S.:这是一个很好的简单折叠示例，a 和 b 类型彼此不同:

foldr (:) [] -- id
foldl (flip (:)) [] -- reverse