7 Lists
7.1 What is a list in Prolog
Lists are powerful data structures for holding and manipulating groups of things. In Prolog, a list is simply a collection of terms. The terms can be any Prolog data types,including structures and other lists.Syntactically, a list is denoted by square brackets with the terms separated by commas. For example, a list of alcohol is represented as
[Tequila,Whisky,Vodka,Martini,Muscat,Malibu,Soho,Epita]
This gives us an alternative way of representing the locations of things. Rather than having separate location predicates for each thing, we can have one location predicate per container, with a list of things in the container.
list_where([Tequila,Whisky,Vodka], bathroom).
list_where([Martini,Muscat], kitchen).
list_where([Malibu,Soho], under_the_bed).
list_where([Epita], everywhere).
The empty list is represented by a set of empty brackets []. This is equivalent to the nil in other programming language.For our example in this section, it can describe the lack of things in a place :
list_where([], cave).
The Unification works on lists just as it works on other data structure of SWI Prolog. With that, we now can ask questions about lists to prolog:
?- [_,_,X] = [lesson, work, sleeping].
X = sleeping
?- list_where(X, under_the_bed).
X = [Malibu,Soho]
Notice that there is a impractical method of getteing a list of elements in
the first example, because of Prolog won't unify unless both list have the same number of elements.
At last, the special notation for list structures.
[X | Y]
This structure is unified with a list, X is bound to the first element of the list, called the head. Y is bound to the list of remaining elements, called the tail.Note that the tail is considered as a list for Prolog and the empty list does not unify with the standart list syntax because it has no head.
Here is an example :
?- [X|Y] = [a, b, c, d, e].
X = a
Y = [b, c, d, e]
?- [X|Y] = [].
no
The empty list does not unify with the standard list syntax because it has no head.
?- [X|Y] = [].
no
This failure is important, because it is often used to test for the boundary condition in a recursive routine. That is, as long as there are elements in the list, a unification with the [X|Y] pattern will succeed. When there are no elements in the list, that unification fails, indicating that the boundary condition applies.
We can specify more than just the first element before the bar (|). In fact, the only rule is that what follows it should be a list.
?- [First, Second | Q] = [water,gin,tequila,whisky].
First = water
Second = gin
Q = [tequila,whisky]
We have said a list is a special kind of structure. In a sense it is, but in another sense it is just like any other Prolog term. The last example gives us some insight into the true nature of the list. It is really an ordinary two-argument predicate. The first argument is the head and the second is the tail. This predicate is represented by a period(.). To see this notation, we use the built-in predicate display, which writes lits in using this syntax.
?- X = [T|Q], display(X).
.(_01,_02)
From this examples it should be clear why there is a different syntax for lists. The easier syntax makes for easier reading, but sometimes obscures the behavior of the predicate. It helps to keep this "real" structure of lists in mind when working with predicates that manipulate lists. 7.2 How to manipulate list
For lists to be useful,there must be easy way to access,add, and delete list elements.Moreover, we should not have to concern ourselves about the number of list items, or their order.Two Prolog features enable us to accomplish this easy access. One is a special notation that allows reference to the first element of a list and the list of remaining elements, and the other is recursion.
These two features are very useful for coding list utility predicates, such as member, which finds members of a list, and append, which joins two lists together. List predicates all follow a similar strategy--try something with the first element of a list, then recursively repeat the process on the rest of the list.
The first one we will look at is member. As with most recursive predicates, we will start with the boundary condition, or the simple case. An element is a member of a list if it is the head of the list.
member(T,[T|Q]).
This clause also illustrates how a fact with variable arguments acts as a rule. The second clause of member is the recursive rule. It says an element is a member of a list if it is a member of the tail of the list.
member(X,[T|Q]) :- member(X,Q).
As with many Prolog predicates, member can be used in multiple ways. If the first argument is a variable, member will, on backtracking, generate all of the terms in a given list.
?- membre(X, [muscat, soho, martini]).
X = muscat;
X = soho;
X = martini;
no
Another very useful list predicate builds lists from other lists or alternatively splits lists into separate pieces. This predicate is usually called append. In this predicate the second argument is appended to the first argument to yield the third argument. For example
?- append([a,b,c],[d,e,f],X).
X = [a,b,c,d,e,f]
It is a little more difficult to follow, since the basic strategy of working from the head of the list does not fit nicely with the problem of adding something to the end of a list. append solves this problem by reducing the first list recursively. The boundary condition states that if a list X is appended to the empty list, the resulting list is also X.
append([],X,X).
The recursive condition states that if list X is appended to list [T|Q1], then the head of the new list is also H, and the tail of the new list is the result of appending X to the tail of the first list.
append([T|Q1],X,[T|Q2]) :- append(Q1,X,Q2).
Real Prolog magic is at work here, which the trace alone does not reveal. At each level, new variable bindings are built, that are unified with the variables of the previous level. Specifically, the third argument in the recursive call to append is the tail of the third argument in the head of the clause. These variable relationships are included at each step.
|
<-- Recursion
|
-
|
Others Elements of Prolog --> |