3

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).
false
  • 10,264
  • 13
  • 101
  • 209
Kathy Robb
  • 31
  • 1
  • 1
    In the latest SWI-Prolog: `?- min_max(2,5,X,Y). X = 2, Y = 5`. – Wouter Beek Jun 08 '15 at 21:12
  • @false Not that I know of. I merely wanted to indicate that on my implementation of Prolog I cannot reproduce the reported behavior (i.e., the goal not succeeding). – Wouter Beek Jun 09 '15 at 14:56

2 Answers2

1

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.

Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • Your statement "The `->` operator ... a 'soft cut' ..." is misleading. I get what you want to express, but 'soft cuts' are already in SWI (`(*->)/3`) and SICStus (`if/3`). Unlike `->` the soft cuts do not eliminate alternatives. – repeat Jun 08 '15 at 23:50
  • @repeat: There is no `(*->)/3`, it's rather `(;)/2` since the principal functor is `(;)/2` and not `(*->)/2`. – false Jun 09 '15 at 08:13
1

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.
repeat
  • 18,496
  • 4
  • 54
  • 166
  • This is the correct way to do it (+1): if you have a min, the other one should be max (right?); I don't like the dangling choice points, but I don't want to get into that topic. –  Jun 09 '15 at 06:54
  • 2
    [Here](http://stackoverflow.com/questions/29156560/sorting-large-lists-in-prolog-not-enough-memory/29164060#29164060) somewhere in the middle is a discussion on how to avoid the choice point. Spurious choice points are the one truly ugly face of Prolog (personal opinion, arguments: gut feeling). –  Jun 09 '15 at 07:00
  • 3
    @Boris: Spurious choice points are an efficiency problem, but they do not affect correctness. Better programming techniques (like [`if_/3`](http://stackoverflow.com/a/27358600/772868) and [`call_semidet/1`](http://stackoverflow.com/a/12942551/772868)) can help to remove them. – false Jun 09 '15 at 08:17
  • 4
    Please note the asymmetry of this definition when you consider floats, too. Like `min_max(1,1.0, Min, Max)` and `min_max(1.0,1,Min,Max)`. – false Jun 09 '15 at 08:23