# A Scheme Code Kata, Explained (Part I).

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.)