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也会发散(即,它返回底部).