foldr与foldl在(++)操作符下是否等价？

首先结论：对于有限的列表输入，两者结果完全相同；但对于无限列表，两者行为差异极大，因此整体上不能认为这两个表达式等价。

核心逻辑分析 #

• 列表拼接操作(++)满足结合律：对任意列表a、b、c，(a ++ b) ++ c = a ++ (b ++ c)始终成立，且空列表[]是(++)的单位元（[] ++ a = a ++ [] = a）。
• foldr是右折叠，执行逻辑为：foldr (++) [] [x1, x2, ..., xn] = x1 ++ (x2 ++ (... ++ (xn ++ [])...))
• foldl是左折叠，执行逻辑为：foldl (++) [] [x1, x2, ..., xn] = ((...(([] ++ x1) ++ x2) ++ ...) ++ xn)

借助(++)的结合律，有限列表下两种折叠的最终拼接结果完全一致，不存在“内容相同顺序不同”的情况——结果的元素顺序和原列表中各子列表的顺序完全一致。

关键差异：无限列表的处理 #

当输入是无限列表时，两者的行为天差地别：

• foldr (++) []会利用惰性求值特性，立即返回第一个子列表，后续元素仅在需要时才会拼接，因此可以正常处理无限列表，返回一个无限的拼接结果。
• foldl (++) []会从左到右不断执行拼接操作，永远无法完成初始折叠步骤，陷入无限循环，不会返回任何结果。

对比你提到的其他操作符 #

• (+)满足结合律且0是单位元，因此foldr (+) 0和foldl (+) 0对有限/无限列表（只要和存在）的结果一致。
• (-)不满足结合律，且0不是它的右单位元（x - 0 = x但0 - x ≠ x），因此两者结果必然不同。

内容的提问来源于stack exchange，提问作者holypropa