[mercury-users] challenge

[David Matthew Overton]

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).
> 
> collect_pairs(T, U, L) should hold exactly when L is a list of
> corresponding elements of T and U in an inorder traversal of the
> trees.  The catch is that T and U may not be the same shape.  You can
> assume the trees will contain the same numbers of nodes if you like,
> or just collect as many pairs as there are nodes in the smaller tree.
> Take your pick.
> 
> Oh, and no fair turning T and U into lists and then operating on the
> lists.  What I'm looking for is code to traverse two different-shaped
> trees at once.  I speculate that there is no reasonably elegant way to
> do it, but I'd be delighted to be proved wrong.
> 

Here's a solution using higher order predicates to traverse the trees
lazily.  Does this count as  a ``reasonably elegant'' solution, 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
-- 
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