The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. Indeed, this is suggested by the form in which the result is printed by the interpreter. Figure shows the representation of this structure in terms of pairs. Another way to think of sequences whose elements are sequences is as trees . The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
Figure shows the structure in figure viewed as a tree.
Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree. Length of the empty list is 0. Count-leaves is similar. But in the reduction step, where we strip off the car of the list, we must take into account that the car may itself be a tree whose leaves we need to count. A binary mobile consists of two branches, a left branch and a right branch.