0

有人可以清楚地解释为什么 min_of_list 的这种实现（来自 SO 3965054）在序言中起作用：

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

虽然此实现会生成不正确的输出：

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

结语。这行得通。

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

?

我得到的行为是 min_of_list_2 返回列表中的最后一个元素。谢谢。

4

2 回答 2

2

min_of_list_2/2 的第一个子句是可以的，它表示具有单个元素的列表的最小值是该元素。第二个子句不太好：意图似乎是说如果 X 是列表 T 的最小值，并且 X 小于 H，那么 X 也是列表 [H|T] 的最小值，这将如果 compare/3 表现得像一个真正的关系，则按预期工作，但不幸的是它没有：

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

然而，更一般的查询失败了，就好像没有解决方案一样（尽管我们知道至少有一个！）：

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

由于 min_of_list_2/2 的一种典型用法（包括例如在第三个子句中的使用）使第二个参数未实例化，因此您将遇到此问题。如果您在 min_of_list_2/2 的相应递归调用之后发出 compare/3 的所有调用，您的代码将按预期工作。因此，与您发布的其他程序相比，您的谓词不再是尾递归的。应该删除最后一个子句中的 compare/3 调用（在这种情况下 X 是什么？），因为它总是会失败！

于 2012-05-07T21:52:22.713 回答
1

第一个比较列表的前两个元素，然后将 min 再次放入列表中，直到只有一个元素。

第二个...获取列表的头部并与 X 进行比较。X 在第一次调用中未实例化，因此 compare(<,X,_any_number) 将为真。X 不会被实例化，所以同样会重复，直到列表中只有一个元素将被返回*（最后一个）。

'* where returned = 与第二个参数统一。

于 2012-05-07T21:39:30.583 回答