§7.0 Introduction

Any Prolog structure can be thought of as a tree

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:

Tiresome! So we introduce "syntactic sugar"

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

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!):

Using this idea,

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

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

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.

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

Re-use of code as important as ever!

• How about:

Exercise: check reversal of list [a,b,c]

Three efficiency points on reverse/2

• for lists of length n, the procedure requires O(n²) operations,

• we can better this (a standard Prolog trick) through an extra parameter,
  in this case obtaining an O(n) procedure:

which we could call through

• 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,

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

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,

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

rather than

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