Automatic generation of map, foldr, foldl

Lee Naish Lee.Naish at cs.kuleuven.ac.be
Mon Sep 7 01:19:20 AEST 1998


I have been doing some (Prolog) hacking based on
http://www.cs.mu.oz.au/~lee/papers/hose/ which
discusses automatically generating various higher
order predicates from the data type.  From a type 
definition such as

:- type tree(T) ---> leaf(T); t(tree(T),tree(T)).

you can generate some Horn clauses:

tree(A, leaf(B)) :-
        call(A, B).
tree(A, t(B, C)) :-
        tree(A, B),
        tree(A, C).

tree_any(leaf(A)).
tree_any(t(A, B)) :-
        tree_any(A),
        tree_any(B).

And with another declaration like

:- skeleton tree_any/1 generates foldl, foldr, map(1), map(2).

generate

foldl_tree_any(A, B, leaf(C)) -->
        call(A, C).
foldl_tree_any(A, B, t(C, D)) -->
        call(B),
        foldl_tree_any(A, B, C),
        foldl_tree_any(A, B, D).

foldr_tree_any(A, B, leaf(C), D) :-
        call(A, C, D).
foldr_tree_any(A, B, t(C, D), E) :-
        foldr_tree_any(A, B, C, F),
        foldr_tree_any(A, B, D, G),
        call(B, F, G, E).

map_tree_any(A, leaf(B), leaf(C)) :-
        call(A, B, C).
map_tree_any(A, t(B, C), t(D, E)) :-
        map_tree_any(A, B, D),
        map_tree_any(A, C, E).

map2_tree_any(A, leaf(B), leaf(C), leaf(D)) :-
        call(A, B, C, D).
map2_tree_any(A, t(B, C), t(D, E), t(F, G)) :-
        map2_tree_any(A, B, D, F),
        map2_tree_any(A, C, E, G).

I figured it would be nice to incorporate such a mechanism 
into Mercury.  It should be possible to incorporate this kind
of thing into the type class mechanism I would have thought,
and have types "inherit" these higher order predicates/functions.

What d'yall think?

	lee




More information about the developers mailing list