52 349 Logic Programming

Chapter 7 - Lists: The Basic Prolog Element

§7.0 Introduction: List Representation §7.2 Applications of Lists
§7.1 Standard List Predicates §7.3 A Useful Dodge: Naming Lists

Previous Reading: Prolog - Terminology & Semantics

§7.0 Introduction

Any Prolog structure can be thought of as a tree

parent(james_iv, margaret_tudor, james_v).

Structure tree

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

List tree

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

[Head |Tail].

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.

§7.1 Standard List Predicates

List membership?

X is in a list

member(X, [X |Tail]).
member(X, [_ |Tail]):-
member(X, Tail).


Exercise: check membership of list [a,b,c].

Appending two lists?

append([], L2, L2).
append([H1 |T1], L2, [H1 |List]):-
append(T1, L2, List).


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).

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

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]):-
order_insert(X, [X |T], [X |T]).
% Or result [X, X |T] if you prefer!
order_insert(X, [H|T], [H|Ans]):-
lt(H, X),
order_insert(X, T, Ans).

Question: does clause ordering matter?

§7.2 Applications of Lists

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?

Exercise: see practical sheet 3!

§7.3 A Useful Practical Dodge

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