Why does my min() function in Prolog not work?

Question

This is my min() function in Prolog that should find the smallest element in a list of numbers. My idea was to test that the Result is smaller or equal to every element in the list. The head of the list is removed until it is empty. When this point is reached, the set in result was correct.

min([], Result).
min([Head|Tail], Result) :-
    Result =< Head,
    min(Tail, Result).

When consulting this file in SWI-Prolog, it can test if a value is the minimal element with min([5, 3, 7, 6], 3) which returns true. But min([5, 3, 7, 6], X) does not find a value for X but just returns true.

How can I make it find the value for X?

Answer 1

The min of an empty list can't be set. You can just write

min([X], X). 

hoping that X is an integer ; I assume it is ! then

min([Head|Tail], Result) :-
    % you fetch the min of the rest of the list
    min(Tail, R1),
    (Head < R1
    -> Result = Head
    ;  Result = R1).

Answer 2

My SWI-Prolog reports

?- min([5, 3, 7, 6], X).
ERROR: user://1:18:
    =</2: Arguments are not sufficiently instantiated

which makes sense as the first X =< 3 is performed with unbound X. To make the predicate work, you need to follow the definition of minimum, which is not defined for empty lists:

min([X], X).
min([X|L], Min) :-
    L = [_|_],    % non-empty tail; could be replaced by a cut
    min(L, MinL),
    Min is min(X, MinL).

(Note that the final line backs off to the built-in min, which is evaluated by is.)

Alternatively, you can take minima of pairs of elements, giving

min([X], X).
min([X,Y|L], Min) :-
    MinXY is min(X, Y),
    min([MinXY|L], Min).

This version is tail-recursive.

Answer 3

If you turn tracing on you can see what's wrong with your script.

1 ?- trace.
true.

Original version:

/** Version 0 */
min([], Result).
min([Head|Tail], Result) :-
    Result =< Head,
    min(Tail, Result).

Output:

[trace] 2 ?- min([5,3,7,6],X).
   Call: (6) min([5, 3, 7, 6], _G4129) ? creep
   Call: (7) _G4129=<5 ? creep
ERROR: =</2: Arguments are not sufficiently instantiated
   Exception: (7) _G4129=<5 ? creep

You're trying to compare an unistantiated variable with 5. Solution: swap lines in the script so that the variable is instantiated before the comparison.

/** Version 1 */
min([], Result).
min([Head|Tail], Result) :-
    min(Tail, Result),
    Result =< Head.

Output:

[trace] 5 ?- min([5,3,7,6],X).
   Call: (6) min([5, 3, 7, 6], _G517) ? creep
   Call: (7) min([3, 7, 6], _G517) ? creep
   Call: (8) min([7, 6], _G517) ? creep
   Call: (9) min([6], _G517) ? creep
   Call: (10) min([], _G517) ? creep
   Exit: (10) min([], _G517) ? creep
   Call: (10) _G517=<6 ? creep
ERROR: =</2: Arguments are not sufficiently instantiated
   Exception: (10) _G517=<6 ?
[trace] 102 ?- min([5,3,7,6],X).
   Call: (6) min([5, 3, 7, 6], _G3067) ? creep
   Call: (7) min([3, 7, 6], _G3067) ? creep
   Call: (8) min([7, 6], _G3067) ? creep
   Call: (9) min([6], _G3067) ? creep
   Call: (10) min([], _G3067) ? creep
   Exit: (10) min([], _G3067) ? creep
   Call: (10) _G3067=<6 ? creep
ERROR: =</2: Arguments are not sufficiently instantiated
   Exception: (10) _G3067=<6 ? 

This way the script goes a bit further but when computing the minimum of the tail it reaches a comparison with an unistantiated variable again. Solution: change min([], Result). to min([Result], Result).

/** version 2 */   
min([Result], Result).
min([Head|Tail], Result) :-
    min(Tail, Result),
    Result =< Head.

Output:

[trace] 8 ?- min([5,3,7,6],3).
   Call: (6) min([5, 3, 7, 6], 3) ? creep
   Call: (7) min([3, 7, 6], 3) ? creep
   Call: (8) min([7, 6], 3) ? creep
   Call: (9) min([6], 3) ? creep
   Call: (10) min([], 3) ? creep
   Fail: (10) min([], 3) ? creep
   Fail: (9) min([6], 3) ? creep
   Fail: (8) min([7, 6], 3) ? creep
   Fail: (7) min([3, 7, 6], 3) ? creep
   Fail: (6) min([5, 3, 7, 6], 3) ? creep
false.

The program now only returns false. This is because you only consider the case the minimum of the tail is smaller than or equal than the head. This program will only return a correct result when the input list is sorted decreasingly (so that the minimum of the tail is smaller than the head, recursively).

[trace] 10 ?- min([5,4,3,2],X).
   Call: (6) min([5, 4, 3, 2], _G2469) ? creep
   Call: (7) min([4, 3, 2], _G2469) ? creep
   Call: (8) min([3, 2], _G2469) ? creep
   Call: (9) min([2], _G2469) ? creep
   Exit: (9) min([2], 2) ? creep
   Call: (9) 2=<3 ? creep
   Exit: (9) 2=<3 ? creep
   Exit: (8) min([3, 2], 2) ? creep
   Call: (8) 2=<4 ? creep
   Exit: (8) 2=<4 ? creep
   Exit: (7) min([4, 3, 2], 2) ? creep
   Call: (7) 2=<5 ? creep
   Exit: (7) 2=<5 ? creep
   Exit: (6) min([5, 4, 3, 2], 2) ? creep
X = 2 .

So you need to take care of the case when the minimum of the tail is strictly greater than the head by adding the clause:

min([Head|Tail], Result) :-
    min(Tail, R1),
    Head < R1,
    Result is Head.

And here's the final version:

/** version 3 */
min([Result], Result).
min([Head|Tail], Result) :-
    min(Tail, Result),
    Result =< Head.

min([Head|Tail], Result) :-
    min(Tail, R1),
    Head < R1,
    Result is Head.

(turn tracing off with nodebug.)

Answer 4

It couldn't possibly have returned true there. X =< 3 causes "ERROR: =</2: Arguments are not sufficiently instantiated". Perhaps you used @=< for comparison, but with it X @=< 3 just succeeds, without instantiating X in any way. So X would get passed unchanged, and min([], X) would just finally succeed - exactly what you've observed.

Your code is wrong in another way too. min([5, 3, 7, 6], 0) succeeds too, and it shouldn't.

others provided you with recursive solutions. For an iterative one, we typically add another, accumulating argument, and pass the Result down the chain unchanged to receive the final value from the accumulator for us:

min([H|T], Result):- min(T,H,Result).

min([], Result, Result).
min([Head|Tail], M, Result) :-
    M =< Head -> min(Tail, M, Result)
    ;            min(Tail, Head, Result).

Empty list has no minimum value. An argument list's head is used as initial value for the minimum.