Haskell的foldr/foldl定义行新手？对于 foldl 实际函数采用 f（默认情况）x 而对于 foldr 函数采用 f x（默认情况）？
Haskell's foldr/foldl definitions trip newbie? For foldl Actual function takes f (default case) x while for foldr function takes f x (default case)?
首先，我了解（几乎）折叠函数。鉴于该功能，我可以很容易地计算出会发生什么以及如何使用它。
问题是关于它的实现方式，这导致函数定义略有不同，这需要一些时间 understand.To 更糟糕的是，大多数折叠示例具有相同类型的列表和默认情况，这对理解没有帮助，因为它们可能不同。
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 （即默认大小写作为第一个参数传递）。
如果我们在两种情况下都将默认情况传递为相同（两者中的第一个参数或第二个参数），函数定义是否相同？这个选择有什么特别的原因吗？
为了让事情更清楚一些，我将在您的 foldl 签名中重命名几个类型变量...
foldr: (a -> b -> b) -> b -> [a] -> b
foldl: (b -> a -> b) -> b -> [a] -> b
... 所以在这两种情况下，a 代表列表元素的类型，b 代表折叠结果的类型。
foldr 和 foldl 之间的主要区别可以通过扩展它们的递归定义来看出。 f在foldr中的应用向右关联，初始值显示在元素的右边：
foldr f a [x,y,z] = x `f` (y `f` (z `f` a))
与foldl相反：关联在左边，初始值显示在左边（正如Silvio Mayolo在中强调的那样必须使初始值位于最里面 sub-expression):
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
折叠是一种变形，或者说是一种将数据结构 "tearing down" 转换为标量的方法。在我们的例子中，我们 "tear down" 一个列表。现在，在处理变形时，我们需要为每个数据构造函数提供一个案例。 Haskell 列表有两个数据构造函数。
[] :: [a]
(:) :: a -> [a] -> [a]
也就是说，[] 是一个构造函数，它不接受任何参数并生成一个列表（空列表）。 (:) 是一个构造函数，它接受两个参数并生成一个列表，将第一个参数放在第二个参数之前。所以我们需要有两个案例。 foldr 是变形的直接例子。
foldr :: (a -> b -> b) -> b -> [a] -> b
如果我们遇到 (:) 构造函数，将调用第一个函数。它将传递第一个元素（(:) 的第一个参数）和递归调用的结果（在 (:) 的第二个参数上调用 foldr）。第二个参数，如您所说的 "default case" ，用于当我们遇到 [] 构造函数时，在这种情况下我们只使用默认值本身。所以它最终看起来像这样
foldr (+) 4 [1, 2, 3]
1 + (2 + (3 + 4))
现在，我们可以用同样的方式设计 foldl 吗？当然。 foldl 不是（完全）变形，但它在精神上表现得像一个变形。在foldr中，默认大小写是最里面的值；它只在递归的 "last step" 处使用，当我们 运行 超出列表元素时。在 foldl 中，我们为了一致性做同样的事情。
foldl (+) 4 [1, 2, 3]
((4 + 1) + 2) + 3
让我们更详细地分析一下。 foldl 可以认为是使用累加器来高效地得到答案。
foldl (+) 4 [1, 2, 3]
foldl (+) (4 + 1) [2, 3]
foldl (+) ((4 + 1) + 2) [3]
foldl (+) (((4 + 1) + 2) + 3) []
-- Here, we've run out of elements, so we use the "default" value.
((4 + 1) + 2) + 3
所以我想对你的问题的简短回答是，从数学上讲，它更一致（也更有用），以确保基本情况始终位于递归调用的最里面，而不是专注于它一直在左边或右边。
考虑调用 foldl (+) 0 [1,2,3,4] 和 foldr (+) 0 [1,2,3,4] 并尝试想象它们的作用：
foldl (+) 0 [1,2,3,4] = ((((0 + 1) + 2) + 3) + 4)
foldr (+) 0 [1,2,3,4] = (0 + (1 + (2 + (3 + 4))))
现在，让我们尝试在每个步骤中交换对 (+) 的调用的参数：
foldl (+) 0 [1,2,3,4] = (4 + (3 + (2 + (1 + 0))))
请注意，尽管是对称的，但这与之前的 foldr 不同。我们仍然从列表的左边开始累加，我只是改变了操作数的顺序。
在这种情况下，因为加法是可交换的，所以我们得到相同的结果，但是如果您尝试折叠某些 non-commutative 函数，例如字符串连接，结果是不同的。折叠 ["foo", "bar", "baz"]，您将获得 "foobarbaz" 或 "bazbarfoo"（而 foldr 也会导致 "foobarbaz"，因为字符串连接是关联的）。
换句话说，这两个定义使得这两个函数对于交换和结合二元运算（如普通算术addition/multiplication）具有相同的结果。将参数交换到累积函数会破坏这种对称性并迫使您使用 flip 来恢复对称行为。
这两个折叠由于它们相反的结合性而产生不同的结果。基值总是出现在最里面的括号内。两个折叠的列表遍历发生方式相同。
使用前缀表示法用 (+) 向右折叠
foldr (+) 10 [1,2,3]
=> + 1 (+ 2 (+ 3 10))
=> + 1 (+ 2 13)
=> + 1 15
=> 16
foldl (+) 10 [1,2,3]
=> + (+ (+ 10 1) 2) 3
=> + (+ 11 2) 3
=> + 13 3
=> 16
两个折叠的计算结果相同，因为 (+) 是可交换的，即
+ a b == + b a
让我们看看当函数不可交换时会发生什么，例如除法或求幂
foldl (/) 1 [1, 2, 3]
=> / (/ (/ 1 1) 2) 3
=> / (/ 1 2) 3
=> / 0.5 3
=> 0.16666667
foldr (/) 1 [1, 2, 3]
=> / 1 (/ 2 (/ 3 1))
=> / 1 (/ 2 3)
=> / 1 0.666666667
=> 1.5
现在，让我们用函数 flip (/)
评估 foldr
let f = flip (/)
foldr f 1 [1, 2, 3]
=> f 1 (f 2 (f 3 1))
=> f 1 (f 2 0.3333333)
=> f 1 0.16666667
=> 0.16666667
类似地，让我们用 f
评估 foldl
foldl f 1 [1, 2, 3]
=> f (f (f 1 1) 2) 3
=> f (f 1 2) 3
=> f 2 3
=> 1.5
因此，在这种情况下，翻转折叠函数参数的顺序可以使左折叠 return 与右折叠具有相同的值，反之亦然。但这并不能保证。示例：
foldr (^) 1 [1, 2, 3] = 1
foldl (^) 1 [1, 2, 3] = 1
foldr (flip (^)) 1 [1,2,3] = 1
foldl (flip (^)) 1 [1,2,3] = 9 -- this is the odd case
foldl (flip (^)) 1 $ reverse [1,2,3] = 1
-- we again get 1 when we reverse this list
顺便说一下，reverse 等同于
foldl (flip (:)) []
但尝试使用 foldr
定义反向
首先，我了解（几乎）折叠函数。鉴于该功能，我可以很容易地计算出会发生什么以及如何使用它。
问题是关于它的实现方式，这导致函数定义略有不同，这需要一些时间 understand.To 更糟糕的是，大多数折叠示例具有相同类型的列表和默认情况，这对理解没有帮助，因为它们可能不同。
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 （即默认大小写作为第一个参数传递）。
如果我们在两种情况下都将默认情况传递为相同（两者中的第一个参数或第二个参数），函数定义是否相同？这个选择有什么特别的原因吗？
为了让事情更清楚一些，我将在您的 foldl 签名中重命名几个类型变量...
foldr: (a -> b -> b) -> b -> [a] -> b
foldl: (b -> a -> b) -> b -> [a] -> b
... 所以在这两种情况下，a 代表列表元素的类型，b 代表折叠结果的类型。
foldr 和 foldl 之间的主要区别可以通过扩展它们的递归定义来看出。 f在foldr中的应用向右关联，初始值显示在元素的右边：
foldr f a [x,y,z] = x `f` (y `f` (z `f` a))
与foldl相反：关联在左边，初始值显示在左边（正如Silvio Mayolo在
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
折叠是一种变形，或者说是一种将数据结构 "tearing down" 转换为标量的方法。在我们的例子中，我们 "tear down" 一个列表。现在，在处理变形时，我们需要为每个数据构造函数提供一个案例。 Haskell 列表有两个数据构造函数。
[] :: [a]
(:) :: a -> [a] -> [a]
也就是说，[] 是一个构造函数，它不接受任何参数并生成一个列表（空列表）。 (:) 是一个构造函数，它接受两个参数并生成一个列表，将第一个参数放在第二个参数之前。所以我们需要有两个案例。 foldr 是变形的直接例子。
foldr :: (a -> b -> b) -> b -> [a] -> b
如果我们遇到 (:) 构造函数，将调用第一个函数。它将传递第一个元素（(:) 的第一个参数）和递归调用的结果（在 (:) 的第二个参数上调用 foldr）。第二个参数，如您所说的 "default case" ，用于当我们遇到 [] 构造函数时，在这种情况下我们只使用默认值本身。所以它最终看起来像这样
foldr (+) 4 [1, 2, 3]
1 + (2 + (3 + 4))
现在，我们可以用同样的方式设计 foldl 吗？当然。 foldl 不是（完全）变形，但它在精神上表现得像一个变形。在foldr中，默认大小写是最里面的值；它只在递归的 "last step" 处使用，当我们 运行 超出列表元素时。在 foldl 中，我们为了一致性做同样的事情。
foldl (+) 4 [1, 2, 3]
((4 + 1) + 2) + 3
让我们更详细地分析一下。 foldl 可以认为是使用累加器来高效地得到答案。
foldl (+) 4 [1, 2, 3]
foldl (+) (4 + 1) [2, 3]
foldl (+) ((4 + 1) + 2) [3]
foldl (+) (((4 + 1) + 2) + 3) []
-- Here, we've run out of elements, so we use the "default" value.
((4 + 1) + 2) + 3
所以我想对你的问题的简短回答是，从数学上讲，它更一致（也更有用），以确保基本情况始终位于递归调用的最里面，而不是专注于它一直在左边或右边。
考虑调用 foldl (+) 0 [1,2,3,4] 和 foldr (+) 0 [1,2,3,4] 并尝试想象它们的作用：
foldl (+) 0 [1,2,3,4] = ((((0 + 1) + 2) + 3) + 4)
foldr (+) 0 [1,2,3,4] = (0 + (1 + (2 + (3 + 4))))
现在，让我们尝试在每个步骤中交换对 (+) 的调用的参数：
foldl (+) 0 [1,2,3,4] = (4 + (3 + (2 + (1 + 0))))
请注意，尽管是对称的，但这与之前的 foldr 不同。我们仍然从列表的左边开始累加，我只是改变了操作数的顺序。
在这种情况下，因为加法是可交换的，所以我们得到相同的结果，但是如果您尝试折叠某些 non-commutative 函数，例如字符串连接，结果是不同的。折叠 ["foo", "bar", "baz"]，您将获得 "foobarbaz" 或 "bazbarfoo"（而 foldr 也会导致 "foobarbaz"，因为字符串连接是关联的）。
换句话说，这两个定义使得这两个函数对于交换和结合二元运算（如普通算术addition/multiplication）具有相同的结果。将参数交换到累积函数会破坏这种对称性并迫使您使用 flip 来恢复对称行为。
这两个折叠由于它们相反的结合性而产生不同的结果。基值总是出现在最里面的括号内。两个折叠的列表遍历发生方式相同。
使用前缀表示法用 (+) 向右折叠
foldr (+) 10 [1,2,3]
=> + 1 (+ 2 (+ 3 10))
=> + 1 (+ 2 13)
=> + 1 15
=> 16
foldl (+) 10 [1,2,3]
=> + (+ (+ 10 1) 2) 3
=> + (+ 11 2) 3
=> + 13 3
=> 16
两个折叠的计算结果相同，因为 (+) 是可交换的，即
+ a b == + b a
让我们看看当函数不可交换时会发生什么，例如除法或求幂
foldl (/) 1 [1, 2, 3]
=> / (/ (/ 1 1) 2) 3
=> / (/ 1 2) 3
=> / 0.5 3
=> 0.16666667
foldr (/) 1 [1, 2, 3]
=> / 1 (/ 2 (/ 3 1))
=> / 1 (/ 2 3)
=> / 1 0.666666667
=> 1.5
现在，让我们用函数 flip (/)
let f = flip (/)
foldr f 1 [1, 2, 3]
=> f 1 (f 2 (f 3 1))
=> f 1 (f 2 0.3333333)
=> f 1 0.16666667
=> 0.16666667
类似地，让我们用 f
foldl
foldl f 1 [1, 2, 3]
=> f (f (f 1 1) 2) 3
=> f (f 1 2) 3
=> f 2 3
=> 1.5
因此，在这种情况下，翻转折叠函数参数的顺序可以使左折叠 return 与右折叠具有相同的值，反之亦然。但这并不能保证。示例：
foldr (^) 1 [1, 2, 3] = 1
foldl (^) 1 [1, 2, 3] = 1
foldr (flip (^)) 1 [1,2,3] = 1
foldl (flip (^)) 1 [1,2,3] = 9 -- this is the odd case
foldl (flip (^)) 1 $ reverse [1,2,3] = 1
-- we again get 1 when we reverse this list
顺便说一下，reverse 等同于
foldl (flip (:)) []
但尝试使用 foldr