[mercury-users] challenge

[Andrew Bromage]

G'day all.

David Matthew Overton wrote:

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

Here's a variation on the same theme, using stacks instead of
closures.

Warning: untested code follows.

<<
:- 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 semidet.

:- implementation.

:- type tselement(T)
        --->    singleton(T)
        ;       tree(tree(T)).

:- type tree_stack(T) == list(tselement(T)).

collect_pairs(T1, T2, List) :-
        collect_pairs_2([tree(T1)], [tree(T2)], [], List).

:- pred collect_pairs_2(tree_stack(T), tree_stack(T),
                list(pair(T)), list(pair(T))).
:- mode collect_pairs_2(in, in, in, out) is semidet.

collect_pairs_2(L0, R0, Xs0, Xs) :-
        ( pop(L0, X, L) ->
                pop(R0, Y, R),
                collect_pairs_2(L, R, [X - Y | Xs0], Xs)
        ;
                \+ pop(R0, _, _),
                Xs = Xs0
        ).

:- pred pop(tree_stack(T), T, tree_stack(T)).
:- mode pop(in, out, out) is semidet.

pop([singleton(T) | S], T, S).
pop([tree(empty) | S0], T, S) :- pop(S0, T, S).
pop([tree(tree(L, X, R)) | S0], T, S) :-
        pop([tree(R), singleton(X), tree(L) | S0], T, S).
>>

Unfortunately, the termination analyser can't prove the termination of
pop/3 using any of the built-in norms. :-(

Cheers,
Andrew Bromage