§7.0  Introduction: List Representation  §7.2  Applications of Lists  
§7.1  Standard List Predicates  §7.3  A Useful Dodge: Naming Lists 
Any Prolog structure can be thought of as a tree
parent(james_iv, margaret_tudor, james_v).
So, how might we sketch a list?
Any list has (in general)
 a recursive definition, ending in [], the empty list.
So, perhaps a list could be sketched
This is exactly Prolog's form  even to the dot functor:
.(a, .(b,. (c, []))).
Tiresome! So we introduce "syntactic sugar"
[a, b, c].
Sugar for us, not for the Prolog interpreter!
In Prolog, as in Scheme, we normally think recursively
 which can never match the pattern [Head Tail].
The HeadTail split is simply another example of the fundamental rule of programming (or of life!):
if you can't handle something, 
give it a name and pass on! 
Using this idea,
[a, b, c]
 =
 [a [b, c]]

=
 [a, b [c]]
 
=
 [a, b, c []]

Lists are the data structure for nonimperative programming,
 so let's study them in Prolog.
List membership?
X is in a list
member(X, [X Tail]).
 
member(X, [_ Tail]):
 
member(X, Tail).

Note:
Exercise: check membership of list [a,b,c].
append([], L2, L2).
 
append([H1 T1], L2, [H1 List]):
 
append(T1, L2, List).

Note:
Exercise: check with lists [a, b, c], [d, e, f].
Reversing a list?
reverse([], []).
 
reverse([H T], Rev):
 
reverse(T, T_rev),
 
append(T_rev, [H], Rev).

Reuse of code as important as ever!
member_1(X, L):  append (_, [X _], L).
Exercise: check reversal of list [a,b,c]
Three efficiency points on reverse/2
reverse([], Ans, Ans).
 
reverse([H T], So_far, Ans):
 
reverse(T, [H So_far], Ans).

reverse_2(L, Ans): reverse(L, [], Ans).
Exercise: convince yourself, about reverse/3, with the list [a,b,c]!
Insertion in ordered list?
Using the general (undefined!) lt(X,Y)
intended to be read as X is less than Y,
order_insert(X, [], [X]).
 
order_insert(X, [H T], [X, H T]):
 
lt(X,H).
 
order_insert(X, [X T], [X T]).
 
% Or result [X, X T] if you prefer!
 
order_insert(X, [HT], [HAns]):
 
lt(H, X),
 
order_insert(X, T, Ans).

Question: does clause ordering matter?
Two particular applications stand out, apart from the general utility of lists as the fundamental structure for any sequence of elements
Exercise: see practical sheet 3!
It is tedious to have to retype the same list
data(list_1, [a,b,c]).
? data(list_1, L), member(X,L).
? member(X, [a, b, c]).
This idea we shall meet again, also in Chapter 10.
© Paul Goldfinch 1997  Next Chapter  Return to 52 349 Menu 