foldl 和 foldr 等价的充分条件

Question

考虑表达式 E1 = foldl op acc l 和 E2 = foldr op acc l.

op、acc、and/or、l有哪些自然充分条件可以保证E1和E2等价？

一个天真的例子是，如果 op 是常量，那么两者是等价的。

我很确定必须有精确的条件涉及 op 的交换性 and/or 结合性、l 的 and/or 有限性、and/or 的中性性acc.

Answer 1

若op是结合运算，acc是op的中性元素，l是有限元，则它们等价

的确，foldr的结果是

(l1 `op` (l2 `op` ... (ln `op` acc)))

而foldl的是

(((acc `op` l1) `op` l2) `op` ... ln)

要证明相等，化简acc，重新结合即可。

即使acc不是中性元素，但acc仍然满足较弱的条件

forall x,  acc `op` x = x `op` acc

然后，如果 op 是结合的并且 l 是有限的，我们再次得到所需的等价。

为了证明这一点，我们可以利用 acc 与所有事物交换的事实，并且 "move" 它从尾部位置到头部位置，利用关联性。例如

(l1 `op` (l2 `op` acc))
=
(l1 `op` (acc `op` l2))
=
((l1 `op` acc) `op` l2)
=
((acc `op` l1) `op` l2)

题中提到了充分条件op = const k，它是结合性的，但没有中性元素。尽管如此，任何 acc 都可以通勤，因此 "constant op" 情况是上述充分条件的子情况。

假设op有一个中性元素acc，如果我们假设

foldr op acc [a,b,c] = foldl op acc [a,b,c]      -- (*)

我们得出

a `op` (b `op` c) = (a `op` b) `op` c

因此，如果 (*) 对所有 a,b,c 成立，则 op 必须是关联的。结合性是充分必要的（当存在中性元素时）。

如果l是无限的，那么无论op,acc是什么，foldl总是发散的。如果 op 对其第二个参数严格，则 foldr 也会发散（即 returns 底部）。

Sufficient conditions for foldl and foldr equivalence