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