## 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).` 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].`

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

where
• Tail is itself a list,

• and Head may be anything
(including a sequence of elements)

• and the recursion stops, of course, when we reach the empty list

- which can never match the pattern [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

• 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]):-` `member(X, Tail).`

Note:

• 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].

• either L1, say, is empty
and the result is just L2

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

Note:

• 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([], []).` `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

• 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]):-` `lt(X,H).` `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

• Sorting, which we will consider later (in Chapter 10)

• but perhaps try order_insert/3 now,
as the basis for Insertion Sort?

• 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

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

• so, use a predicate to give it a name

• for example,

`data(list_1, [a,b,c]).`

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

rather than

`?- member(X, [a, b, c]).`

This idea we shall meet again, also in Chapter 10.