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

[Peter Schachte]

On Mon, Sep 21, 1998 at 02:25:28PM +1000, Fergus Henderson wrote:
> On 09-Sep-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> > 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.

Yup, I pushed it too far; I forgot to reply to my own message to
correct this.  Instead of what I was suggesting earlier, I now suggest
a family of typeclasses iterator_n(T1,... Tn, IT) indicating that IT
is an iterator of types T1 to Tn.  This promises only the operations

	:- pred next(IT::in, IT::out, T1::out, ... Tn::out) is semidet.
	:- pred finished(IT::in) is semidet.

Then a generalized member/2 could be defined as

	:- predicate member(T, IT) <= iterator(IT, T).

	member(E, It) :-
		next(It, It1, E1),
		(   E1 = E
		;   member(E, It1)
		).

and called as

	member(E, iterator(L))

where

	:- func iterator(list(T)) = list(T)
	iterator(L) = L.

	:- instance iterator1(list(T), T).
	next([H|T], T, H).
	finished([]).

and

	:- type int_range ---> int - int.

	:- instance iterator1(int_range, int).
	next(Low-High, Low, Low+1..High) :- Low =< High.
	finished(Low-High) :- High = Low-1.

and

	:- type tree(T) ---> leaf ; tree(tree(T), T, tree(T)).
	:- type tree_inorder(T) --->
		(   empty 
		;    down(tree(T), tree_inorder(T))
		;    up(tree(T), tree_inorder(T))
		).

	:- func inorder(tree(T)) = tree_inorder(T)
	inorder(T) = down(T, empty).

	:- instance iterator1(tree_inorder(T), T).
	next(down(leaf, Stack0), E, Stack) :-
		next(Stack0, E, Stack).
	next(down(tree(L,E,R), Stack0), E1, Stack) :-
		next(down(L, up(tree(L,E,R), Stack0)), E1, Stack).
	next(up(tree(_,E,R), Stack), E, down(R, Stack)).
	finished(empty).


and map/3 could be defined as:

	:- pred map(pred(T1,T2), IT) <= iterator2(IT, T1, T2).

	map(P, It) :-
		(   next(It, It1, X1, X2) ->
			P(X1, X2),
			map(P, It1)
		;   finished(It)
		).

and invoked as

	map(pred(X,X+1), iterator(List,Successors))

(assuming pred(X,X+1) is the right syntax), where

	:- func iterator(list(T1), list(T2)) = pair(list(T1), list(T2)).
	iterator(L1, L2) = L1-L2

	:- instance iterator2(pair(list(T1), list(T2)), T1, T2).
	next([H1|T1]-[H2|T2], T1-T2, H1, H2).
	finished([]-[]).

I wonder if deforestation is smart enough to remove the unnecessary
construction of iterator data structures?

The interesting bit comes in when you make an iterator that is a pair
of other iterators, so both length and iota (a la apl) can be defined
as a simple operation over a pair of a list and integer range
iterator.  You need the concept of accumulators to handle folding, but
they can be defined, too.  Also, a nicer syntax, perhaps some sort of
`forall' syntax, would make this a lot more pleasant.

I'll leave the discussion of these points to another message.


-- 
Peter Schachte                | The question of whether a computer can think
mailto:pets at cs.mu.OZ.AU       | is no more interesting than the question of
http://www.cs.mu.oz.au/~pets/ | whether a submarine can swim.
PGP: finger pets at 128.250.37.3 |     -- E. W. Dijkstra