Search code examples
prolog

Prolog recursion trouble - minimum value in list

I have been given a task as follows:

Write a predicate to determine the minimum element in a list. This predicate should not match any value for an empty list, should work with both positive and negative values and should not introduce an artificial minimum value.

I have worked through the recursive logic on paper and came up with the following code as a solution. It fails immediately.

min_val([H], H).
min_val([H|T], M) :- min_val(T, M1), H =< M1, M is H.

If someone could please explain where I have gone wrong, that would be most appreciated.

Solution

  • In your code you should ask yourself what if H > M1?

    Try this instead:

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

    If you prefer cuts then this is better:

    min_val([H], H).
min_val([H|T], H) :- min_val(T, M), H < M, !.
min_val([_|T], M) :- min_val(T, M).