Naish ([Nai96]), and various references included therein,
argued for a higher order approach to programming in Prolog,
based on similar techniques which are widely used in functional
programming. One of the key steps in this approach is to develop suitable
higher order predicates which can be used for a whole class of computations
over a particular data structure. Modern functional
languages have certain data types and higher order functions built in. For
example, the polymorphic type list(T) and higher order function
foldr
which generalises the common simple recursion used to compute a value from
a list. Program 7 demonstrates the use of foldr
using Prolog syntax in the style of (Naish, [Nai96]).
:- type list(T) ---> [] ; [T|list(T)].
foldr(F, B, [], B).
foldr(F, B, [A|As], R) :-
foldr(F, B, As, R1),
call(F, A, R1, R).
sum(As, S) :- foldr(plus, 0, As, S).
product(As, P) :- foldr(times, 1, As, P).
length(As, L) :- foldr(add1, 0, As, L).
add1(_, TailLen, Len) :- Len is TailLen + 1.
Program 7: Using foldr
In addition to the input list and result, foldr
has two other arguments.
One is the base case: what to return when the end of the list is reached.
The other is a function -- a predicate in the Prolog context. The predicate
takes the head of a list and the result of folding the tail of a list to
give the result of folding the whole list.
The call/N predicates are available as builtins or library
predicates in
several Prolog systems. The first argument (a predicate) is called with the
additional arguments added. For example, call(plus(A),R1,R) is
equivalent to plus(A,R1,R), which is true if A+R1=R.
In (Naish, [Nai96]) an alternative higher order primitive, apply/3,
is recommended due to its greater flexibility. In this
paper we simply use call/N as it is more widely known.
Examples in (Naish, [Nai96])
show how foldr can be used to compute both the sum
and product in a single pass by using a pair of numbers for the base case,
intermediate results and final answer. These higher order definitions can
be optimised very
effectively, see (Sagonas and Warren [SW95]), for example.
Further examples are given to show how predicates which are analogous to
foldr can be constructed.