52 349 Logic Programming
Chapter 7 - Lists: The Basic Prolog Element
||Introduction: List Representation
||Applications of Lists
||Standard List Predicates
||A Useful Dodge: Naming Lists
Prolog - Terminology & Semantics
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)
- the current element
- followed by all other elements
- a recursive definition, ending in , the empty list.
So, perhaps a list could be sketched
- as a binary tree
- with some unspecified functor "." at the internal nodes?
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
- for a list this means
- thinking what to do with the head (or first) element
- then handling the tail (the rest of the list) recursively
- for which we have more syntactic sugar
The Head-Tail 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 non-imperative programming,
- so let's study them in Prolog.
X is in a list
- if X is the head of the list
- or if X is in the tail of the list
member(X, [X |Tail]).
member(X, [_ |Tail]):-
- in first clause,
why bother to introduce a Head and check for equality?
- in second clause,
the anonymous variable is easier than Head!
Exercise: check membership of list [a,b,c].
Appending two lists?
- either L1, say, is empty
and the result is just L2
- or L1 had head H1 (and tail T1)
and the result is some list (from T1 and L2) with head H1.
append(, L2, L2).
append([H1 |T1], L2, [H1 |List]):-
append(T1, L2, List).
- as in member/2, we can capitalize on the fact that
we're pattern matching - Prolog style!
Exercise: check with lists [a, b, c], [d, e, f].
Reversing a list?
- an empty list is its own reverse
- the reverse of a non-empty list is
- the reverse of the tail
- with the original head appended at the rear
reverse([H |T], Rev):-
append(T_rev, [H], Rev).
Re-use 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
- for lists of length n, the procedure requires O(n2) operations,
- we can better this (a standard Prolog trick) through an extra parameter,
in this case obtaining an O(n) procedure:
reverse(, Ans, Ans).
reverse([H |T], So_far, Ans):-
reverse(T, [H |So_far], Ans).
which we could call through
reverse_2(L, Ans):- reverse(L, , Ans).
- first clause is vital, for each of the procedures;
- but, despite normal procedural rules,
it can usefully be placed second
- after all, it's only wanted once!
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]):-
order_insert(X, [X |T], [X |T]).
% Or result [X, X |T] if you prefer!
order_insert(X, [H|T], [H|Ans]):-
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
Question: why, for both set points?
- Sorting, which we will consider later (in Chapter 10)
- but perhaps try order_insert/3 now,
as the basis for
- or, for the more adventurous, use append/3
as the final part of Quick Sort?
- Sets are also useful
- best regarded as ordered lists of elements
- in each of which an element may occur at most once
Exercise: see practical sheet 3!
It is tedious to have to retype the same list
- so, use a predicate to give it a name
- for example,
- all that "data" does, is to link the atom list_1 to the list [a,b,c]
- then, also consult the file containing data (or, in due course, use "assert")
- now, use (for example)
?- data(list_1, L), member(X,L).
?- member(X, [a, b, c]).
This idea we shall meet again, also in Chapter 10.