So far the only data structures that we have introduced are
functor/argument structures (or operator/argument structures).
These tend to be a little inflexible for many applications.
We want to have some list or set of items that we can add items
to or remove items from as we wish. List structures are what we
need
.
Valid prolog list structures include:
[1, 2, 3] [alison, richard] [1, 2, 3, "go"] [1+2, [alison], widget(handle(2))] [name=widget21, size=22, colour=blue] [alison, [[david, [[harold], [ida]]], [kathleen, [[john]]]]] [] (empty list)
Some of these are a bit silly. It is hard to think of a context where lists like the fourth would be useful, and the last list might be better represented as a conventional Prolog functor/argument tree structure, such as:
person(name(alison), parents(person(name(david), parents(...)), person(..)))
However, in general a Prolog list may consist of arbitrary Prolog terms, including lists.
As in functional languages, we can select the head and tail of a list through matching. In Prolog the special pattern [V1|V2] matches a list with head matching V1 and tail matching V2:
?- [H|T] = [1,2,3,4]. H = 1 T = [2,3,4] ?- [alison|Rest] = [Person, richard, alan, jeff]. Person = alison Rest = [richard, alan, jeff] ?- [person(X)|Rest] = [person(fred), person(joe)] X = fred Rest = [person(joe)] ?- [H|T] = [a] H = a T = [] ?- [H|T] = [] no ?- [a,b|C] = [a,b,c,d] C = [c,d] ?- [a,b|[c|D]] = [a,b,c,d] D = [d]
From the last two examples, note that patterns involving ``|'' need not be simple [Head|Tail] patterns - The ``|'' can follow several items, and occur within a sublist. The bit after the ``|'' should always match the rest of the list.
We can now start writing some list processing predicates. Suppose we want to write a predicate member, to find out if an item is in a given list. An item is a member of a list if it's the head of the list, or if it's a member of the tail of the list, so:
member(Item, [Item|_]). % It's a member if it matches the head.
member(Item, [_|Tail]) :-
member(Item, Tail). % or if it's a member of the tail.
Note the use of the unnamed variable ``_''. It is convenient (and good style) to use this variable name for things we don't care about.
We can use our member predicate to check if something is a member of a list, to ``generate'' members of a list, or even (if we really want to) to generate lists which have it as a member:
?- member(a, [b, a, c]). yes ?- member(I, [b, a, c]). I = b ; I = a ; I = c ; no ?- member(a, L). L = [a|_16] ; L = [_15,a|_20] ; L = [_15,_19,a|_24] yes
Think about how Prolog backtracks to get different solutions.
Member doesn't just work on ``simple'' lists. They can be lists consisting of complex terms. It will in fact succeed if the first argument MATCHES an item in the list given in the second argument (not just if they are identical). Most Prolog predicates are like this - they check if things MATCH, not if things are the same, and the result of the matching is that some variables are BOUND.
?- member(book(tolkien, X), [book(cawsey, explanation), book(tolkien, lord_of_rings)]). X = lord_of_rings ?- member(book(X, Y), [book(cawsey, explanation), book(tolkien, lord_of_rings)]). X = cawsey Y = explanation; X = tolkien Y = lord_of_rings
Another useful predicate is append:
append([], List, List).
append([H|T], List, [H|New]) :-
append(T, List, New).
An empty list appended to list is just that list. Two lists appended together consist of a new list with head the head of the first list, and tail the result of appending the tail of the first list to the second. A traced example gives:
?- append([1,2], [3], L).
(1) 1 call: append([1,2],[3],_9) ?
(2) 2 call: append([2],[3],_27) ?
(3) 3 call: append([],[3],_34) ?
(3) 3 exit: append([],[3],[3])
(2) 2 exit: append([2],[3],[2,3])
(1) 1 exit: append([1,2],[3],[1,2,3])
L = [1,2,3]
For recursive list processing predicates such as member and append the basic strategy is to write a base case that solves some simple version of the problem, and a recursive case that remains true, and where each recursive call tends more towards the base case. In append, the structure to be returned is built up in the head of the clause ([H|New]). (This can be a bit difficult to follow.)
Anothe common strategy when writing list processing predicates is to use an extra variable to hold some ``result so far''. An obvious example is a predicate to find the maximum value of some list:
max([], MaxSoFar, MaxSoFar).
max([Number|Rest], MaxSoFar, Max) :-
Number > MaxSoFar,
max(Rest, Number, Max).
max([Number|Rest], MaxSoFar, Max) :-
Number =< MaxSoFar,
max(Rest, MaxSoFar, Max).
This could be called with something like:
?- max([1,6,23,21], 0, Max).
(assuming the numbers in the list were guaranteed greater than 0).
For predicates like these it is probably easier to give a more procedural account of what is happening (which isn't so different to what happens in, say, a Pascal program). To find the maximum of a list, given a maximum value so far, if the next element is bigger than the max so far then make that the new max so far, and try the remaining elements. If its not bigger just go on to the next element of the list. When you get to the end of the list then the max so far will be the maximum value of the whole list.
Some further example list processing predicates are given below. Try working out how they work:
% reverse(+List,+SoFar,-ReversedList)
% Should succeed with ReversedList bound to reversed List (appended to
% initial value of SoFar). Normally called with SoFar=[]/
reverse([], SoFar, SoFar).
reverse([H|T], SoFar, Final) :-
reverse(T, [H|SoFar], Final).
% delete(+Item, +List, ?NewList)
% Should succeed with NewList bound to List but with all items matching
% Item removed.
delete(_, [], []).
delete(Item, [Item|Rest], NewRest) :-
delete(Item, Rest, NewRest).
delete(Item, [First|Rest], [First|NewRest]) :-
not First = Item,
delete(Item, Rest, NewRest).
% replace(+Item, +NewItem, +List, -NewList)
% Should succeed with NewList bound to List but with all items
% matching Item replaced by NewItem
replace(_,_,[],[]).
replace(Item, New, [Item|Rest], [New|NewRest]) :-
replace(Item, New, Rest, NewRest).
replace(Item, New, [First|Rest], [Item|NewRest]) :-
not First = Item,
replace(Item, New, Rest, NewRest).
Note the use of ``not'' to check if something is NOT true. In some Prologs you have to use \+ in place of not. The reason is that it is not a real logical not - Prolog just checks to see if it can prove something, and if it can't ``not'' succeeds (it means ``I'm not sure but I can't prove it''). Some Prologs don't like using ``not'' to represent this lesser notion (referred to as ``negation as failure'').