0

Can someone explain clearly why this implementation (from SO 3965054) of min_of_list works in prolog:

% via: http://stackoverflow.com/questions/3965054/prolog-find-minimum-in-a-list
min_of_list_1( [H], H).
min_of_list_1([H,K|T],M) :- H =< K, min_of_list_1([H|T],M). 
min_of_list_1([H,K|T],M) :- H > K,  min_of_list_1([K|T],M).

while this implementation generates an incorrect output:

min_of_list_2( [H], H).
min_of_list_2( [H| T], X) :- compare(<, X, H), min_of_list_2(T, X).
min_of_list_2( [H| T], H) :- compare(>, X, H), min_of_list_2(T, X).
min_of_list_2( [H| T], H) :- compare(=, X, H), min_of_list_2(T, H).

Epilogue. This works.

min_of_list_3( [H], H).
min_of_list_3( [H| T], X) :- min_of_list_3(T, X), compare(<, X, H).
min_of_list_3( [H| T], H) :- min_of_list_3(T, X), compare(>, X, H).
min_of_list_3( [H| T], H) :- min_of_list_3(T, X), compare(=, X, H).

?

The behavior I get is that min_of_list_2 returns the last element in the list. Thanks.

BlessedKey
  • 1,615
  • 1
  • 10
  • 16

2 Answers2

2

The first clause of min_of_list_2/2 is OK, it says the minimum of a list with a single element is that element. The second clause is not quite so OK: The intention seems to state that if X is the minimum of the list T, and X is smaller than H, then X is also the minimum of the list [H|T], and this would work as intended if compare/3 behaved like a true relation, but unfortunately it doesn't:

?- compare(<, a, b).
true.

Yet the more general query fails as if there were no solution (although we know there is at least one!):

?- compare(<, a, X).
false.

Since one typical usage of min_of_list_2/2 (including for example its use in the third clause) leaves the second argument uninstantiated, you will run into this problem. Your code will work as expected if you place all calls of compare/3 after the respective recursive calls of min_of_list_2/2. As a consequence, your predicate is then no longer tail recursive, in contrast to the other program you posted. The compare/3 call in the last clause should be removed (what is the X in that case?), as it will always fail!

mat
  • 40,498
  • 3
  • 51
  • 78
1

the first one compares the first two elements of the list and then puts the min again in the list till there is only one element.

the second one... takes the head of the list and compares with X. X is non-instantiated in the first call so compare(<,X,_any_number) will be true. X wont be instantiated so the same will repeat till there is only one element in the list which will be returned* (the last one).

'* where returned = unified with the second argument.

Thanos Tintinidis
  • 5,828
  • 1
  • 20
  • 31