Getting the minimum value of a list

Question

I am trying to find the minimum value of a list (as a learning experience, so without min).

My approach is the following:

minimo([X], X).
minimo([X,Y|Tail], N):-
    (X > Y, minimo([Y,Tail], Y));
    (X <= Y, minimo([X,Tail], X)).

This gives me the following error:

Syntax error: Operator expected

So my questions are:

• What is causing the syntax error?
• I will try it myself once that is fixed if it actually gives the correct value back, but would this actually be a correct approach?

Thanks in advance.

Answer 1

There are several bugs in your program:

1. as pointed out by Joe Lehmann, there is no '<='/2. It must be '=<'/2.

2. when you call minimo/2 recursively, you construct the lists wrong. Instead of [Y,Tail] use [Y|Tail]. Otherwise, you get a list with a list as second element.

3. you bind the second argument of the recursive call of minimo/2 to Y or X. Instead it must be bound to N. Otherwise, your N will never be instantiated.

You can improve your program further by adding cuts or using if-then-else ('->' + ;):

minimo([X], X) :- !.
minimo([X,Y|Tail], N):-
    ( X > Y ->
        minimo([Y|Tail], N)
    ;
        minimo([X|Tail], N)
    ).

Answer 2

In addition to the other versions posted already, consider also a version without if-then-else, and using a more descriptive name for the relation (which relates a list to its minimum):

list_min([L|Ls], Min) :- list_min(Ls, L, Min).

list_min([], Min, Min).
list_min([L|Ls], Min0, Min) :-
    Min1 is min(L, Min0),
    list_min(Ls, Min1, Min).

Such a pattern is called a fold (from the left), and we can write it equivalently using `foldl/4:

list_min([L|Ls], Min) :- foldl(min_, Ls, L, Min).

min_(A, B, Min) :- Min is min(A, B).

Example query:

?- list_min([1,0,2], Min).
Min = 0.

---

Note though that this is not a true relation and cannot be used in all directions due to the use of low-level arithmetic. For example, if we try to use it in the other direction, we get:

?- list_min([X,Y], 3).
ERROR: is/2: Arguments are not sufficiently instantiated

To make it a true solution, use constraints like clpfd and clpq. For example, for a solution over integers:

:- use_module(library(clpfd)).

list_min([L|Ls], Min) :- foldl(min_, Ls, L, Min).

min_(A, B, Min) :- Min #= min(A, B).

This works in all directions:

?- list_min([X,Y], 3).
X in 3..sup,
3#=min(Y, X),
Y in 3..sup.

Answer 3

The syntax error is, because less or equal in Prolog is =<, not <=.

I think the approach will work, but you really should avoid ; in a clause. Just split it up into two clauses.

Also I think that you want to do something like [X|Tail] in the recursion rather than [X,Tail]

Answer 4

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

min([], Min, Min).
min([H|T], Min, Min1) :-
  (   H < Min
  ->  min(T, H, Min1)
  ;   min(T, Min, Min1) ).