[mercury-users] challenge

[David Matthew Overton]

I apologise if anyone gets this twice.  It didn't seem to work the
first time I tried sending it.

On Fri, Sep 25, 1998 at 10:58:08PM EST, Peter Schachte wrote:
> Here's a programming challenge that should be a bit more interesting
> than writing rot13 in Mercury.  Given a type
> 
> 	:-type tree(T) ---> empty ; tree(tree(T), T, tree(T)).
> 
> write a predicate
> 
> 	:- pred collect_pairs(tree(T), tree(T), list(pair(T))).
> 	:- mode collect_pairs(in, in, out).
> 

Here's a solution using higher order predicates to traverse the trees
lazily.  Do you consider this ``reasonably elegant'', Peter?

:- module challenge.

:- interface.
:- import_module list, std_util.

:- type tree(T)
	--->	empty
	;	tree(tree(T), T, tree(T)).

:- pred collect_pairs(tree(T), tree(T), list(pair(T))).
:- mode collect_pairs(in, in, out) is det.

:- implementation.

collect_pairs(Tree1, Tree2, List) :-
	collect_pairs_2(get_elements([Tree1]), get_elements([Tree2]), List).

:- type next(T)
	--->	next(T, pred(next(T))).

:- inst next
	--->	next(ground, pred(out(next)) is semidet).

:- pred collect_pairs_2(pred(next(T)), pred(next(T)), list(pair(T))).
:- mode collect_pairs_2(pred(out(next)) is semidet, 
		pred(out(next)) is semidet, out) is det.

collect_pairs_2(P1, P2, L) :-
	(
		P1(next(E1, P1Prime)),
		P2(next(E2, P2Prime))
	->
		L = [E1 - E2 | L0],
		collect_pairs_2(P1Prime, P2Prime, L0)
	;
		L = []
	).

:- pred get_elements(list(tree(T)), next(T)).
:- mode get_elements(in, out(next)) is semidet.

get_elements([empty | Trees], R) :-
	get_elements(Trees, R).
get_elements([tree(L, E, R) | Trees], next(E, get_elements([L, R | Trees]))).

-- 
David Overton
MEngSc Student                       Email: dmo at cs.mu.oz.au     
Department of Computer Science       Web: http://www.cs.mu.oz.au/~dmo
The University of Melbourne          Phone: +61 3 9344 9159