prolog-false is returned instead of a number

592 views Asked by At

I am trying to write a predicate that returns the minimum and maximum between two numbers. The min and max predicates work fine, however when I try the min_max function with for example min_max(2,5,X,Y), I get false. Can anyone help?

min(X,Y,X) :- X=<Y.
min(X,Y,Y) :- Y<X.

max(X,Y,Y) :- X=<Y.
max(X,Y,X) :- Y<X.

min_max(X,Y,MIN,MAX) :-
   min(X,Y,MIN),
   max(X,Y,MAX).
2

There are 2 answers

2
Nicholas Carey On

Your min/2 and max/2 are indeterminate, so there are alternatives to be looked for. When you evaluate

min_max(2,5,X,Y).

You see

X = 2,
Y = 5

and it pauses, waiting for input from you. If you then press ., it will succeed. If, however, you press ; it searches for the alternatives, and finding none, fails.

You need to modify your min/2 andmax/2 to be determinate, something like this:

min(X,Y,Z) :- ( X < Y -> Z = X ; Z = Y ) .

max(X,Y,Z) :- ( X > Y -> Z = X ; Z = Y ) .

[The -> operator (implication) effectively acts as a 'soft cut', eliminating alternatives.]

Once you do that, it will work as you might expect, without pausing for your input (as you've eliminated the choice points):

13 ?- min_max(2,5,X,Y).
X = 2,
Y = 5.

14 ?- 

It might help if you think of the your prolog program as something of a tree with the choice points as branches (and solutions as leaf nodes). The prolog engine runs over that tree trying to find solutions.

In your original program, your min_max/4 has 4 possible solutions (2 for min/2 and 2 for max/2), even though there is just one "functional" solution. On backtracking, the prolog engine trys to find alternative solutions and finding none, fails.

By re-writing min/2 and max/2 to eliminate the choice points, we are effectively pruning the tree as we descend it, leaving us with a single solution.

4
repeat On

How about combining min/3 and max/3 in a slightly different way? Consider this definition:

min_max(X,Y,X,Y) :- X =< Y.
min_max(X,Y,Y,X) :- Y  < X.

Sample queries:

?- min_max(2,5,Min,Max).
Min = 2,  Max = 5 ;
false.

?- min_max(20,5,Min,Max).
Min = 5,  Max = 20.

?- min_max(10,10,Min,Max).
Min = 10, Max = 10 ;
false.