Previous Table of Contents Next


6.2.5. Lists

The terms we have looked at so far have been just constants and variables. Now let’s look at another class of terms, the list terms, and the equalities that hold over them.

[a,b,c] is a Prolog term that stands for the list of elements a, b, and c in that order. There can be as many or as few elements in a list as we want; for instance, [a] is a list, and [] is a list. This last list is referred to as the empty list. We can give variables as list elements too, intermixed with constants if we want, such as [a,X,b,Y]. We can put spaces before and after the commas if we want, but inside terms, it is traditional to leave out the spaces.

This comma-separated-sequence notation is really just a convenience. The underlying representation of a non-empty list in Prolog, as in Lisp, is a pair consisting of a term (the head of the list) and a list (the tail of the larger list). The list of one element [a] is thus seen as the list with head a and tail []. The expression [H|T] is also a valid term and refers to the list with head H and tail T. The terms [a|[]] and [a] are just two ways of writing the same term, and in fact the query [a|[]] = [a] returns yes.

Let’s look at some other equality queries involving lists:

   [X,Y,c] = [a,b,Z].  % Query 1
   [Hd|Tl] = [a].      % Query 2
   [Hd|Tl] = [b,c,X].  % Query 3
   [a,b,c] = [X,b,X].  % Query 4
   [a,b,a] = [X,b,X].  % Query 5

The first query returns the substitution X=a, Y=b, Z=c because that is the only substitution which makes the lists identical. The second yields Hd=a, Tl=[] because that substitution makes the left-hand term into [a|[]], which as we have seen previously is identical to [a]. Similarly, Query 3 yields Hd=b, Tl=[c, X]; note that here, we have not put any constraint on the value of X at all. The fourth query returns no because no substitution for X makes the two lists identical, but the fifth query returns X = a.

There is a form of list that generalizes both the comma-style lists and the bar-style lists. The expression [a,b,c|X] denotes the list beginning with a, b, and c, whose tail after those first three elements is X. In practice, this mixed comma-and-bar style of list comes up fairly seldom but is useful occasionally.

Thus the full BNF for a list term is as follows:

   <list-term>     ::= “[“ [<list-contents>] “]”
   <list-contents> ::= <term> [<rest-of-list>]
   <rest-of-list>  ::= “,” <term> <rest-of-list>
                  |“|” <term>

List terms can be used anywhere any other terms can be used. They constitute the basic data structure of Prolog programs and are used in just about every application.

6.2.6. Predicates on Lists

Lists are recursive data structures, in the sense that the tail of a list is also a list. Recursive predicates are therefore the natural things to use on them. This section explores some simple recursive list predicates.

6.2.6.1. member

Consider the following predicate definition1:


1This definition may lead to “singleton variable” warnings on some Prologs; we can ignore these warnings for now.
   % member(List, X):  X is a member of List.
   member(List, X) :-
    List = [Head|Tail],
    X = Head.
   me0mber(List, X) :-
    List = [Head|Tail],
    member(Tail, X).

Here we are using equality goals in the bodies of clauses in order to express what we want. (Soon we will see a much simpler version of this predicate that does not use equalities.) The first clause can be read as “X is a member of List if List consists of a Head and a Tail (that is, if List is not the empty list) and X is the head.” The second clause can be read as “X is a member of List if List consists of a Head and a Tail and X is a member of the tail.”

When you think about it, those are the only two cases in which we would normally consider an element to be a member of a list, so the predicate definition is correct and complete. If Prolog is given this definition, it correctly tells us that member([a, b, c], b), and the query member([faith, hope, charity], X) returns three possible solutions for X. Note that this member predicate can be used not only to confirm that something is a member of a list, but also to generate all the members of the list.

6.2.6.2. append

Now let’s consider a definition of a predicate version of the traditional append function. In functional languages, append is a function that takes two lists as arguments and returns a list (which is the two lists appended into a single list). In Prolog, where we are defining relations, it is a predicate that takes three lists: append(List1, List2, Result) means that the result of appending List1 to List2 is Result. As in functional programming, the key question is whether the first list is empty or not. The clause

   append(List1, List2, Result) :-
    List1 = [],
    Result = List2.

can be read as follows: “The result of appending List1 and List2 is Result if List1 is empty, and Result is just List2.”

The clause

   append(List1, List2, Result) :-
    List1 = [H|T],
    append(T, List2, Temp),
    Result = [H|Temp].

can be read as follows: “The result of appending List1 and List2 is Result if List1 consists of a head H and a tail T; the result of appending T and List2 is Temp; and Result is the list with head H and tail Temp.”

The two clauses of the whole definition have the effect of the Lisp-style definition

  (defun (append list1 list2)
    (cond ((null list1) list2)
         (t (cons (car list1) (append (cdr list1) list2)))))

However, because this is Prolog and we can use any pattern of variables and constants in queries, we can ask not only append([a, b], [c, d], R) and get R = [a, b, c, d], but we can also ask append([a, b], L2, [a, b, c, d]) and get L2 = [c, d]. In essence, we can “run the predicate backward” in a way that we cannot do with the function.


Previous Table of Contents Next