Hacker News Reader

Comment by jfarmer | Hacker News Reader

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.

View on HN

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

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

Reply on news.ycombinator.com