haskell - foldl 和 foldr 等价的充分条件

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是无限的， foldl无论如何总是发散 op,acc是。如果 op对第二个参数很严格， foldr也发散(即，它返回底部)。