haskell - 为什么foldr 会反转foldl 的参数？

Question

这是一个非常非常简单的 Foldl 函数:它接受一个列表，并返回相同的列表:

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 连续将 [x]++' 到现有的 acc:

((([] ++ [1]) ++ [2]) ++ [3])

而identityR 连续++'ing acc 到起始 [x]:

([1] ++ ([2] ++ ([3] ++ [])))

Answer 1

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 视为将自由幺半群(也称为列表)转换为您选择的另一个幺半群的工具。