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

[Fergus Henderson]

On 09-Sep-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> > :- 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.

I agree with Peter here.

> Or maybe when you say
> that one can write one's own predicates you're indicating that you've
> made that abstraction.

That *seemed* to be what Lee was saying, but I couldn't see how it
would work, and Lee hasn't given us any examples (hint, hint ;-).

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

That won't work; you're not allowed to put constraints on type
variables such as `IT' which don't occur in the predicate's arguments.
The compiler can't figure out what type `IT' should be.  Note there
might be more than one possible iterator type for a given collection
type and element type.  For example, you might have iterators that
iterate forwards, iterators that iterate backwards, iterators that
iterate only over the even-numbered elements, etc.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.