Contents | The Lisp Editor ED | Trees and Recursion

Lists as Trees

There is a way of thinking about recursive functions that may help to clarify the method. This brief chapter will try to explain the simple Lisp functions in terms of trees. We will then use the tree representation in later chapters to describe the action of recursive functions.

A useful way to see what a deeply embedded list looks like is to think of it as a tree. A tree, as the name implies, is a structure with a root, branches and leaves. This is a tree.

picture representation of ((Mary had a) (little (lambda)))

The above tree is the representation of the list
((Mary had a) (little (lambda)))
Each node of the tree indicates the starting point of a pair of elements. The root [first node] indicates the starting point of the main list. The leaves of the tree are the atoms in the list.

Notice that each node of the tree branches two ways. This type of tree is called a binary tree because of the two way branching.

Let's take a look at a simpler tree.

(a list)

(a list) tree representation
This tree has two nodes and four branches. There are atoms at the ends of the lowest branches [NIL is an atom too!].
(new stuff)

(new stuff) tree representation
It looks the same. Now, let's insert the second tree into the first, replacing "(new stuff)" for "a". The resulting tree looks like the following diagram.
((new stuff) list)

((new stuff) list) tree representation
When we look at the CAR of the above tree we are looking at
(new stuff)
CAR can be thought of as returning all the material hanging on the left branch. CDR, as you might expect, returns the material on the right branch.

(list) representation
This is why there are still a set of parentheses around it. Note that all the trees eventually terminate in NIL ["()"]. Recall that if you keep taking the CDR of a list you will eventually hit a NIL. The reason for this should now be apparent. If we were to insert a NIL into the end of the list, we would get:
((new stuff) list ())

((new stuff) list ()) representation
This is the CDR of the above list.
(list ())

(list ()) representation
The CDR of that is

(()) representation
CAR of that is
()   [that is: NIL]

So is CDR.

Both the CAR and CDR of NIL are NIL. Thus, we can't change the list from here on without CONSing stuff onto it. Let's do so now.

(setq worktree ())

(setq worktree (cons 'stuff worktree))

(setq worktree (cons 'stuff worktree)) representation
(setq worktree (cons '(more) worktree))

(setq worktree (cons '(more) worktree)) representation
You should be able to draw and analyze the functions of CONC and various other simple Lisp functions.

Contents | The Lisp Editor ED | Trees and Recursion