[mercury-users] challenge

[Henk Vandecasteele]

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.

How about this:

:- module collect_pairs.
:- interface.

:- import_module list.

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

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

:- implementation.



collect_pairs(empty, empty, []).
collect_pairs(Tree1, Tree2, List):-
	Tree1 = tree(Left1, El1, Right1),
	Tree2 = tree(Left2, El2, Right2),
	( Left1 = empty ->
	    ( Left2 = empty ->
		List = [(El1, El2)|List2],
		collect_pairs(Right1, Right2, List2);
		Left2 = tree(Left3, El3, Right3),
		collect_pairs(Tree1, tree(Left3,El3,
					  tree(Right3, El2, Right2)),
			      List)
	    );
	    ( Left2 = empty ->
		Left1 = tree(Left4, El4, Right4),
		collect_pairs(tree(Left4, El4,
				   tree(Right4, El1, Right1)),
			      Tree2, List);
		Left1 = tree(Left4, El4, Right4),
		Left2 = tree(Left3, El3, Right3),
		collect_pairs(tree(Left4, El4,
				   tree(Right4, El1, Right1)),
			      tree(Left3, El3,
				   tree(Right3, El2, Right2)),
			      List)
	    )

	).



I hope I understood the question.

Henk