Module 5, part 2

Termination criteria

In the previous section we saw how it was possible to work through a list, taking the head of a list and writing it, then performing the same operation on the tail. The procedure used to implement this included two rules: one recursive and the other the terminating condition.

Terminating conditions are essential in list processing because they usually represent conditions that we are more interested in. The three patterns that we are interested in are:

Terminate when the list is empty

We've already seen an example of this in dissect_list/1. The key point is that the computation ends when the empty list ([]) is found.

Terminate when a specified element is found

Examples of this are searching for a given element in a list, either to discover it is there, or to perform some operation on it, such as replacement.

Terminate when a specific point is reached

Here, we work through lists until we have reached a specific point (irrespective of what that element is), and then perhaps perform some operation on it.

Each of the three sections include examples designed to illustrate the topic. However, the examples given aren't necessarily the ones most frequently used by expert programmers, because there are other versions that are more efficient. These are considerations that have to take into account the way that Prolog is implemented on the underlying hardware. In this sense, the previous versions are not "wrong" but less appropriate.

The topic of efficiency in list processing is taken further in discussion on the topic of accumulators.

These Pages are maintained by Dr Peter Hancox

Last updated October 1998