9.2.2 Lists as terms

Lists are another good example where Prolog works with one internal representation, and gives us another more user friendly notation to work with. Let's start with a quick look at the user friendly notation (that is, the use of the square bracket [ and ]). In fact, because Prolog also offers the | constructor, there are are many ways of writing the same list, even at the user friendly level:

?- [a,b,c,d] == [a |[b,c,d]].
yes
 
?- [a,b,c,d] == [a,b |[c,d]].
yes
 
?- [a,b,c,d] == [a,b,c |[d]].
yes
 
?- [a,b,c,d] == [a,b,c,d |[]].  
yes

But how does Prolog view lists? In fact, Prolog sees lists as terms which are built out of two special terms, namely [], which represents the empty list, and ., a functor of arity 2 which is used to build non-empty list (the terms [] and . are called list constructors).

Here's how these constructors are used to build lists. Needless to say, the definition is recursive:

• The empty list is the term []. The empty list has length 0.

• A non-empty list is any term of the form .(term,list), where term can be any Prolog term, and list is any list. If list has length , then .(term,list) has length .

?- .(a,[]) == [a].
yes
 
?- .(f(d,e),[]) == [f(d,e)].
yes
 
?- .(a,.(b,[])) == [a,b].
yes
 
?- .(a,.(b,.(f(d,e),[]))) == [a,b,f(d,e)].
yes
 
?- .(.(a,[]),[]) == [[a]].
yes
 
?- .(.(.(a,[]),[]),[]) == [[[a]]].
yes
 
?- .(.(a,.(b,[])),[]) == [[a,b]].
yes
 
?- .(.(a,.(b,[])),.(c,[])) == [[a,b],c].
yes
 
?- .(.(a,[]),.(b,.(c,[]))) == [[a],b,c].
yes
 
?- .(.(a,[]),.(.(b,.(c,[])),[])) == [[a],[b,c]].
yes

Again, it is clear that Prolog's internal notation for lists is not as user friendly as the use of the square bracket notation. But actually, it's not as bad as it seems at first sight. It is very similar to the | notation. It represents a list in two parts: its first element or head, and a list representing the rest of the list. The trick is to read these terms as trees. The internal nodes of this tree are labeled with . and all have two daughter nodes. The subtree under the left daughter is representing the first element of the list and the subtree under the right daughter the rest of the list. So, the tree representation of .(a,.(.(b,.(c,[])),.(d,[]))), i.e. [a, [b,c], d], looks like this:

One final remark. Prolog is very polite. Not only are you free to talk to it in your own user friendly notation, it will reply in the same way.

?- .(f(d,e),[]) = Y.
 
Y = [f(d,e)]  
yes
 
 
?- .(a,.(b,[])) = X, Z= .(.(c,[]),[]), W = [1,2,X,Z].
 
X = [a,b]  
Z = [[c]]  
W = [1,2,[a,b],[[c]]]  
yes