4 ms·

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 https://ww

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

rraval 4y ago
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.
- 082349872349872 4y ago
  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 http://xahlee.info/comp/i/ICFPAugust2009Steele.pdf
gopiandcode 4y ago
> 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 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 https://v2.ocaml.org/manual/letrecvalues.html
- mkeoliya 4y ago
  > 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;;
  - deleted 4y ago
    [deleted]

rraval 4y ago

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.

082349872349872 4y ago
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 http://xahlee.info/comp/i/ICFPAugust2009Steele.pdf

gopiandcode 4y ago

> 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 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 https://v2.ocaml.org/manual/letrecvalues.html

mkeoliya 4y ago
> 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;;
- deleted 4y ago
  [deleted]