Recent work on shape (Jay and Cockett, [JC94]), (Jay, [Jay95]),
(Bellé et al., [BJM96]) and
polytypism (Jeuring and Jansson, [JJ96]),
(Jansson and Jeuring, [JJ96])
has formalised the notion that many data types
have certain higher order functions naturally associated with them. For
example, map/3 takes a list and produces another list of the same
length. The shape of the output, the list structure, is the same as the
shape of the input and the elements of the lists are related by the function
map/3 applies. The idea of map/3 can be applied to
any algebraic type such as lists and trees, and also arrays and matrices.
A generic version of map/3
applied to a binary tree will produce a binary tree of the same shape where
the elements of the trees are related by the function map/3 applies.
Similarly, foldr can be generalised to any algebraic type.
For lists, a call to foldr specifies two things: what
should be returned for the empty list, and what should be returned for
a non-empty list, given the head and the result of folding the tail.
For a general algebraic type we need to specify what should be returned
for each constructor in the type, given the arguments of the
constructor corresponding to type parameters and the result of folding
the arguments which correspond to a concrete type (generally the type
being defined recursively).
Consider the prod_leaves/2 example given earlier as
Program 3a.
The overall operation is to fold a tree into a single number. We
need to define the results of folding terms of the form
leaf(X) and tree(L,R), given the folded
versions of L and R.
Reconstructing the predicate is_tree/1 as a definition of
the type bt(T) and using the approach of (Naish, [Nai96]) we
arrive at Program 8: a version of foldr for this tree
type and corresponding definitions of prod_leaves/2 and
sum_leaves/2. In (Naish, [Nai96]) it was assumed that
foldrbt/4 would be written by a programmer who has the
required degree of insight. It is now clear that this predicate can be
generated automatically from a definition of the type.
This is discussed in Section 6.
:- type bt(T) ---> leaf(T) ; tree(bt(T),bt(T)).
foldrbt(TreeP, LeafP, leaf(X), Folded) :-
call(LeafP, X, Folded).
foldrbt(TreeP, LeafP, tree(L, R), Folded) :-
foldrbt(TreeP, LeafP, L, FoldedL),
foldrbt(TreeP, LeafP, R, FoldedR),
call(TreeP, FoldedL, FoldedR, Folded).
prod_leaves(T, P) :- foldrbt(times, =, T, P).
sum_leaves(T, P) :- foldrbt(plus, =, T, P).
Program 8: Extensions of Program 2a using foldr