Here's a neat paper on fold by Graham Hutton: "A tutorial on the universality and
expressiveness of fold"<p><a href="https://www.cs.nott.ac.uk/~pszgmh/fold.pdf" rel="nofollow">https://www.cs.nott.ac.uk/~pszgmh/fold.pdf</a><p>It gives a sufficient and necessary condition for when a function can be written as a (right) fold.<p>It's not clear whether the author means to say foldl and foldr are equivalent, or only that any foldl call which terminates can be converted into a foldr call.<p>The latter is true, but the former is false.<p>For finite lists, every foldl call can be translated into a foldr call that produces the same result (and vice versa).<p>Foldr still makes sense for infinite lists in a language w/ lazy evaluation, but foldl will recurse forever.