A little while ago I dumped some Scheme code on you, without much in the way of context. Unless you clicked on those delicious links and spent time poring over the information therein, what I posted might not have made much sense. I intend to rectify that sad situation with this little post.

(BTW: If you want this code, it’s available at github, as is the entire source of this blog. Though I heartily recommend that you type it in for yourself, since that will probably force you to pay slightly closer attention to it. And attention is the name of the game, I think.)

I’ll begin by restating the problem in my own words. Suppose you are given a regular Lisp list of the form

(a 1 2 3 b 4 5 c 6 d e).

Write code that will convert said list into a so-called “association list.” This is a very ancient Lisp structure that serves a function similar to a primitive hash table (though much, much slower).

((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e ()))

This will allow us to get at the “values” associated with each symbol using the `assoc`

procedure. In this case:

scheme@(guile-user)> (assoc 'b (plist->alist foo)) $397 = (b (3 4))

After wrestling with a few of my own failed solutions, I came across one by Brian Harvey in the comp.lang.scheme discussion surrounding this problem. He used a couple of higher-order procedures, as I recall. I didn’t fully grok his particular solution; I decided that I could write something a bit more concise.

His solution did inspire me to separate the act of gathering the next batch of non-symbols from the act of creating the alist.

Here I’ll define a procedure, `gather-next-batch`

, which accepts two arguments: a predicate procedure and a sequence. The predicate will tell `gather-next-batch`

what, exactly, to gather the next batch *of*:

(define (gather-next-batch pred seq) (cond ((null? seq) '()) ((pred (car seq)) (cons (car seq) (gather-next-batch pred (cdr seq)))) (else '())))

You can see that this is a pretty bog-standard recursive Scheme procedure. Let’s walk through it together. First, we test if our sequence `seq`

is `null?`

, or empty. If not, we check the first element of `seq`

(a.k.a. `(car seq)`

) against our `pred`

, or predicate procedure, which will return true or false. If `pred`

looks at `(car seq)`

and returns `#t`

, then we `cons`

the aforementioned first element of `seq`

onto a list created by recursively calling `gather-next-batch`

on what’s left of `seq`

, namely, all but the first element, which we’ve just processed.

(If you’re looking for a set of rules/patterns on how to write nice little recursive procedures like this, I can highly recommend a tome of great power known as The Little Schemer. Or should I say: a tome that deposits one, slightly bewildered, at the outer gateways of great power! But I digress…)

Let’s test out our awesome new procedure:

scheme@(guile-user)> (gather-next-batch number? '(a 1 2 3 b 4 5 c 6 d e)) $404 = ()

What happened? I was expecting to get back `(1 2 3)`

! Well, as it turns out the first element of the list we passed to `gather-next-batch`

didn’t match our supplied `number?`

predicate. Therefore, we crashed through our conditional to the bottom (where `else`

lives), and in this case we asked `else`

to return the empty list, `()`

. And so it did!

Let’s try this again, using a list whose first element matches our predicate:

scheme@(guile-user)> (gather-next-batch number? (cdr '(a 1 2 3 b 4 5 c 6 d e))) $403 = (1 2 3)

In this case we asked for the `cdr`

of our list, which does begin with a number. Therefore `gather-next-batch`

was able to get going on its work of gathering up a list containing the next batch of numbers, `(1 2 3)`

.

Next time we’ll look at how to integrate this procedure with our larger solution. For now I’ll leave you with the trace output of `gather-next-sequence`

(helpfully drawn for us by Scheme 48). It should help visualize what this little procedure’s actually doing.

Until then, may you hack gracefully, friends!

> (gather-next-batch number? (cdr foo)) '(1 2 3) > ,trace gather-next-batch > (gather-next-batch number? (cdr foo)) [Enter (gather-next-batch #{Procedure 585 number?} '(1 2 3 b 4 5 c 6 ---)) [Enter (gather-next-batch #{Procedure 585 number?} '(2 3 b 4 5 c 6 d ---)) [Enter (gather-next-batch #{Procedure 585 number?} '(3 b 4 5 c 6 d e)) [Enter (gather-next-batch #{Procedure 585 number?} '(b 4 5 c 6 d e)) Leave gather-next-batch '()] Leave gather-next-batch '(3)] Leave gather-next-batch '(2 3)] Leave gather-next-batch '(1 2 3)] '(1 2 3)

(Image courtesy Mélisande* under Creative Commons license.)