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
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
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
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).
prod_leaves/2 example given earlier as
The overall operation is to fold a tree into a single number. We
need to define the results of folding terms of the form
tree(L,R), given the folded
Reconstructing the predicate
is_tree/1 as a definition of
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
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