Tag Archives: kata

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

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

A Scheme Code Kata

https://logicgrimoire.files.wordpress.com/2012/02/wpid-scheme-kata-paper-quilt.jpg

Reader beware! This is a meta-creature, a post about a post about a post. By way of comp.lang.scheme, the musings of the great jao (who incidentally is the Wizard behind Geiser (which is the way to Scheme with Emacs these days)), and finally, this humble blag, I present my (straight R^5RS!) solution to the Scheme kata described in the above links:

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

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

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