如何找到条款列表中的最小值？

Question

我有一个术语列表如下

[t('L', 76), t('I', 73), t('V', 86), t('E', 69)]

我想在 prolog 中写一个谓词，这样它将 return 具有最小第二值的术语。即从上面的列表中应该 return t('E', 69)

下面是我试过的。但这是行不通的。

minChar(L, Min) :-
    setof(t(_, A), member(t(_, A), L), Li),
    Li = [Min|_].

这是它为上述输入提供的输出。

?- minChar([t('L', 76), t('I', 73), t('V', 86), t('E', 69)], Min).
Min = t(_G14650, 69) ;
Min = t(_G14672, 73) ;
Min = t(_G14683, 76) ;
Min = t(_G14661, 86).

Answer 1

正如 lurker 所说，谓词不能以大写字母开头，所以先解决这个问题。

这里有两个基本问题：首先，第二行中的两个下划线指的是不同的变量，因此 setof/3 不知道您需要在模板中和member/2 电话。

其次，setof 对结果进行排序（这就是为什么您可以像那样提取最小值），但是按照您构建模板的方式，它会错误地排序。 swi-prolog 中的排序使用 standard order of terms definition，在您的例子中，您正在对 t(A, B) 类型的复合项进行排序，其中 A 是原子，B 是数字。这将首先按字典顺序在 A 上排序，然后在 B 上排序，这不是你想要的，你想在 B 上排序。

当您想使用与术语本身不同的键对事物进行排序时，这里的标准技巧是提取您想要的键，将其与 (-)/2 函子绑定，然后对其进行排序.因此，对于您的示例，这应该有效：

minChar(L, Min) :- 
  setof(B-t(A, B), member(t(A, B), L), Li),
  Li = [_-Min|_].

请记住，在 Prolog 中，当您说 X - Y 时，您实际上并没有做任何减法，即使看起来您在做。您只需使用 (-)/2 仿函数将 X 和 Y 绑定在一起。如果您特别要求它，它只会做减法，但是会使用一些强制算术评估的运算符（例如 =:=、<、> 或 is）。这就是 1+1 = 2 在 Prolog 中为假的原因，因为 = 是统一运算符，并且不进行任何算术计算。

明确一点：您没有为此使用 -，您可以使用任何您喜欢的仿函数。但是对于这种事情，传统上使用减函子。

编辑：此外，setof/3 将回溯模板中未找到的任何自由变量，并且由于两个下划线不引用相同的自由变量，因此它将回溯每个可能的赋值第二个下划线，然后丢弃该结果并为第一个下划线分配一个新的自由变量。这就是为什么你可以回溯结果并得到一堆你不知道它们来自哪里的匿名变量。

Answer 2

而不是使用在 O(n log n) 中运行的 setof（至少），您还可以自己编写一个 minChar 谓词:

minChar([X],X) :-
    !.
minChar([t(_,V1)|T],t(A2,V2)) :-
    minChar(T,t(A2,V2)),
    V2 < V1,
    !.
minChar([X|_],X).

或者您可以通过使用累加器进一步提高性能：

minChar([X|T],Min) :-
    minChar(T,X,Min).

minChar([],X,X).
minChar([t(A2,V2)|T],t(_,V1),Min) :-
     V2 < V1,
     !,
     minChar(T,t(A2,V2),Min).
minChar([_|T],X,Min) :-
    minChar(T,X,Min).

代码的工作原理如下：首先将列表统一为[X|T]，（显然必须至少有一个项目，否则没有最小值）。现在您将 X 作为 第一个最小值 。您遍历列表，每次比较 t(A2,V2)（列表的新 head）与 t(A1,V1)（当前找到的最小值）。如果第二个属性 V2 小于 V1，我们知道我们找到了一个新的最小值，我们将继续使用该术语进行搜索。否则，任务将以旧的当前最小值继续。如果我们到达列表的末尾，我们只需 return 当前最小值 。

另一个性能黑客，将空列表案例放在最后一个，并将当前最小值是最小的案例放在第一位：

minChar([t(_,V2)|T],t(A1,V1),Min) :-
     V1 <= V2,
     !,
     minChar(T,t(A1,V1),Min).
minChar([X|T],_,Min) :-
    minChar(T,X,Min).
minChar([],X,X).

这是因为 Prolog 总是首先按照定义的顺序执行谓词。它只会在您到达 空列表 情况（在列表末尾）时发生。而且遗嘱后，找到更小值的几率会大大降低。

Answer 3

您是 Prolog 的初学者，所以请尝试考虑 Prolog。

列表的最小值是多少？此列表中的一个元素，此列表中没有其他元素更小。所以你可以写

my_min(L, Min) :-
    member(Min, L),
    \+((member(X, L), X < Min)).

有人会说："it's not efficient !"。是的，但我认为这是学习 Prolog 的好方法。

您应该根据您的情况调整此代码。

编辑我说适应 :

min_of_list(L, t(X,Y)) :-
    member(t(X, Y), L),
    \+((member(t(_, Z), L), Z < Y)).

如何找到条款列表中的最小值？

How to find the minimum of the list of the terms?

list

prolog

minimum