[m-dev.] Automatic generation of map, foldr, foldl

[Peter Schachte]

> :- type tree(T) ---> leaf(T); t(tree(T),tree(T)).
> you can generate some Horn clauses:

 [ generalization of apply_closure_to_all_elements and member ]

> And with another declaration like
> :- skeleton tree_any/1 generates foldl, foldr, map(1), map(2).
> generate

 [ generalization of foldl, foldr, etc. ]


I like the idea of generating higher-order code, or indeed anything
that makes it easier to use higher levels of abstraction.  But I do
have the feeling that this isn't necessarily the right set of
abstractions.  For example, your first generated predicate is
something like "for all x in <data structure> f(x)", and your second
is "x in y."  Why isn't the second "there exists x in <data structure>
such that f(x)?"  And on binary trees, foldl and foldr do preorder and
postorder traversal; what about inorder?  And how about mapping and
folding operators that stop before traversing the whole data
structure?  There are so many variants of these travarsal predicates.

This would be much nicer if you could abstract what is common among
all of these and provide that.  A tall order.  Or maybe when you say
that one can write one's own predicates you're indicating that you've
made that abstraction.

One thought, though.  One way of abstracting part of what all of these
predicates do is with the concept of an "iterator" (I know, I know,
this word brings to mind horrible images of C++, but it's a pretty
good description).  I guess it's best to think of iterator as a family
of type classes iterator_n(T,CT,IT) where T is a type (or a tuple of
types somehow?), CT is a collection of T, and IT is an iterator for
that collection.  Instances of iterator1 provide these predicates and
functions:

	:- func iterator(CT::in) = IT::out is det.
	:- pred next(IT::in, IT::out, T::out) is semidet.

iterator2 provides:

	:- func iterator(CT::in, CT::in) = IT::out is det.
	:- func iterator(CT::in, CT::out) = IT::out is det.
	:- func iterator(CT::out, CT::in) = IT::out is det.
	:- pred next(IT::in, IT::out, T::out, T::out) is semidet.
	:- pred next(IT::in, IT::out, T::in, T::out) is semidet.
	:- pred next(IT::in, IT::out, T::out, T::in) is semidet.

and so on.  The iterator function and next predicate should support
all combinations of modes for the type CT and T terms where at least
one is input.  The idea, if the names didn't give it away, is that the
iterator function creates an iterator from some collections, which
must have exactly the same shape, and the next predicate gives back the
corresponding elements of the collections, and an iterator which will
return the rest of the collections.

Before I go on, I should say that I know the current Mercury mode
system couldn't handle this.  And I've probably messed up my use of
type classes.  But I hope you get the idea.  And maybe a polymorphic
mode system could handle this, I dunno.

Anyway, given just this, you can write a lot of the sorts of
higher-order predicates you're talking about generating once, and put
them in the library.  Eg, member is

	:- pred member(T::out, CT::in) is nondet <= iterator1(T,CT,IT).

	member(Elt, Coll) :-
		member1(Elt, iterator(Coll)).

	member1(Elt, It) :-
		next(It, _, Elt).
	member1(Elt, It) :-
		next(It, It1, _),
		member1(Elt, It1).

and map is

	:- pred map(pred(T,T) is det, CT::in, CT::out) is det
		<= iterator2(T,CT,IT).

	map(P, C0, C) :-
		map1(P, iterator(C0, C)).

	map1(P, It) :-
		(   next(It, It1, E0, E) ->
			P(E0, E),
			map1(P, It1)
		;   true
		).

and foldl is

	:- pred foldl(pred(T,A,A) is det, CT::in, A::in, A::out) is det
		<= iterator1(T,CT,IT).

	foldl(P, Coll, Acc0, Acc) :-
		foldl1(P, iterator(Coll), Acc0, Acc).

	foldl1(P, It, Acc0, Acc) :-
		(   next(It, It1, E) ->
			P(E, Acc0, Acc1),
			fold1(P, It1, Acc1, Acc)
		;   Acc = Acc1
		).

and so on.

Given this scheme, then all you would have to generate is the
iterators.  Generating pre- and post-order iterators should be a
easy.  Inorder iterators for types where nonterminals always have two
descendents should also be easy.  Beyond this, the user will have to
specify an order somehow.

Oh, I forgot to mention, I'm assuming lots of clever type
specialization to make this code reasonably efficient.

What do you think?


-- 
Peter Schachte                | The fantastic advances in the field of
mailto:pets at cs.mu.OZ.AU       | communication constitute a grave danger to
http://www.cs.mu.oz.au/~pets/ | the privacy of the individual.
PGP: finger pets at 128.250.37.3 |     -- Earl Warren