Prolog Tutorial 6: Introducing Lists

James Power, 1997.


We have already met structures; lists are Prolog's other built-in data type.


Format of Lists

A list is simply an ordered, extendable sequence of terms; they correspond (roughly) to vectors in C++/Java.

Remember that lists, like anything else which represents objects in Prolog, are terms. Thus we don't need to "declare" them, we just use them when needed.

We write a list in Prolog using the brackets "[" and "]", and separate the elements by commas. As with any term, they must only appear in a clause as arguments to a predicate.

Thus [john, mary, pat] is a list with three elements.

List elements do not all have to look the same: ['string', 6, mary, X] is also a valid list. In fact, a list element may be any kind of term: that is, a constant, variable, structure, or even another list.

Empty and Non-Empty Lists

There is one special unique list in Prolog called the empty list, written "[ ]". This is the list which contains no elements.

Every non-empty list can be separated into two parts:

Thus:
The head of [john, mary, pat] is john
The tail of [john, mary, pat] is [mary, pat].

It is not valid to try and get the head or tail of the empty list.

In Prolog we have a special notation just for dividing up lists:

Thus the list [john, mary, pat] can also be written as [john | [mary,pat]].

Since [mary, pat] is also a list with head mary and tail [pat] (a one-element list), we can also write the above list as: [john | [mary | [pat]]]

Any one-element list can be written as that element joined to the empty list; thus [pat] is the same as [pat | []], and so we can write the full list as: [john | [mary | [pat | []]]]

This type of division is used in predicates which process lists; these take advantage of the unification rules for lists:

As a consequence of these rules, we note that [] can never be the same as a list of the form [H|T] (for any element H and list T).


Some Examples

Almost all predicates which use lists are recursive; they are defined for:

The length of a list

Suppose we wanted to write a predicate size(L,N) meaning "the size of list L is N" (by size we mean the number of elements it contains).

The size of the list is exactly equal to the number of times we can perform the head/tail division before we get the empty list.

We can write:

  % size(List,N) is true if List has N elements
  size([],0).
  size([H|T],N) :- size(T,N1), N is N1+1.

To paraphrase:

Type in this definition, and try it on some examples...


Summing a list

Suppose we know that a list contains only numbers; we should then be able to write a predicate that will get the sum of those numbers...

This will be a little like the size/2 predicate, except now at each stage we want to add in the current element to the total. Thus we write:

  % sumlist(List, N) is true if the elements of List sum to N
  sumlist([],0).
  sumlist([H|T],N) :- sumlist(T,N1), N is N1+H.


List Membership

Similarly we can define the predicate contains(X,L) which is true if X is an element of the list L.

We observe that X is contained in L if

Thus we write:
  % contains(Elem, List) is true if List contains Elem
  contains(X,[X|_]).
  contains(X,[_|T]) :- contains(X,T).

In other words:

Note that we did not have to define a predicate for the case where the list was empty, because this case could never be true. (That is, contains will fail if the list is empty).

Type in the contains predicate, and try entering the following queries:


Exercises

Let L be any list of terms. Define Prolog predicates for the following:
  1. average(L,N) is true if N is the average of all the numbers in L, or just 0 if the sum is 0
  2. sumpos(L,N) is true if N is the sum of all the positive numbers in L
  3. sumsquare(L,N) is true if N is the sum of the squares of all the numbers in L
  4. maxlist(L,N) is true if N is the largest element in the list L.
  5. maxpos(L,N) is true if N is the position of the largest element in the list L. (If there's more than one occurrence of the maximum, then this should be the first position at which it appears.)
  6. final(L,E) is true if E is the final element in L
  7. evenpos(L) which prints out the elements of L at positions 2,4,6... up to the end of the list (Use write/1 to print out the elements.)


Written by James Power
Released under the GNU Free Documentation License
Last revised: 22 Oct 2006