How can I get this simple Prolog predicate to “return” the right way?

2
votes

So I am learning Prolog. I need to write a predicate that finds the min/max value of an integer list. For example, the query minmaxArray([4,-1,5,4,1,2,3,-2],X,Y) would return X = -2 Y = 5. Here is what I have so far:

    %min/max element of a 1 item list is that item.

    minmaxArray([X], X, X).

%when there is only 2 items, put the smaller element in A and the 
%larger element in B

    minmaxArray([X,Y], A, B) :- mymin(X,Y,Min), 
    A is Min, mymax(X,Y,Max), B is Max.

%when there is more than two items make a recursive call to find the min/max
%of the rest of the list.

    minmaxArray([X,Y|T], A, B) :- minmaxArray([Y|T], M, K), 
    mymin(X,M,Temp), A is Temp, mymax(X,K,Temp2), B is Temp2.

Assume mymin and mymax predicates work properly. They return the min and max of 2 numbers.

The issue here is that for example when I query minmaxArray([4,-1,5],X,Y) it returns X = -1 Y = 5 and then again X = -1 Y = 5. I know this must be because it hits the 2nd condition on the recursive call. I only want it to return X = -1 Y = 5 one time. I tried replacing condition 3 with this:

minmaxArray([X,Y,_|T], A, B) :- minmaxArray([Y,_|T], M, K), 
    mymin(X,M,Temp), A is Temp, mymax(X,K,Temp2), B is Temp2.

but that crashes the program. What can I do to fix this?

Note: I know that I may not be using the terminology correctly by saying returning and saying predicate when it should be rule, etc so I apologize in advance.

3
prolog
You don't need is/2 at all--you're not doing any arithmetic. You can just say minmaxArray([X,Y], Min, Max) :- mymin(X,Y,Min), mymax(X,Y,Max). – Daniel Lyons
You can use min(X,Y) built in as, Min is min(X,Y) to obtain the minimum of two values. Likewise for max. That might make your life a little simpler. And to build on @DanielLyons comment, don't use is to unify terms. Use =/2. So for example, B = Temp2, not B is Temp2. Also as pointed out, you can avoid that step altogether by unifying them right in the argument list, as his example shows. – lurker
Ok, so I am totally new to this and this may be a stupid question but what is =/2 and when you say not to use is and use = instead, is that because 'is' is used when you want to evaluate an arithmetic operation? Thanks! – Rob L
The notation predicate/N is the name of the predicate with the arity (number of arguments). =/2 is = and is/2 is is (that's easy to read!). You use =/2 when you want to explicitly unify two terms and you use is/2 when you want to unify the variable or value on the left side with the result of evaluating the arithmetic expression on the right side. – Daniel Lyons
By the way, "predicate" is correct nomenclature, but "return" is not. Moreover, you're not crashing the program, it's just failing. – Daniel Lyons

3 Answers

2
votes

Seems that your code could be simpler. This predicate does all what's needed, and attempt to show how to use some standard construct (if/then/else)

minmaxArray([X], X, X).
minmaxArray([X|R], Min, Max) :-
    minmaxArray(R, Tmin, Tmax),
    ( X < Tmin -> Min = X ; Min = Tmin ), % or mymin(X,Tmin,Min)
    ( X > Tmax -> Max = X ; Max = Tmax ).
2
votes

You have provided 2 ways of solving the case where there are 2 items: one explicitly for 2 items, and your general case, which then employs the 1 element case.

Solution: remove the unneeded 2-element case.

1
votes

Or, tail-recursive:

minmax([X|Xs],Min,Max) :- % we can only find the min/max of a non-empty list.
  minmax(Xs,(X,X),Min,Max)  % invoke the helper with the min/max accumulators seeded with the first item
  .

minmax([],(Min,Max),Min,Max).    % when the source list is exhausted, we're done: unify the accumulators with the result
minmax([X|Xs],(M,N),Min,Max) :-  % when the source list is non-empty
  min(X,M,M1) ,                  % - get a new min value for the accumulator
  max(X,N,N1) ,                  % - get a new max value for the accumulator
  minmax(Xs,(M1,N1),Min,Max)     % - recurse down on the tail.
  .

min(X,Y,X) :- X =< Y . % X is the min if it's less than or equal to Y.
min(X,Y,Y) :- X >  Y . % Y is the min if it's greater than X.

max(X,Y,X) :- X >= Y . % X is the max if it's greater than or equal to Y.
max(X,Y,Y) :- X <  Y . % Y is the max if it's greater than X.