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.

 
[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,[])))