Structural Induction

Perhaps the most straightforward style of computing a value over a tree is by structural induction. The result of a tree is computed as a function of the results of its subtrees. The simplest example of such a function is equality of trees. Two trees are equal if the top nodes have the same structure and all the corresponding subtrees are equal. This function is so common that it is always generated by the term processor. Only one click less trivial is the function to compute the number of leaves of a tree. An example of that functions follows. The base case of nroftips simply returns 1, and the structural induction case just adds the results of the components.  

/* A very simple tree structure */
funnytree:      Str(casestring)
|               Cons(funnytree funnytree)
;


int nroftips(funnytree $f)
{
    Str:        { return 1; }
    Cons(l, r): { return nroftips(l) + nroftips(r); }
}

In general one writes a function for every phylum that occurs in the tree.