[mercury-users] Newbie problem. :)

[Fergus Henderson]

On 12-Jun-1999, Rob <zharradan at suffering.org> wrote:
> my_insert(X, Y, Z) :-
> 	(
> 	    Y = [Hd | Tl],
> 	    (
> 		X =< Hd,                  <-- Line 40
> 		Z = [X | [Hd | Tl]]
> 	    ;
> 		X > Hd,
> 		my_insert(X, Tl, W),
> 		Z = [Hd | W]
> 	    )
> 	;   
> 	    Y = [],
> 	    Z = [X]
> 	).
...
> blah.m:018: In `my_insert(in, in, out)':
> blah.m:018:   error: determinism declaration not satisfied.
> blah.m:018:   Declared `det', inferred `nondet'.
> blah.m:040:   call to `=<(in, in)' can fail.
> blah.m:043:   call to `>(in, in)' can fail.
> blah.m:042:   Disjunction has multiple clauses with solutions.
> 
> I am obviously missing something here, but I thought this was the way
> things were supposed to work - part of the disjunction fails, and it
> checks against the rest..
> 
> Help. :)

The compiler's determinism analysis follows a fairly simple algorithm;
this algorithm is not smart enough to figure out that the two different
tests X =< Hd and X > Hd are mutually exclusive and cover all cases,
because it doesn't have any knowledge about the semantics of particular
predicates such as `=<' and `>' other than that given by their type,
mode and determinism declarations.  As far as the compiler's determinism
analysis is concerned, you might equally as well have written

 	    (
 		p(X, Hd),
 		Z = [X | [Hd | Tl]]
 	    ;
 		q(X, Hd),
 		my_insert(X, Tl, W),
 		Z = [Hd | W]
 	    )
	    ...
	    :- pred p(int::in, int::in) is semidet.
	    :- pred q(int::in, int::in) is semidet.

and so the compiler has to assume that this disjunction might fail
or might have two solutions.

The solution in cases like this is to use an if-then-else rather than
a disjunction:

 	    (if X =< Hd then
 		Z = [X | [Hd | Tl]]
 	    else /* X > Hd */
 		my_insert(X, Tl, W),
 		Z = [Hd | W]
 	    )

P.S.
This is a quite common question; it ought to be in the FAQ list...

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------