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.

As this is difficult to read, we construct a tree using the method for drawing trees of compound terms.[a,[b,c],d]goes to

cons(a,[[b,c],d])

goes to

cons(a,cons([b,c],[d])

goes to

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

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

cons(a,cons(cons(b,cons(c,[])),[d])

goes to

cons(a,cons(cons(b,cons(c,[])),cons(d,[])))

Mon May 24 20:14:48 BST 1999