折叠和折叠等效的充分条件

Question

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

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

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

我很确定必须有精确的条件涉及op的交换性和/或结合性，和/或l的有限性和/或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与一切事物交换的事实，并将其从尾部位置"移动"到头部位置，利用关联性。

例如

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

在问题中提到了充分条件op = const k它是结合的，但没有中性因素。尽管如此，任何acc都会与一切通勤，因此"常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也会发散(即，它返回底部)。