Friday, April 20, 2007

function of the day: fold

The fold function does very much what the name implies: it's meant to fold ingredients into a big mixing bowl, of course. Here's a definition:


;; fold: (ingredient bowl -> bowl) bowl (listof ingredient) -> bowl
;; Folds in a list of ingredients into a bowl with a folding-action.
(define (fold folding-action a-bowl ingredients)
(cond
[(empty? ingredients) a-bowl]
[else
(local ((define mixed-bowl (folding-action
(first ingredients)
a-bowl)))
(fold folding-action mixed-bowl (rest ingredients)))]))


FOLD here adds an ingredient at a time, using the folding-action to mix in every ingredient thoroughly into our large bowl. Once we have this incorporating function, we can roll up our sleeves and whisk some pancake batter:


;; make-pancake-batter: -> string
;; Example of FOLD to make pancake batter.
(define (make-pancake-batter)
(local ((define (whisk an-ingredient a-bowl)
(string-append a-bowl an-ingredient))

(define pancake-ingredients '("flour" "sugar" "eggs" "milk"))

(define empty-bowl ""))
(fold whisk empty-bowl pancake-ingredients)))

Oh! I forgot the baking powder, so those pancakes will be a little stiff. Oh well.

Of course, we might even want to whisk in a slightly different way:

(local
((define (whisk an-ingredient a-bowl)
(cond [(string=? an-ingredient "eggs")
(string-append a-bowl "egg-white-only")]
[else
(string-append a-bowl an-ingredient)])))
(fold whisk "" '("flour" "eggs" "cabbage")))

Now we've got the basics of an okonomiyaki, I suppose.

We might even be silly enough to mix things that aren't even food!

> (fold + 0 '(1 2 3 4 5))
15

but this seems like a boring example compared to whisking.

Folding is popular, but for some reason it goes by different names by different programming camps. Python programmers call it REDUCE, and Ruby programmers call it INJECT. I don't know about these names, though: I think they sound a little bit aggressive for my taste. As for me, I like the homeliness of "fold": it reminds me of the kitchen.

4 comments:

Anonymous said...

Which Scheme implementation are you using?

PJW said...

Nice examples. I found the boring examples in Graham Hutton's "A tutorial on the universality and expressiveness of fold" to be instructive as well.

A copy of the paper at least currently can be found here:
www.cs.nott.ac.uk/~gmh/fold.pdf

Anonymous said...

Actually, Smalltalk calls it inject, Ruby just lifted Smalltalk's library and object model.

Danny Yoo said...

Hi anonymous,

I'm using the "Intermediate Student" language level in DrScheme, which adds a few extra primitives like LOCAL, FIRST, and REST.

I'm doing this to make the examples more readable to people who might not know Scheme. In particular, I'm using LOCAL to avoid writing LAMBDA, which seems to trigger instinctive panic in the primitive part of my brain sometimes.

The examples in an R5RS environment would look something like this (apologies for the indentation; I don't know how to put literal code in comments well):

(define (fold folding-action a-bowl ingredients)
(cond ((null? ingredients) a-bowl)
(else
(let ((mixed-bowl (folding-action (car ingredients)
a-bowl)))
(fold folding-action mixed-bowl (cdr ingredients))))))

(define (make-pancake-batter)
(define (whisk an-ingredient a-bowl)
(string-append a-bowl an-ingredient))
(define pancake-ingredients '("flour" "sugar" "eggs" "milk"))
(define empty-bowl "")
(fold whisk empty-bowl pancake-ingredients))


(let ((whisk (lambda (an-ingredient a-bowl)
(cond ((string=? an-ingredient "eggs")
(string-append a-bowl "egg-white-only"))
(else
(string-append a-bowl an-ingredient))))))
(fold whisk "" '("flour" "eggs" "cabbage")))