Download Introduction to Prolog Programming

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
15