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:
- the head, which is the first element
- the tail, which is the list containing all the other elements
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:
- [Hd | Tl] denotes the list whose head is Hd and whose
tail is (the list) Tl.
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:
- The only term that unifies with [] is []
- A list of the form [H1|T1] will only unify with a list
of the form [H2|T2], and then only if H1 unifies
with H2 and T1 unifies with T2
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 base case: the empty list []
- The recursive case: for a list of the form [H|T],
perform some action on the head H, then call
the predicate recursively with the tail T
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:
- The size of the empty list is 0.
- The size of the list whose head is H and whose tail is
the list T is: 1 + (the size of T).
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
- X is the head of L, or
- X is in the tail of L.
Thus we write:
% contains(Elem, List) is true if List contains Elem
contains(X,[X|_]).
contains(X,[_|T]) :- contains(X,T).
In other words:
- X is a member if the list whose head-element is
X (and whose tail is anything).
- X is a member of the list whose head is anything and
whose tail is T if X is a member of T.
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:
- contains(2, [1,2,3])
- contains(E, [1,2,3])
- contains(E, [2,1,2])
- contains(E, [])
Exercises
Let L be any list of terms. Define Prolog predicates for the
following:
- average(L,N) is true if N is the average of all the
numbers in L, or just 0 if the sum is 0
- sumpos(L,N) is true if N is the sum of all the
positive numbers in L
- sumsquare(L,N) is true if N is the sum of the
squares of all the numbers in L
- maxlist(L,N) is true if N is the largest
element in the list L.
- 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.)
- final(L,E) is true if E is the final element in
L
- 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