next up previous contents
Next: How To Glue Up: Prolog Syntax Previous: The Occurs Check

Lists Are Terms Too

If a list is a term then it must be a compound term. What, then is its principal functor? Predicates have a fixed arity but lists can be any length ---so what is the arity of the principle functor?

For the moment only, let us suppose we have a gluing agent which glues an element onto the front of a list. We know this is a reasonable supposition because we already have a list destructor/constructor that works like this.

[a,b,c,d] = [HeadTail]

---results in Head=a, Tail=[b,c,d]

We might think of this constructor as a predicate cons/2. We have to build lists like this. Note, however, that there is no built-in predicate named cons/2 ---the real name for the list constructor function is ./2!

In Prolog, the empty list is represented as []. In some implementations, the empty list is named ``nil'' ---but the Prolog you will use does not use this name.

Now to represent the lists as trees ---but we will distort them a little:

You will have noticed that we could have written cons where we have written . ---well, remember that Prolog doesn't use a meaningful name for the constructor cons/2. Really, the constructor is ./2. For (textual) explanation purposes, we shall stick to using cons/2.

Now we will show how to unpack the structure of a non-flat list. We do this by building up the structure from left to right.


goes to


goes to


goes to

now [b,c] is cons(b,[c])

that is, cons(b,cons(c,[]))


goes to


As this is difficult to read, we construct a tree using the method for drawing trees of compound terms.

Paul Brna
Mon May 24 20:14:48 BST 1999