Prolog - Arguments are not sufficiently instantiated. lists/recursion

0
votes

I am trying to get the maximum number from a given list 'L' and assign it to a variable, so I used to write the following function:

max(L,X):-
    [H|Q]=L,
    (X<H -> X=H),
    length(Q,QLEN),
    (QLEN>0 -> max(Q,X)),
    true.

However after compiling the code and prompting max([1,2,3],X) within SWI-Prolog, I get the following error:

ERROR: Arguments are not sufficiently instantiated ERROR: In: ERROR:
[9] _1064<1 ERROR: [8] max([1,2|...],_1092) at c:/users/kais/desktop/tp3.pl:24 ERROR: [7]

Why I'm getting such error?

2
listprologinstantiation-error
Because X does not have a value when you try to compare it with H. That whole line makes no sense in Prolog. You need some other parameter for the max value so far. - Tomas By
Don't try to compute the length at each step. The search ends when the list is empty. - coredump
@TomasBy If I initialize X within the function, I lose its value for the next recursion. - user6039980
@coredump okay. - user6039980
@Kais: in the answer below, the base case of maxList/3 is where your X gets instantiated, ie at the end. - Tomas By

2 Answers

3
votes

As said in the comment you try to compare H with X which is not instantiated. A solution to this problem is to create a predicate maxList/3 and call it inside maxList/2 as follows:

maxList([H|T], Max) :-
    maxList(T, H, Max).

maxList([], Max, Max).
maxList([H|T], Max0, Max) :-
    Max1 is max(H, Max0),
    maxList(T, Max1, Max).

?- maxList([1,2,3],X).
X = 3.

max/2 simply returns the max between two arguments. A possible implementation for max/2 could be:

myMax(M,A,B):-
    A > B ->  M = A;
    M = B.

?- myMax(A,1,2).
A = 2.

BTW, there is already a built in predicate in SWI to do this, which is called max_list/2 (the code I posted before actually comes from this implementation):

?- max_list([1,2,3],X).
X = 3.
1
votes

Another possible implementation, not relying on an auxiliary predicate, can be done according to the following logic:

  1. If the list contains exactly one element, then it is the maximum.
  2. If the list L contains more than one element, i.e. it is of the form [H|T], and the greatest element of T is M, then the greatest element of L will be H if H>=M, otherwise it will be M.

A rough encoding could be:

maxList([X],X).
maxList([H|T],H) :-
  maxList(T,M),
  H >= M.
maxList([H|T],M) :-
  maxList(T,M),
  H < M.

This leaves room for improvement, but respects the logic above stated and returns the greatest element for each non-empty integer list.