Prolog, find minimum in a list

Question

in short: How to find min value in a list? (thanks for the advise kaarel)

long story:

I have created a weighted graph in amzi prolog and given 2 nodes, I am able to retrieve a list of paths. However, I need to find the minimum value in this path but am unable to traverse the list to do this. May I please seek your advise on how to determine the minimum value in the list?

my code currently looks like this:

arc(1,2).
arc(2,3).
arc(3,4).
arc(3,5).
arc(3,6).
arc(2,5).
arc(5,6).
arc(2,6).

path(X,Z,A) :- 
 (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1).

thus, ' keying findall(Z,path(2,6,Z),L).' in listener allows me to attain a list [3,2,2,1]. I need to retrieve the minimum value from here and multiply it with an amount. Can someone please advise on how to retrieve the minimum value? thanks!

Answer 1

It is common to use a so-called "lagged argument" to benefit from first-argument indexing:

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).

This pattern is called a fold (from the left), and foldl/4, which is available in recent SWI versions, lets you write this as:

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

num_num_min(X, Y, Min) :- Min is min(X, Y).

---

---

Notice though that this cannot be used in all directions, for example:

?- list_min([A,B], 5).
is/2: Arguments are not sufficiently instantiated

If you are reasoning about integers, as seems to be the case in your example, I therefore recommend you use CLP(FD) constraints to naturally generalize the predicate. Instead of (is)/2, simply use (#=)/2 and benefit from a more declarative solution:

:- use_module(library(clpfd)).

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

num_num_min(X, Y, Min) :- Min #= min(X, Y).

This can be used as a true relation which works in all directions, for example:

?- list_min([A,B], 5).

yielding:

A in 5..sup,
5#=min(B, A),
B in 5..sup.

Answer 2

This looks right to me (from here).

min_in_list([Min],Min).                 % We've found the minimum

min_in_list([H,K|T],M) :-
    H =< K,                             % H is less than or equal to K
    min_in_list([H|T],M).               % so use H

min_in_list([H,K|T],M) :-
    H > K,                              % H is greater than K
    min_in_list([K|T],M).               % so use K