A Scheme Code Kata, Explained (Part I).

https://logicgrimoire.files.wordpress.com/2012/03/wpid-scheme-kata-2-backlit-tesselation.jpg

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s