foldl和foldr等价的充分条件
考虑表达式E1 = foldl op acc l和E2 = foldr op acc l 。
op ， acc和/或l自然充分条件是什么保证了E1和E2的等价性？
一个天真的例子是，如果op是不变的，那么两者是等价的。
我非常肯定，必须有精确的条件，包括交换性和/或op关联性，和/或l有限性，和/或acc中立性。
如果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也会发散（即返回底部）。