challenge

[Peter Schachte]

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.


-- 
Peter Schachte                | What we cannot speak about we must pass over
mailto:pets at cs.mu.OZ.AU       | in silence.
http://www.cs.mu.oz.au/~pets/ |     -- Wittgenstein 
PGP: finger pets at 128.250.37.3 |