💾 Archived View for idiomdrottning.org › fold-maps captured on 2024-08-25 at 00:53:17. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

A fold is a map

OK, Scheme students, this is gonna get dense. Start at the top, don’t skip ahead, and when you’ve found the one you need, stop reading, grab it and get back to work.♥︎

By “frobnicate” I just mean whatever code you want to put in there. Upcase, count letters, cons, reverse, all kinds of stuff. Side effects are fine too, this isn’t Haskell.♥︎ And by “frobnication” I mean the output of such! el, elem, element… beloved pet names for the same thing: the items, numbers, words, lists, sprites or whatever things, elements, you want your frobnication to work on. Neither the word frobnicate nor the word elem needs to appear in your code. Instead, use appropriate names. term, file-name, whatever. Although nothing beats a good old x.

Audrey — The Sliver:

These dreams are lucid, baby.

They hurt in every joint and bone.

The scene shifts, we drift into colours.

I fold maps, just wishing to hold you close

Map

Have you ever used a map in Scheme, like this:

(map (λ (el) (… frobnicate and do stuff …)) elems)

but wished that your frobnications could also be able to access the previous frobnication?

Wished that the map, instead of saving away the result of your frobnications in a list, gave it to the next call to frobnication directly?

Fold

fold, from SRFI-1, can do that!

(fold (λ (el previous-frobnication) (… frobnicate and do stuff…)) start-frobnication elems)

You won’t automatically get the list that map gives you but you can do all kinds of things!♥︎

How about when you find yourself wishing you would have the… the next frobnication instead of the previous one?

That’s when you can use a fold-right.

(fold-right (λ (el next-frobnication) (… frobnicate and do stuff…)) start-frobnication elems)

With fold-right you can even fake a regular old map if you are always consing your stuff onto the next frobnication.

Both fold-right and fold get their elements from the start of the list, but, with fold-right since you always need to know the next frobnication, it’ll execute “backwards”. Something to know if you use side effects.♥︎

fold builds it lists from the right side first (while going through the original list left-to-right); it’s a good way to implement a reverse, which is just:

(fold cons '() elems)

fold-right construct its list left-to-right, while still going through the original list left-to-right, but, the last frobnications (and the right-most of the original elems) are going to get done first because the preceding ones needed to know that in order to… uh… it’s time travel basically, what can I say. That’s why it uses a little bit more memory. 1.21 gigawatts.

Reduce

What if you don’t even need a start-frobnication, you’re fine if the start is the car of elems and then you just wanna fold over the cdr of elems? A reduce can do that!

But… you need to provide a default value just in case elems happens to be empty.

(reduce (λ (el previous-frobnication) (… frobnicate and do stuff…)) default elems)
(reduce-right (λ (el next-frobnication) (… frobnicate and do stuff…)) default elems)

For example to sum a bunch of numbers, just:

(reduce + 0 my-list-of-numbers)

Yeah, yeah, I know, I know, when that list is small it’s fine to just apply it. But this does come in handy. Maybe you have a newly made function that only works with two arguments? A reduce or fold can be the way you make it sum up or multiply up or frobnicate up many more in one go.

Pair-fold

Having access to one previous frobnication is nice and all but sometimes you wanna look at the entire remaining list. Time for pair-fold!

(pair-fold
 (λ (all-remaining-elems previous-frobnication)
   (… frobnicate and do stuff…))
 start-frobnication elems)

(pair-fold-right
 (λ (all-remaining-elems next-frobnication)
   (… frobnicate and do stuff…))
 last-frobnication elems)

Unfold

A map takes you from a list to a list with each element separately frobnicated. A fold takes you from a list to whatever you want.

An unfold takes you to a list from whatever you want; you’ll provide three procedures that’ll all get the same input (and the first time around, it’s the start-frobnication value of course) but they do different things to it.

(unfold
 (λ (previous-frobnication) … should we stop yet? y/n …)
 (λ (previous-frobnication) … frobnicate into a list element)
 (λ (previous-frobnication) … prepare the input for next frobnication …)
 start-frobnication)

Or, optionally:

(unfold
 (λ (previous-frobnication) … should we stop yet? y/n …)
 (λ (previous-frobnication) … frobnicate into a list element)
 (λ (previous-frobnication) … prepare the input for next frobnication …)
 start-frobnication
 (λ (last-frobnication) … something special for the tail of the list …))

The friend of fold-right is unfold because you do the leftmost list-element first, then the next and so on.

If you want to go in the other direction, which is sometimes cheaper in terms of memory, there’s the friend of fold which is, of course, unfold-right.

(unfold-right
 (λ (previous-frobnication) … should we stop yet? y/n …)
 (λ (previous-frobnication) … frobnicate into a list element)
 (λ (previous-frobnication) … prepare the input for next frobnication …)
 start-frobnication)

Or, optionally:

(unfold-right
 (λ (previous-frobnication) … should we stop yet? y/n …)
 (λ (previous-frobnication) … frobnicate into a list element)
 (λ (previous-frobnication) … prepare the input for next frobnication …)
 start-frobnication
 my-special-tail)

So, again, the difference between the vanilla unfold vs unfold-right is that with unfold-right you build your list starting with the right end of the list—the tail—and you cons onto that before continuing the loop. With the other unfold you are always anticipating the next thing as you build your list from left to right, kinda like fold-right.

Multiple lists

You know how map can be used on two or even any amount of lists, right?

(map + '(600 700 100) '(20 30 40) '(1 2 3))

That evals to (621 732 143) as you might already know.

And that’s right: fold, fold-right, pair-fold and pair-fold-right can all similarly take multiple lists, unlike reduce and unfold, which can’t.

It’s straight forward to use, your procedure just need to take more arguments, that’s all!

(fold (λ (A B C previous-frobnication) (… frobnicate and do stuff…)) start-frobnication As Bs Cs)

This is good for when you want to do things “in parallel”, stitching together those lists side by side, just like with a map.

Good luck♥︎