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]As this is difficult to read, we construct a tree using the method for drawing trees of compound terms.
now [b,c] is cons(b,[c])
that is, cons(b,cons(c,))