Oh, no, I wasn't trying to say that they were equivalent in general - of course, fold right is the more general operator, as you can implement fold left in terms of fold right. (As an OCaml programmer, I'm used to assuming that all my lists are finite[1]).
The interesting part that I wanted to highlight was the fact that when you express fold as a declarative relation, it is possible to obtain both fold left and fold right essentially for free. Maybe this is an obvious fact for Prolog practitioners, but as a functional programmer this was a somewhat surprising discovery for me.
> Here's a neat paper on fold by Graham Hutton: "A tutorial on the universality and expressiveness of fold"
> https://www.cs.nott.ac.uk/~pszgmh/fold.pdf
Oh, nice! Thanks for the pointer, that's a great paper!
[1] Although technically it is possible to represent certain restricted classes of infinite lists in OCaml: https://v2.ocaml.org/manual/letrecvalues.html
The other way works too: fold right can be implemented in terms of fold left. Here's an approach using continuations in OCaml:
let fold_right f z xs = (List.fold_left (fun kont x -> (fun y -> kont (f x y))) Fun.id xs) z;;
https://www.cs.nott.ac.uk/~pszgmh/fold.pdf
It gives a sufficient and necessary condition for when a function can be written as a (right) fold.
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.
The latter is true, but the former is false.
For finite lists, every foldl call can be translated into a foldr call that produces the same result (and vice versa).
Foldr still makes sense for infinite lists in a language w/ lazy evaluation, but foldl will recurse forever.