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.♥︎
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
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, 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.
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, 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.
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)
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.
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♥︎