为什么 foldr 会反转 foldl 的参数？
Why does foldr invert foldl's parameters?
这是一个非常非常简单的 foldl 函数：它接受一个列表，returns 相同的列表：
identityL :: (Integral a) => [a] -> [a]
identityL xs = foldl (\ acc x -> acc ++ [x]) [] xs
我尝试用 foldr 做同样的事情，认为我所要做的就是将 foldl 更改为 foldr 并在“++”周围翻转 "acc" 和“[x]”。但显然，您还需要翻转参数：
identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ x acc -> [x] ++ acc) [] xs
这似乎非常违反直觉，对于一个似乎服务于针对累加器线性处理列表的目的的函数。我可能错误地接近了这个概念；是否有一个简单的折叠模型可以证明翻转参数的怪异性？
编辑：这很愚蠢；正如所指出的，参数顺序相互抵消。以下代码有效：
identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ acc x -> [acc] ++ x) [] xs
我以前看到过这个，但是让我很困扰，因为 acc 应该是一个列表，不需要列表封装，而 x 应该。
然而，当您查看折叠的实际作用时，将 x 和 acc 变量取反是非常有意义的。
给定列表 [1,2,3]，identityL 连续 ++'ing 一个 [x] 到现有的 acc:
((([] ++ [1]) ++ [2]) ++ [3])
而 identityR 连续 ++'ing 一个 acc 到起始 [x]:
([1] ++ ([2] ++ ([3] ++ [])))
foldr 和 foldl 都将列表传递给参数顺序相同的函数。
foldr (+) 0 [1, 2, 3] = 1 + (2 + (3 + 0))
foldl (+) 0 [1, 2, 3] = ((0 + 1) + 2) + 3
仅此而已。
> foldr (\x y -> "(" ++ show x ++ " + " ++ y ++ ")") "0" [1, 2, 3]
"(1 + (2 + (3 + 0)))"
> foldl (\x y -> "(" ++ x ++ " + " ++ show y ++ ")") "0" [1, 2, 3]
"(((0 + 1) + 2) + 3)"
数学
假设你有一个幺半群，M:
identity :: M
op :: M -> M -> M
-- Monoid laws:
-- x `op` (y `op` z) = (x `op` y) `op` z
-- x `op` identity = x
-- identity `op` x = x
foldr 和 foldl 的定义方式，foldr 和 foldl 总是给出相同的结果，假设 op 是总的。它们只是将相同表达式括起来的不同方式。
foldr op identity == foldl op identity
例如，
concat :: [[a]] -> [a]
-- both definitions give same result
concat = foldr (++) []
concat = foldl (++) []
sum :: Num a => [a] -> a
-- both definitions give same result
sum = foldr (+) 0
sum = foldl (+) 0
product :: Num a => [a] -> a
-- both definitions give same result
product = foldr (*) 1
product = foldl (*) 1
对于非关联运算，这无关紧要，因为 foldr 和 foldl 通常不会给出相同的结果。对于交换运算，这是无关紧要的，因为 foldr 和 foldl 将给出相同的结果，无论参数以何种顺序进入。这仅对一般的幺半群有用。
或者，换句话说，您可以将 foldr 和 foldl 视为将自由幺半群（a.k.a 列表）转换为您选择的另一个幺半群的工具。
如果您将 foldr 视为替换列表中的 (:) 和 []，那么传递给函数的参数顺序就很合理了：
xs = x1 : x2 : x3 : ... : []
foldr f a xs = x1 `f` x2 `f` x3 `f` ... `f` a
这是一个非常非常简单的 foldl 函数：它接受一个列表，returns 相同的列表：
identityL :: (Integral a) => [a] -> [a]
identityL xs = foldl (\ acc x -> acc ++ [x]) [] xs
我尝试用 foldr 做同样的事情，认为我所要做的就是将 foldl 更改为 foldr 并在“++”周围翻转 "acc" 和“[x]”。但显然，您还需要翻转参数：
identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ x acc -> [x] ++ acc) [] xs
这似乎非常违反直觉，对于一个似乎服务于针对累加器线性处理列表的目的的函数。我可能错误地接近了这个概念；是否有一个简单的折叠模型可以证明翻转参数的怪异性？
编辑：这很愚蠢；正如所指出的，参数顺序相互抵消。以下代码有效：
identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ acc x -> [acc] ++ x) [] xs
我以前看到过这个，但是让我很困扰，因为 acc 应该是一个列表，不需要列表封装，而 x 应该。
然而，当您查看折叠的实际作用时，将 x 和 acc 变量取反是非常有意义的。
给定列表 [1,2,3]，identityL 连续 ++'ing 一个 [x] 到现有的 acc:
((([] ++ [1]) ++ [2]) ++ [3])
而 identityR 连续 ++'ing 一个 acc 到起始 [x]:
([1] ++ ([2] ++ ([3] ++ [])))
foldr 和 foldl 都将列表传递给参数顺序相同的函数。
foldr (+) 0 [1, 2, 3] = 1 + (2 + (3 + 0))
foldl (+) 0 [1, 2, 3] = ((0 + 1) + 2) + 3
仅此而已。
> foldr (\x y -> "(" ++ show x ++ " + " ++ y ++ ")") "0" [1, 2, 3]
"(1 + (2 + (3 + 0)))"
> foldl (\x y -> "(" ++ x ++ " + " ++ show y ++ ")") "0" [1, 2, 3]
"(((0 + 1) + 2) + 3)"
数学
假设你有一个幺半群，M:
identity :: M
op :: M -> M -> M
-- Monoid laws:
-- x `op` (y `op` z) = (x `op` y) `op` z
-- x `op` identity = x
-- identity `op` x = x
foldr 和 foldl 的定义方式，foldr 和 foldl 总是给出相同的结果，假设 op 是总的。它们只是将相同表达式括起来的不同方式。
foldr op identity == foldl op identity
例如，
concat :: [[a]] -> [a]
-- both definitions give same result
concat = foldr (++) []
concat = foldl (++) []
sum :: Num a => [a] -> a
-- both definitions give same result
sum = foldr (+) 0
sum = foldl (+) 0
product :: Num a => [a] -> a
-- both definitions give same result
product = foldr (*) 1
product = foldl (*) 1
对于非关联运算，这无关紧要，因为 foldr 和 foldl 通常不会给出相同的结果。对于交换运算，这是无关紧要的，因为 foldr 和 foldl 将给出相同的结果，无论参数以何种顺序进入。这仅对一般的幺半群有用。
或者，换句话说，您可以将 foldr 和 foldl 视为将自由幺半群（a.k.a 列表）转换为您选择的另一个幺半群的工具。
如果您将 foldr 视为替换列表中的 (:) 和 []，那么传递给函数的参数顺序就很合理了：
xs = x1 : x2 : x3 : ... : []
foldr f a xs = x1 `f` x2 `f` x3 `f` ... `f` a