Chapter 2
List Manipulation
This chapter introduces a special
notation for lists, one of the most important data structures in Prolog, and provides some
examples for how to work with them.
2.1 Notation
Lists are contained in square brackets
with the elements being separated by commas. Here’s an example:
[elephant, horse,
donkey, dog]
This is the list of the four atoms
elephant, horse, donkey, and dog. Elements of lists could be any valid Prolog terms, i.e. atoms, numbers,
variables, or compound terms. This includes
also other lists. The empty list is written as []. The following is another example for a (slightly more complex) list:
[elephant, [], X,
parent(X, tom), [a, b, c], f(22)]
Internal representation. Internally, lists are represented as compound
terms using the functor .
(dot). The empty list [] is an atom and elements are added one by one. The list
[a,b,c], for example, corresponds to the following term:
.(a, .(b, .(c,
[])))
2.2 Head and Tail
The first element of a list is called its head and the
remaining list is called the tail. An empty
list doesn’t have a head. A list just containing a
single element has a head (namely that particular single element) and its tail
is the empty list.
A variant of the list notation allows
for convenient addressing of both head and tail
of a list. This is done by using the separator | (bar). If it is put just before the last
term inside a list, it means that that last term denotes another list. The entire list is
of a list. This is done by using the separator | (bar). If it is put just before the last
term inside a list, it means that that last term denotes another list. The entire list is
15
16 Chapter
2. List Manipulation
then constructed by appending this sub-list to the list
represented by the sequence of elements
before the bar. If there is exactly one element before the bar, it is the head
and the term after the bar is the list’s tail. In the next example 1 is the
head of the list and [2,3,4,5] is the tail,
which has been computed by Prolog simply by matching the list of numbers
with the head/tail-pattern.
?- [1, 2, 3, 4, 5] = [Head | Tail]. Head = 1
Tail = [2, 3, 4, 5]
Yes
Yes
Note that Head and Tail are just names for variables. We
could have used X and Y or whatever instead with the same result. Note also
that the tail of a list (more generally speaking: the thing after |) is always
a list itself. Possibly the empty list, but definitely a list. The head, however, is an
element of a list. It could be a list as
well, but not necessarily (as you can see from the previous example — 1
is not a list). The same applies to all other elements listed before the
bar in a list.
This notation also allows us to
retrieve the, say, second element of a given list. In the
following example we use the anonymous variable for the head and also for the
list after the bar, because we are
only interested in the second element.
?- [quod, licet, jovi, non, licet, bovi]
= [_, X | _]. X = licet
Yes
The head/tail-pattern can be used to
implement predicates over lists in a very compact
and elegant way. We exemplify this by presenting an implementation of a predicate that
can be used to concatenate two lists.1 We call it concat_lists/3. When called with the
first two elements being instantiated to lists, the third argument should be matched with
the concatenation of those two lists, in other words we would like to get the following
behaviour:
and elegant way. We exemplify this by presenting an implementation of a predicate that
can be used to concatenate two lists.1 We call it concat_lists/3. When called with the
first two elements being instantiated to lists, the third argument should be matched with
the concatenation of those two lists, in other words we would like to get the following
behaviour:
?- concat_lists([1, 2, 3], [d, e, f, g],
X). X = [1, 2, 3, d,
e, f, g]
Yes
The general approach to such a problem
is a recursive one. We start with a base
case
and then write a clause to reduce a complex problem to a simpler one until the base case
is reached. For our particular problem, a suitable base case would be when one of the
two input-lists (for example the first one) is the empty list. In that case the result (the
third argument) is simply identical with the second list. This can be expressed through
the following fact:
and then write a clause to reduce a complex problem to a simpler one until the base case
is reached. For our particular problem, a suitable base case would be when one of the
two input-lists (for example the first one) is the empty list. In that case the result (the
third argument) is simply identical with the second list. This can be expressed through
the following fact:
1Note that most Prolog systems already provide such a predicate,
usually called append/3 (see Section 2.3). So you do not actually have to
implement this yourself. 
Ulle
Endriss. And Introduction to Prolog
Programming 17
concat_lists([],
List, List).
In all other cases (i.e. in all cases where a query with
concat_lists as the main functor
doesn’t match with this fact) the first list has at least one element. Hence, it can be
written as a head/tail-pattern: [Elem | List1]. If the second list is associated with
doesn’t match with this fact) the first list has at least one element. Hence, it can be
written as a head/tail-pattern: [Elem | List1]. If the second list is associated with
the variable List2, then we know that
the head of the result should be Elem and the tail
should be the concatenation of List1 and List2. Note how this simplifies our initial
problem: We take away the head of the first list and try to concatenate it with the
(unchanged) second list. If we repeat this process recursively, we will eventually end
up with an empty first list, which is exactly the base case that can be handled by the
previously implemented fact. Turning this simplification algorithm into a Prolog rule is
straightforward:
should be the concatenation of List1 and List2. Note how this simplifies our initial
problem: We take away the head of the first list and try to concatenate it with the
(unchanged) second list. If we repeat this process recursively, we will eventually end
up with an empty first list, which is exactly the base case that can be handled by the
previously implemented fact. Turning this simplification algorithm into a Prolog rule is
straightforward:
concat_lists([Elem | List1], List2,
[Elem | List3]) :-
concat_lists(List1, List2, List3).
concat_lists(List1, List2, List3).
And that’s it! The concat_lists/3 can now be used for
concatenating two given lists as
specified. But it is actually much more flexible than that. If we call it with
variables in the first two arguments and
instantiate the third one with a list, concat_lists/3 can be used to decompose that list. If you use the semicolon key to get all
alternative solutions to your query, Prolog will print out all
possibilities how the given list could be obtained
from concatenating two lists.
?- concat_lists(X,
Y, [a, b, c, d]).
X = []
Y = [a, b, c, d] ;
X = [a]
Y = [b, c, d] ;
X = [a, b]
Y = [c, d] ;
X = [a, b, c]
Y = [d] ;
Y = [d] ;
X = [a, b, c, d] Y = [] ;
No
Recall that the
No at the end means that there are no further alternative solutions.
18 Chapter 2. List Manipulation
2.3 Some Built-in Predicates for List Manipulation
Prolog comes with a range of
predefined predicates for manipulating lists. Some of the most important ones are presented
here. Note that they could all easily be implemented by exploiting the head/tail-pattern.
length/2: The second argument is matched with the length of
the list in the first argu-
ment. Example:
ment. Example:
?- length([elephant, [], [1, 2, 3, 4]],
Length). Length = 3
Yes
It is also possible to use length/2 with an uninstantiated
first argument. This will generate a list of
free variables of the specified length:
?- length(List,
3).
List = [_G248, _G251, _G254]
Yes
Yes
The names of those variables may well
be different every time you call this query, because they are generated by Prolog during
execution time.
member/2: The goal member(Elem, List)
will succeed, if the term Elem can be matched
with one of the members of the list List. Example:
with one of the members of the list List. Example:
?- member(dog, [elephant, horse, donkey,
dog, monkey]).
Yes
Yes
append/3: Concatenate two
lists. This built-in
works exactly like
the predicate
concat_lists/3 presented in Section 2.2.
concat_lists/3 presented in Section 2.2.
last/2: This predicate succeeds, if its
second argument matches the last element of the
list given as the first argument of last/2.
list given as the first argument of last/2.
reverse/2: This
predicate can be used to reverse the order of elements in a list. The first
argument has to be a (fully instantiated) list and the second one will be matched
with the reversed list. Example:
argument has to be a (fully instantiated) list and the second one will be matched
with the reversed list. Example:
?- reverse([1, 2, 3, 4, 5], X). X = [5, 4, 3, 2, 1]
Yes
select/3: Given a list in the second
argument and an element of that list in the first, this
predicate will match the third argument with the remainder of that list. Example:
predicate will match the third argument with the remainder of that list. Example:
?- select(bird, [mouse, bird, jellyfish,
zebra], X). X = [mouse,
jellyfish, zebra]
Yes
Ulle Endriss. And Introduction to Prolog Programming 19
2.4 Exercises
Exercise 2.1. Write a Prolog predicate analyse_list/1 that
takes a list as its argument and prints out the list’s head and tail on the screen. If the given list is empty, the
predicate should put out an accordant message. If the argument term isn’t a list at all, the predicate
should just fail. Examples:
?- analyse_list([dog, cat, horse, cow]).
This is the head
of your list: dog
This is the tail of your list: [cat,
horse, cow]
Yes
Yes
?-
analyse_list([]).
This is an empty list.
Yes
Yes
?- analyse_list(sigmund_freud).
No
No
Exercise 2.2. Write a Prolog predicate membership/2 that
works like the built-in predicate
member/2 (without using member/2).
Hint: This exercise, like many others,
can and should be solved using a recursive approach and the head/tail-pattern for lists.
Exercise 2.3. Implement a Prolog predicate
remove_duplicates/2 that removes all duplicate elements from a list given in the first argument and
returns the result in the second argument
position. Example:
?- remove_duplicates([a, b, a, c, d, d],
List). List = [b, a, c,
d]
Yes
Exercise 2.4. Write a Prolog predicate reverse_list/2 that
works like the built-in predicate
reverse/2 (without using reverse/2). Example:
?- reverse_list([tiger, lion, elephant, monkey],
List). List = [monkey,
elephant, lion, tiger]
Yes
Exercise 2.5. Consider the following Prolog program:
whoami([]).
whoami([]).
20 Chapter
2. List Manipulation
whoami([_, _ | Rest]) :-
whoami(Rest).
whoami(Rest).
Under what
circumstances will a goal of the form whoami(X) succeed?
Exercise 2.6. The
objective of this exercise is to implement a predicate for returning the last element of a list in two different ways.
(a) Write a predicate last1/2 that works
like the built-in predicate last/2 using a
recursion and the head/tail-pattern of lists.
recursion and the head/tail-pattern of lists.
(b) Define a similar predicate last2/2
solely in terms of append/3, without using a
recursion.
recursion.
Exercise 2.7. Write a predicate replace/4 to replace all
occurrences of a given element (second argument) by another given element (third
argument) in a given list (first argument). Example:
?- replace([1, 2, 3, 4, 3, 5, 6, 3], 3,
x, List). List = [1, 2, x,
4, x, 5, 6, x]
Yes
Exercise
2.8. Prolog lists without
duplicates can be interpreted as sets.
Write a
program that given such a list computes the corresponding power set. Recall that the
power set of a set S is the set of all subsets of S. This includes the empty set as well as
the set S itself.
program that given such a list computes the corresponding power set. Recall that the
power set of a set S is the set of all subsets of S. This includes the empty set as well as
the set S itself.
Define a predicate power/2 such that, if
the first argument is instantiated with a
list, the corresponding power set (i.e. a list of lists) is returned in the second position.
Example:
list, the corresponding power set (i.e. a list of lists) is returned in the second position.
Example:
?- power([a, b, c], P).
P = [[a, b, c], [a, b], [a, c], [a], [b,
c], [b], [c], []]
Yes
Yes
Note: The order
of the sub-lists in your result doesn’t matter.
0 comments:
Post a Comment