$ cat /home/buntine/mind_melting_brilliance

This is the second article in a two (maybe three) part series on tree data structures in Scheme. See the "representation article", also.

Previously, I've spoken about one way of representing a tree data structure in Scheme. This time, I'll talk about a simple algorithm for parsing such a structure, which uses a technique called mutual recursion.

Wikipedia defines mutual recursion as "a form of recursion where two mathematical or computational functions are defined in terms of each other". This is an appropriate explanation for our case, as we'll have two procedures which rely upon each other to produce a single result.

The first procedure will extract the child nodes from a tree structure. The second procedure will accept those children, a list of trees, and extract and parse each one. This process is performed recursively.

As an example, lets write an accumulative procedure that consumes a tree and returns a number representing the amount of parent nodes (that is, nodes which contain further children):

; Using the tree we created in the first article
> (count-parents family-tree)
  3

We can define this as follows:

(define (leaf? node)
  (null? (cdr node)))

(define (count-parents tree)
  (if (leaf? tree)
    0
    (+ 1 (count-parents-in-trees (cdr tree)))))

(define (count-parents-in-trees trees)
  (if (null? trees)
    0
    (+ (count-parents (car trees))
       (count-parents-in-trees (cdr trees)))))

It works by allowing the two procedures to only deal with the information they need. count-parents deals with trees, whilst count-parents-in-trees deals with a list of trees. leaf? is just a simple helper. Each branch of each tree is searched downwards until we reach a dead-end - a node with no children.

The recursive pattern in count-parents-in-trees should be fairly familiar. Basically, we take the first element (car) for inspection, and recurse with the remaining elements (cdr). Because of this, our base-case is the empty list, at which point we've hit every node in the branch and should have our result.

This general pattern can be applied to many tasks involving trees, from representing them graphically to mutating their structure. For example, to write a procedure that takes a tree and returns a new tree without the leaf nodes, all we need to do is use mutual recursion to build up a copy of the tree in question and ignore every leaf node.