Left-right fold equivalence
= Left-right fold equivalence
For finite <lists>, if $x\oplus(y\otimes z)=(x\oplus y)\otimes z$ and $x\oplus a=a\otimes x$, then the <right fold> with step $\oplus$ and seed $a$ equals the <left fold> with step $\otimes$ and seed $a$. The two steps need not be identical. Equality of the resulting values does not imply equal <time complexity>; <list concatenation> is an important example.