Prolog: won't get the biggest element

Question

I'm learning prolog but I'm having some difficulties with learning it. I have an query that goes through a list of elements each with each own element and value and I'm trying to get the element with the biggest value...

highest([(d,1), (c, 1), (b, 2), (a, 1)], X, 0).

So in this case the output should be (or the X) b. My code is as follows:

highest([], _, _).
highest([(El, V)|Tail], X, Y) :-
(
    V >= Y ->
    highest(Tail, El, V)
;
    highest(Tail, X, Y)
).

Thanks will be appreciated!

Answer 1

I'd go with something like this:

highest(L, Elem):-
  highest(L, [], Elem, 0).

highest([], Elem, Elem, _).
highest([(El, V)|Tail], CurElem, Elem, Y):-
  (V >= Y -> highest(Tail, El, Elem, V) ; highest(Tail, CurElem, Elem, Y)).

highest/2 just calls highest/4 with current element as [] and current value as 0.

Then the base clause of highest/4 just unifies CurrentElement with Element (arguments 2 and 3).

Recursive clause checks value of the first element in the input list and calls itself recursively with the tail using the El or CurElem and V or Y accordingly.

Answer 2

The short answer to why your code doesn't work is that you're never binding a value to X. In Prolog, all variables are local and the only way to propagate them is to pass them along down the call stack. You're passing then down the call stack, but at the end, the final result gets discarded as the call stack gets unwound. And when you get to the topmost framce of the call stack, you're left with your original X and Y values.

A common prolog idiom is the use of a helper or worker predicate that does all the work. They carry the original parameters, plus 1 or more extra parameters that maintain state. When it finally succeeds, that state is unified with the original parameters and the final values are propagated back up the call stack.

I would approach the problem like this:

%
% The public predicate. All it does is call a worker predicate, seeding its state variables with the head of the list and passing the tail of the list.
% After all, an empty list doesn't really have a max value: it should just fail
%
highest( [(Emax,Vmax)|Xs] , E , V ) :- highest(Xs,Emax,Vmax,E,V) .

highest( []         , Emax , Vmax , E , V ) .  % if the source list is exhausted, we're done: unify the state variable with the result variables.
highest( [(E,V)|Xs] , Emax , Vmax , E , V ) :- % otherwise,
  V >= Vmax ,                                  % - if the current V is greater than or equal to the current Vmax,
  E1 = E ,                                     %   - The current E becomes the new Emax
  V1 = V ,                                     %   - The current V becomes the new Vmax
  highest( Xs , E1 , V1 , E , V )              % - and we recurse down on the remainder of the list
  .                                            %
highest( [(E,V)|Xs] , Emax , Vmax , E , V ) :- % otherwise,
  V < Vmax ,                                   % - if the current `V` is less than the current `Vmax`,
  highest( Xs , Emax , Vmax , E , V )          % - we discard the current list node and recurse down on the remainder,
  .                                            %   leaving `Emax` and `Vmax` unchanged.

You'll note in the above, that E and V never get unified until the work is complete: we have two helper variables, Emax and Vmax that get carried only down the call stack as we recurse over the list. You could also rewrite this to use implication as

highest( []         , E    , V    , E , V ) .   % source list exhausted? we're done.
highest( [(E,V)|Xs] , Emax , Vmax , E , V ) :-  % otherwise...
  ( V >= Vmax ->                                % - found new highwater mark? If so
      E1 = E ,                                  %   - get new Emax
      V1 = V ,                                  %   - get new Vmax
  ;                                             %   otherwise...
      E1 = Emax ,                               %   - reuse the existing Emax
      V1 = Vmax                                 %   - reuse the existing Vmax
  ) ,                                           % and
  highest( Xs , E1 , V1 , E , V )               % - recurse down on the remainder.
  .                                             %

Whether this latter version is simpler or easier to understand than the former is left as an exercise for the reader.