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:

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!

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.

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

For example to sum a bunch of numbers, just:

Yeah, yeah, I know, I know, in Scheme, for adding up small list it’s already possible to just (apply + my-list-of-numbers). But this does come in handy for other stuff. 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!

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.

Or, optionally:

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.

Or, optionally:

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?

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!

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♥︎

Proxied content from gemini://idiomdrottning.org/fold-maps (external content)

Gemini request details:

Original URL
gemini://idiomdrottning.org/fold-maps
Status code
Success
Meta
text/gemini; lang=en
Proxied by
kineto

Be advised that no attempt was made to verify the remote SSL certificate.