Prolog issue with max list function: nondeterm vs procedure

Question

I am trying to do a small project in prolog where a user can input a list and then it calculates the average, max in the list etc. etc.

So far so good, but I ran into a problem when writing the max function (finds max number in the list). The code is:

maxN([X],X):-!.
maxN([X|L],X) :- maxN(L,M), X > M.
maxN([X|L],M) :- maxN(L,M), M >= X.

The function itself works separately, but I get this error message:

The predicate 'forma::maxN/2 (i,o)', which is declared as 'procedure', is actually 'nondeterm' forma.pro

This is my predicate in the *.cl definition:

maxN: (integer* Z, integer U) procedure (i,o).

I cannot declare it as nondeterm because it causes issues with my whole form. Can you help me/give a hint how to make it a procedure? I am thinking I have to make a cut somewhere but my attempts have failed so far.

P.S. I am using Visual Prolog 7.4.

Edit: After trying the alternatives proposed to make the two rules into one or with an accumulator, I now get that the predicate is 'determ' instead of a procedure. According to my Prolog guide that means that the predicate doesn't have multiple solutions now, but instead has a chance to fail. Basically all code variations I've done up to now lead me to a 'determ'.

Answer 1

The problem is that Prolog sees a choice point between your second and third rules. In other words, you, the human, know that both X > M and M >= X cannot both be true, but Prolog is not able to infer that.

IMO the best thing to do would be to rephrase those two rules with one rule:

maxN([X], X) :- !.
maxN([X|L], Max) :- 
   maxN(L, M), 
   X > M -> Max = X
          ; Max = M.

This way there isn't ever an extra choice point that would need to be pruned with a cut.

Following @CapelliC's advice, you could also reformulate this with an accumulator:

maxN([X|Xs], Max) :- maxN_loop(Xs, X, Max).

maxN_loop([], Max, Max).
maxN_loop([X|Xs], Y, Max) :- 
   X > Y -> maxN_loop(Xs, X, Max)
          ; maxN_loop(Xs, Y, Max).

Answer 2

sorry, I don't know the Prolog dialect you're using, my advice is to try to add a cut after the second clause:

maxN([X|L],X) :- maxN(L,M), X > M, !.

Generally, I think a recursive procedure can be made deterministic transforming it to tail recursive. Unfortunately, this requires to add an accumulator:

maxN([],A,A).
maxN([X|L],A,M) :- X > A, !, maxN(L,X,M).
maxN([X|L],A,M) :- maxN(L,A,M).

Of course, top level call should become

maxN([F|L],M) :- maxN(L,F,M).