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).