Composition of Recursive Programs Iteration Lists are the basic data structure used in logic and functional programming. Lists are a recursive data structure so recursion occurs naturally in the definitions of various list operations. When defining operations on recursive data structures, the definition most often naturally follows the recursive definition of the data structure.
In the case of lists, the empty list is the base case. So operations on lists must consider the empty list as a case. The other cases involve a list which is composed of an element and a list. Here is a recursive definition of the list data structure as found in Prolog. One rule for the empty list the base case and a second rule for non empty lists. For example, here is the definition of the predicate for the length of a list. Element of a list.
Prefix of a list. Suffix of a list. Append concatenate two lists. Compare this code with the code for plus. Here are some simple examples of common list operations defined by pattern matching. The first sums the elements of a list and the second forms the product of the elements of a list.
Another example common list operation is that of appending or the concatenation of two lists to form a third list. In Prolog, an inductive style definition is required.
The first rule is the base case. The second rule is the inductive case. The append relation is quite flexible. It can be used to determine if an object is an element of a list, if a list is a prefix of a list and if a list is a suffix of a list. The member relation can be used to derive other useful relations. A predicate defining a list and its reversal can be defined using pattern matching and the append relation as follows.
To conclude this section, here is a definition of insertion sort. Iteration Recursion is the only iterative method available in Prolog. However, tail recursion can often be implemented as iteration. Note that the second argument functions as an accumulator. The accumulator is used to store the partial product much as might be done is a procedural language.
For example, in Pascal an iterative factorial function might be written as follows. The Prolog solution also illustrates the fact that Prolog permits different relations to be defined by the same name provided the number of arguments is different.
As an additional example of the use of accumulators, here is an iterative tail recursive version of the Fibonacci function.
Iterators, Generators and Backtracking The following fact and rule can be used to generate the natural numbers. The successive numbers are generated by backtracking. For example, when the following query is executed successive natural numbers are printed.
The first natural number is generated and printed, then fail forces backtracking to occur and the second rule is used to generate the successive natural numbers.
The following code generates successive prefixes of an infinite list beginning with N. As a final example, here is the code for generating successive prefixes of the list of prime numbers. Occasionally, backtracking and multiple answers are annoying. Prolog provides the cut symbol! The following code defines a predicate where the third argument is the maximum of the first two.
The code may be simplified by dropping the conditions on the second rule. However, in the presence of backtracking, incorrect answers can result as is shown here. Now the erroneous answer will not be generated. A word of caution: In general the use of cuts should be avoided.
Tuples or Records We illustrate the data type of tuples with the code for the abstract data type of a binary search tree. Here is the Prolog code for the creation of an empty tree, insertion of an element into the tree, and an in-order traversal of the tree.
The membership relation is a trivial modification of the insert relation. Since Prolog access to the elements of a tuple are by pattern matching, a variety of patterns can be employed to represent the tree. Here are some alternatives.