Re: How to fight semideterminism in Mercury?

From: Dmitri Soshnikov (dsoshnikov_at_gmail.com)
Date: 10/17/04 

Date: 17 Oct 2004 13:03:06 -0700

Hello,

Bart, thanks for your reply!

> > :- type tree(T) ---> nil; tree(T,avltree(T),avltree(T)).
> > :- type avltree(T) ---> tree(T)/int.
> >
> > When we come to element addition predicate, it is defined as follows:
> >
> > :- func add(int,avltree(int)) = avltree(int).
> > :- mode add(in,in) = out is semidet.
> > add(X,nil/_) = tree(X,nil/0,nil/0)/1.
> > add(X,tree(Y,L,R)/H) = Res :-
> > X<Y ->
> > tree(Z,L1,R1)/_ = add(X,L),
> > Res = combine(L1,Z,R1,Y,R);
> > X>Y ->
> > tree(Z,L1,R1)/_ = add(X,R),
> > Res = combine(L,Y,L1,Z,R1);
> > Res = tree(X,L,R)/H.
> >
>
> Can you also show your code for combine/5 ?
> Isn't that where one should be able to see that
> Res is always a non-emtpy tree ?

Sorry, I should have posted this in the first place:

:- func combine(avltree(int),int,avltree(int),int,avltree(int)) =
avltree(int).
:- mode combine(in,in,in,in,in) = out is semidet.
combine(T1/H1, A, T2/H2, C, T3/H3) = R :-
        (H2>H1, H2>H3) -> T2=tree(B,T21,T22), Ha=H1+1, Hc=H3+1, Hb=Ha+1,
R=tree(B,tree(A,T1/H1,T21)/Ha,tree(C,T22,T3/H3)/Hc)/Hb;
        (H1>=H2, H1>=H3) -> Hc=max(H2,H3)+1, Ha=max(H1,Hc)+1,
R=tree(A,T1/H1,tree(C,T2/H2,T3/H3)/Hc)/Ha;
                            Ha=max(H1,H2)+1, Hc=max(Ha,H3)+1,
R=tree(C,tree(A,T1/H1,T2/H2)/Ha,T3/H3)/Hc.

The predicate is also semidet, because unification T2=tree... can
fail; however, in real life it cannot, because H2>H3 guarantees that
the T2 is non-empty tree... Since the problem is very similar to the
first code, I thought I would just post one piece of code not to
overcrowd the group...

Thanks,

Dmitri.