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.
Related: Graham Hutton's classic paper: a tutorial on the universality and expressiveness of fold<p>[PDF]: <a href="https://www.cs.nott.ac.uk/~pszgmh/fold.pdf" rel="nofollow">https://www.cs.nott.ac.uk/~pszgmh/fold.pdf</a><p>Section 5.1 walks the reader through implementing foldl in terms of foldr after laying down the ground work and gradually introducing things one concept at a time.<p>For me, the eye-opening insight was using foldr to generate intermediate functions as values, which is the sort of thing "functional" programming does without thinking twice, but is mind bending for someone coming from a more traditional procedural language background.
The author is confused, their Prolog implementation is clearly a left fold!<p>I'm only half joking :)<p>To elaborate: The variable names "ACC" and "RES" suggest the predicate should be viewed as a left fold, because when the predicate is viewed as a right fold the meanings of the variables are flipped.