[mercury-users] challenge

[Gustavo A. Ospina]

I have two approaches to solve colect_pairs.

The first is the simplest solution. collect_pairs only must suceed with
iso-morphic trees.

To manage non isomorphic trees, I define an auxiliar type

:- type undefined(T) --->
        undefined  /* Term not belongs to T */
    ;   elem(T).

This implies redefine the predicate to manage lists of pairs of undefined
type:
:- pred collect_pairs2(tree(T),tree(T),list(pair(undefined(T)))).

When there are non isomorphic trees, result list is composed of pairs of
(undefined,elem(X)) or (elem(X),undefined), depending to empty tree is the
first or the second, respectively.

Alternatives to manage non iso-morphic trees:

- For each type, define an "special undefined term" (e.g. -1 for natural
numbers), instead of use type undefined(T). That is right when we do not
use all the domain of terms wich the type can accept.

- Can be defined an special polimorphic term '_undefined' in Mercury
Compiler?. With such term, special conditions like non iso-morphic trees 
could be handled without have to failure in the clause, and solutions to
collect_pairs problem could be more elegant. Drawback: posible 
complications in type-check algoritm and others predicates and functions.
What do you think?.

All you have a nice day. Best Regards.

+ Gustavo.

--------------------------- First Solution -------------------------------

:- 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),tree(T),list(pair(T))).
:- mode collect_pairs(in,in,out) is semidet.

:- implementation.

collect_pairs(empty,empty,[]).

collect_pairs(empty,tree(_Left,_Root,_Right),_WrongList) :- fail.

collect_pairs(tree(_Left,_Root,_Right),empty,_WrongList) :- fail.

collect_pairs(tree(Left1,Root1,Right1),tree(Left2,Root2,Right2),ListPairs) :-
    collect_pairs(Left1,Left2,PairsLeft),
    collect_pairs(Right1,Right2,PairsRight),
    list__append(PairsLeft,[(Root1,Root2)|PairsRight],ListPairs).

--------------------------- Second Solution -------------------------------

:- module collect_pairs2.

:- interface.

:- import_module list.

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

:- type pair(T) --->
    (T,T).

:- type undefined(T) --->
         undefined
    ;    elem(T).

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

:- implementation.

collect_pairs2(empty,empty,[]).

collect_pairs2(empty,tree(Left,Root,Right),ListPairs) :-
    collect_pairs2(empty,Left,LeftList),
    collect_pairs2(empty,Right,RightList),
    list__append(LeftList,[(undefined,elem(Root))|RightList],ListPairs).

collect_pairs2(tree(Left,Root,Right),empty,ListPairs) :-
    collect_pairs2(Left,empty,LeftList),
    collect_pairs2(Right,empty,RightList),
    list__append(LeftList,[(elem(Root),undefined)|RightList],ListPairs).

collect_pairs2(tree(Left1,Root1,Right1),tree(Left2,Root2,Right2),ListPairs) :-
    collect_pairs2(Left1,Left2,PairsLeft),
    collect_pairs2(Right1,Right2,PairsRight),
    list__append(PairsLeft,[(elem(Root1),elem(Root2))|PairsRight],ListPairs).