Before implementing our transformation tools we recognised several programming patterns and implemented the corresponding higher order predicates. A version of map which also has an accumulator pair of arguments, map_acc, has been of use and could be implemented in functional languages as well. A variation of map0 which calls a predicate for each consecutive pair of elements in a list, map0_consec, can be used to check sortedness, for example. This could be adapted to functional programming by applying functions which return booleans. We have also used a combination of map and filter which relies on the ability of a predicate to either return a result or fail: split(P,Xs,Ys,Zs) applies P/2 to each member of Xs and returns the list of results of successful calls to P and the list of elements for which P failed.
We have also found it useful to extend our tools to implement
transformations which are special cases of other higher order predicates.
Instead of using a complicated instance of a very general higher order
predicate, we can use a relatively simple predicate. This is appropriate if
the instance of the higher order predicate is common. We have already seen
an example of this: map is an instance of foldr, at least in
the case of algebraic types. It is somewhat special instance since it is
particularly useful and can be coded in a tail-recursive way due to the
nature of unification. We have implemented another instance of
map/foldr which preserves the shape of the data structure
without relating the elements: same_shape. It is a generalisation
of same_length for lists. We have also implemented an instance
of foldl which converts any data structure into a list using an
accumulator, list_from, which generalises a reverse post-order
traversal. The transformed code contains calls to append where
the first argument is the list of variables which don't occur in recursive
calls. The append calls are optimised away by the DCG expansion
in NU-Prolog.
Program 20 shows the result of transforming rtree_any/1.
list_from_rtree_any(rt(A, B)) -->
append([A]),
list_from_list_rtree_any(B).
list_from_list_rtree_any([]) -->
append([]).
list_from_list_rtree_any([A|B]) -->
append([]),
list_from_rtree_any(A),
list_from_list_rtree_any(B).
Program 20: List-from transformation for rtree_any/1