Unifying fold left and fold right in Prolog | Hacker News Reader

Unifying fold left and fold right in Prolog

gopiandcode.uk

90 pointsgopiandcode15 comments

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

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.

Hah, you beat me to this by a minute. I guess I'm not the only one that looks back on this paper with fondness.

After you have a right fold and a left fold (both of which fold elemental values one by one into a bulk accumulation), might as well pretend we've got access to a bit more working memory than in the days of Unit Record Equipment, and write an associative "bottom up" fold, that first combines pairs of elemental values, then combines pairs of those combinations, etc., terminating with a single bulk result.

cf http://xahlee.info/comp/i/ICFPAugust2009Steele.pdf

> 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.

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

> of course, fold right is the more general operator, as you can implement fold left in terms of fold right.

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;;

Related: Graham Hutton's classic paper: a tutorial on the universality and expressiveness of fold

[PDF]: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf

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.

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.

Paper-based explanation of folding:

https://www.globalnerdy.com/2008/09/03/enumerating-enumerabl...

That's a lovely little demonstration.

The method name `inject` needs to be formally deprecated in Ruby. It's fundamentally a simple method, but the name _really_ throws people off. Reduce isn't perfect, but it's a bit closer to what's happening.

In Smalltalk it is called inject:into: which I think is quite descriptive.

You "inject" (as in push, insert) elements of the recipient-collection one by one INTO a 2-argument function, which function gets replaced by a new version of itself after each element has been "injected" into it.

In contrast I am always confused by names like "foldLeft". Does it mean "fold elements starting FROM left", or "fold elements TO left" ?

Here the Object-Oriented syntax of Smalltalk and Ruby has an advantage: The name of the method is a command (-verb) to the recipient, passing along arguments. The list to iterate over is not one of the arguments, the list is the recipient of the method-call.

Therefore the method-name does not need to say anything about the recipient, and can thus focus on what should be done with the arguments, and thus can can be more clear about that.

I certainly agree with you that `fold` is a terrible name for it. That makes me think of some kind of halving action.

"inject:into" is definitely a bit better. It's amazing how quite a small addition to a name can make a big difference. I'm always keen on my team using longer method/variable names when it can help with meaning, sometimes just a small expansion can really help readability.

> I certainly agree with you that `fold` is a terrible name for it. That makes me think of some kind of halving action.

I think the poster expressed no opinion on `fold` itself, only on the obviousness or un- of which way `foldl` folds: that is, ignoring base conditions,

    afold f z (x:xs) = f x (afold f z xs)

can be said to fold from the left, whereas

    bfold f z (x:xs) = bfold f (f z x) xs

can be said to fold to the left. It happens that the latter is what we call `foldl`, but I think one can't reasonably argue that a clean-room re-discovery of folding—which would surely discover both implementations—would be guaranteed to impose the same convention. (As weak evidence for this, I note that I would be willing to bet only a tiny sum of fake internet points that your grandparent would agree on which of these they meant by "fold from the left", and which of these they meant by "fold to the left".)

> Does it mean "fold elements starting FROM left", or "fold elements TO left" ?

Neither; it means "left-associative fold", like left-associative operator: ((a + b) + c).

You've not explained how that differs from folding to the left. It's true than foldl cannot be used with infinite lists, as it will recurse infinitely, unlike foldr.

The point to emphasise is that neither foldl nor foldr will swap the ordering of the values in the list, which folding to the left might wrongly imply.

That is, if using fold with a function that is associative, foldl and foldr will give the same result, regardless of whether that function is commutative.

Wikipedia has a visualisation: https://en.wikipedia.org/wiki/Fold_(higher-order_function)#A...

The author is confused, their Prolog implementation is clearly a left fold!

I'm only half joking :)

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.

Yes, good catch! I actually wrote the fold predicate thinking of fold left, hence the naming, but as the same predicate can simulate both fold left and right, for the purposes of the blog post, I figured I could get away without renaming the variables.

Reply on news.ycombinator.com