[HN Gopher] Unifying fold left and fold right in Prolog
___________________________________________________________________
Unifying fold left and fold right in Prolog
Author : gopiandcode
Score : 61 points
Date : 2022-08-26 17:03 UTC (5 hours ago)
(HTM) web link (gopiandcode.uk)
(TXT) w3m dump (gopiandcode.uk)
| galaxyLogic wrote:
| Paper-based explanation of folding:
|
| https://www.globalnerdy.com/2008/09/03/enumerating-enumerabl...
| noneeeed wrote:
| 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.
| galaxyLogic wrote:
| 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.
| noneeeed wrote:
| 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.
| JadeNB wrote:
| > 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".)
| jfarmer wrote:
| 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.
| gopiandcode wrote:
| > 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
| mkeoliya wrote:
| > 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;;
| rraval wrote:
| 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 wrote:
| 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
| rraval wrote:
| 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.
___________________________________________________________________
(page generated 2022-08-26 23:00 UTC)