Prolog - simple prolog problem

Author

simple prolog problem

jongoldsmith@gmail.com

2006-05-01, 10:01 pm

I'm just learning prolog and trying to write statements that will
return the smallest number in a list. The part I can't figure out is a
good way to either keep track of the smallest number by comparing it to
each element in the list or by doing it recursively and then doing the
comparisons on the way back out. I've tried to do it both ways and have
failed.
Any help or tips would be greatly appreciated.
Here is my latest try:

min_list([X|[]],X).
min_list([X|Y],N) :- min_list2(Y,N), X =< N, ! , X.
min_list([X|Y],N) :- min_list2(Y,N), X > N, N.

Thorsten Winterer

2006-05-02, 4:02 am

> min_list([X|[]],X).
> min_list([X|Y],N) :- min_list2(Y,N), X =< N, ! , X.
> min_list([X|Y],N) :- min_list2(Y,N), X > N, N.

This doesn't work for two reasons: you named the predicate min_list/2,
but in the body of clauses 2 and 3, you call a predicate min_list2/2,
which is undefined. Also, the variables at the end of the bodies will
cause errors. With minimal changes, your predicate should look like
this:

min_list2([X|[]],X).
min_list2([X|Y],X) :- min_list2(Y,N), X =< N, !.
min_list2([X|Y],N) :- min_list2(Y,N), X > N.

Note the X in the head of clause 2.

However, you use recursion in both clauses 2 and 3, which is bad: you
will unnecessarily go through the list again. When the check X=<N
fails, you already know that N should be returned as the minimum, so
you should join the two clauses together, like this:

minlist1([X], X) :- !.
minlist1([X | Xs], O) :- minlist1(Xs, I), min(I, X, O).

min(X1, X2, X1) :- X1 =< X2, !.
min(_, X2, X2).

Although for performance reasons you should use tail recursion and keep
track of the minimum:

minlist2([X | Xs], Min) :- minlist3([X | Xs], X, Min).
minlist3([], X, X).
minlist3([X | Xs], I, O) :- X < I, !, minlist3(Xs, X, O).
minlist3([_ | Xs], I, O) :- minlist3(Xs, I, O).

Markus Triska

2006-05-02, 7:04 pm

Thorsten Winterer wrote:
>
> minlist2([X | Xs], Min) :- minlist3([X | Xs], X, Min).
> minlist3([], X, X).
> minlist3([X | Xs], I, O) :- X < I, !, minlist3(Xs, X, O).
> minlist3([_ | Xs], I, O) :- minlist3(Xs, I, O).
>

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

Sponsored Links