A Scheme Code Kata, Explained (Part II)

https://logicgrimoire.files.wordpress.com/2012/04/wpid-orange-tesselation.jpg

Last time I walked you through the gather-next-batch procedure. Now let’s put it together with its caller. As I mentioned before, I was inspired by the Schemish stylings of the good Mr. Harvey to implement the ‘plist’ to ‘alist’ transformation using a higher-order procedure. gather-next-batch was that procedure.

One way I like to think about higher-order procedures is as follows: Imagine a man pushing a lawn-mower along on a beautiful Saturday morning. As he pushes the mower along, it lifts, slices, and ejects the grass that comes underneath its blade. In order for it to move along and do its work, it needs the man pushing, since the forward momentum is essential to its operation – otherwise there would be no grass underneath for it to cut!

It’s much the same with higher-order procedures: one procedure (the man) pushes another (the lawn-mower) across a data structure (the lawn). Of course, this is the simplest use case, but it’s where most of us start.

That might help you to understand how gather-next-batch works, at least in broad strokes. Coming back to our overall problem, we need to figure out how to use gather-next-batch to our advantage. We’ll call it from inside another procedure which will collect the entire ‘alist’ together, the cryptically-named p->a.

p->a will transform the given type of ‘property list’ into an ‘association list.’ Here it is:

(define (p->a p)
  (cond ((null? p) '())
        ((symbol? (car p))
         (cons (list (car p)
                     (gather-next-batch number? (cdr p)))
               (p->a (cdr p))))
        (else (p->a (cdr p)))))

Let’s walk through it. We take a property list p as our only parameter. As is usual with Scheme, we walk the list recursively, checking first for null?, and returning an empty list in that case. If the first item is a symbol, we make a new, smaller list whose first item is the first item of p and whose other items are the result of calling gather-next-batch with number? as its predicate. gather-next-batch walks the rest of p (a.k.a., (cdr p)) and return the next group of numbers.

We then take the little list we’ve made (which will look something like (a 1 2 3) ) and push it onto the result of p->a when called with all but the first element of p.

If the first element of p is not a symbol, we just call p->a on the rest of p.

That’s rather more verbose in English than in Scheme, but I was able to write the English description much more quickly than I was able to write the initial solution in Scheme. See if you can step through the Scheme code in your mind, and use the English as an aid where necessary.

Note that Scheme and Lisp, more so than some other languages, require you to read the code “from the inside out.” The heart of a procedure will return a little data structure, which you’ll then pass to another procedure, and perhaps another, etc.

In closing, let’s look at the trace of p->a printed by my lovely assistant, Scheme 48. Ain’t recursion beautiful?

> (p->a '(a 1 2 3 b 4 5 c 6 7 d e))
[Enter (p->a '(a 1 2 3 b 4 5 c ---))
[Enter (p->a '(1 2 3 b 4 5 c 6 ---))
[Enter (p->a '(2 3 b 4 5 c 6 7 ---))
[Enter (p->a '(3 b 4 5 c 6 7 d ---))
[Enter (p->a '(b 4 5 c 6 7 d e))
[Enter (p->a '(4 5 c 6 7 d e))
[Enter (p->a '(5 c 6 7 d e))
[Enter (p->a '(c 6 7 d e))
[Enter (p->a '(6 7 d e))
[Enter (p->a '(7 d e))
[Enter (p->a '(d e))
[Enter (p->a '(e))
[Enter (p->a '())
 Leave p->a '()]
 Leave p->a '((e ()))]
 Leave p->a '((d ()) (e ()))]
 Leave p->a '((d ()) (e ()))]
 Leave p->a '((d ()) (e ()))]
 Leave p->a '((c (6 7)) (d ()) (e ()))]
 Leave p->a '((c (6 7)) (d ()) (e ()))]
 Leave p->a '((c (6 7)) (d ()) (e ()))]
 Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
 Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
 Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
 Leave p->a '((b (4 5)) (c (6 7)) (d ()) (e ()))]
 Leave p->a '((a (1 2 3)) (b (4 5)) (c (6 7)) (d ()) (e ()))]
'((a (1 2 3)) (b (4 5)) (c (6 7)) (d ()) (e ()))

(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