list - 获取列表的最小值

Question

我试图找到一个列表的最小值（作为学习经验，所以没有min）。

我的方法如下：

minimo([X], X).
minimo([X,Y|Tail], N):-
    (X > Y, minimo([Y,Tail], Y));
    (X <= Y, minimo([X,Tail], X)).

这给了我以下错误：

语法错误：应为运算符

所以我的问题是：

• 是什么导致语法错误？
• 如果它确实返回了正确的值，我会在修复后自己尝试，但这实际上是一种正确的方法吗？

提前致谢。

Answer 1

您的程序中有几个错误：

1. 正如 Joe Lehmann 所指出的，没有'<='/2. 一定是'=<'/2。

2. 当您minimo/2递归调用时，您构建的列表是错误的。而不是[Y,Tail]使用[Y|Tail]. 否则，您会得到一个列表，其中列表作为第二个元素。

3. 您将递归调用的第二个参数绑定minimo/2到Yor X。相反，它必须绑定到N. 否则，您N将永远不会被实例化。

您可以通过添加削减或使用 if-then-else ( '->'+ ;) 来进一步改进您的程序：

minimo([X], X) :- !.
minimo([X,Y|Tail], N):-
    ( X > Y ->
        minimo([Y|Tail], N)
    ;
        minimo([X|Tail], N)
    ).

Answer 2

除了已经发布的其他版本之外，还可以考虑没有 if-then-else 的版本，并为关系使用更具描述性的名称（将列表与其最小值相关联）：

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

这样的模式称为折叠（从左至右），我们可以使用 `foldl/4 等效地编写它：

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

min_(A, B, Min) :- Min is min(A, B).

示例查询：

?- list_min([1,0,2], Min).
Min = 0.

---

请注意，这不是一个真正的关系，并且由于使用了低级算术，因此不能在所有方向上使用。例如，如果我们尝试在另一个方向使用它，我们会得到：

?- list_min([X,Y], 3)。
错误：is/2：参数没有充分实例化

要使其成为真正的解决方案，请使用clpfd和clpq等约束。例如，对于整数的解：

:- use_module(library(clpfd)).

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

min_(A, B, Min) :- Min #= min(A, B).

这适用于所有方向：

?- list_min([X,Y], 3).
X in 3..sup,
3#=min(Y, X),
Y in 3..sup.

Answer 3

语法错误是，因为 Prolog 中的小于等于 =<，而不是 <=。

我认为这种方法会奏效，但你真的应该避免；在一个子句中。把它分成两个子句。

另外我认为你想在递归中做类似 [X|Tail] 而不是 [X,Tail]

Answer 4

min([H|T], Min) :- min(T, H, Min).

min([], Min, Min).
min([H|T], Min, Min1) :-
  (   H < Min
  ->  min(T, H, Min1)
  ;   min(T, Min, Min1) ).