maxlist(L, M) that succeeds if M is the max number in the list L

Question

I'm working my way through "Prolog For Artificial Intelligence" by Ivan Bratko, and exercise 3.17 is to write a maxlist(L, M) that succeeds when M is the largest number in the list L.

My attempt at this was:

maxlist([H|T], Max) :-
  maxlist(T, H, Max).
maxlist([], Max, Max).
maxlist([H|T], CurrentMax, Max) :-
  (
    CurrentMax > H
    -> maxlist(T, CurrentMax, Max)
    ;
    maxlist(T, H, Max)
  ).

The author's solution was:

  maxlist2([N], N).
  maxlist2([N1,N2|T], Max) :-
    maxlist2([N2|T], MaxTail),
    max(N1, MaxTail, Max).

My code is longer, and not as easy to read, but his code gave a choice point.

Anyone have any comments on either piece of code? In particular, is there anything to choose his over mine or vice versa?

Answer 1

If you change the first clause to maxlist2([N], N) :- !., the extra choice point disappears. Your implementation does not recognize the fact that the two clauses are mutually exclusive in the second predicate, but does recognize it for the first predicate. Most probably it can make the distinction between the "empty" and "non-empty" lists case, but not between "length 1" and "length 2 and more".

The use of cut (!) - which cuts off the choices, - is usually frowned upon but your first predicate already uses it, implicitly, by using the -> construct.

Also, the first predicate does only one traversal of the input list, from its head to the tail, whereas the second, being non-tail recursive, traverses it twice - first on the way down to the recursion's base case, and then it travcerses the same length on the stack, on the way back from it.