在Prolog列表中查找逐渐变大的元素

Question

给定一个Prolog列表，我想创建一个第二个列表，其中包含逐渐变大的元素。例如：

L = [ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ]

Answer = [ 1, 5, 10, 15, 20 ]

我的代码：

local_max([],_,_).
local_max([XH|XT],Y,temp) :-
    ( XH =< temp ->
      local_max(XT,Y,temp)
      ;
      local_max(XT,[XH|Y],XH)
    ).

我以为这应该简单地将我的答案反转，但事实并非如此。

列表仅包含正整数，所以我只是做了

local_max([ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ],Answer,0).

- cgss

Answer 1

由于您正在使用Prolog的(;)/2 - if-then-else来完成任务，因此您可能需要考虑if_/3。此外，通过使用CLP(FD)（有关详细信息，请参见Swi-Prolog手册中的CLP(FD)条目），可以使该谓词更加通用。并且我建议使用一个带有两个参数的调用谓词，即逐渐上升元素的列表和子列表。为了强调谓词的关系性质，让我们给它一个更具描述性的名称，比如list_ascendings/2:

:- use_module(library(clpfd)).

list_ascendings([],[]).
list_ascendings([X|Xs],A) :-
   X0 #= X-1,
   list_ascendings_([X|Xs],A,X0).

list_ascendings/2 的第一条规则是处理空列表的。如果你不想包括该情况，可以省略该规则。第二条规则使用一个小于列表头部的支点值 (X0) 调用谓词 list_ascendings_/3，因此后者被包含在逐渐增加元素子列表中。一个 reifying 版本的比较运算符（作为 if_/3 的第一个参数）可以定义如下：

bool_t(1,true).
bool_t(0,false).

#<(X,Y,Truth)  :- X #< Y #<==> B, bool_t(B,Truth).

在此基础上，描述实际关系的谓词可以定义如下：

list_ascendings_([],[],_).
list_ascendings_([X|Xs],A,X0) :-
   if_(X0#<X, (A=[X|As], X1=X), (A=As, X1=X0)), 
   list_ascendings_(Xs,As,X1).

根据枢轴值是否小于列表头部的情况，升序元素列表（A）和新的枢轴值（X1）会有不同的描述。

现在让我们来看看谓词是如何工作的。您的示例查询将产生所需的结果：

   ?- list_ascendings([1,5,2,3,4,10,15,11,12,13,20],A).
A = [1,5,10,15,20]

请注意，如果第一个参数是grounded（没有选择点保留，因此在唯一解之后无需按;），则谓词会确定性地成功。你还可以问相反的问题：哪些列表以[1,5,10,15,20]作为最大递增子列表？

   ?- list_ascendings(L,[1,5,10,15,20]).
L = [1,5,10,15,20] ? ;
L = [1,5,10,15,20,_A],
_A in inf..20 ? ;
L = [1,5,10,15,20,_A,_B],
_A in inf..20,
_B in inf..20 ? 
...

显然这个问题有无限多个答案。但是，希望按照一个更公平的顺序获得答案，即所有长度为6的列表的答案都排在长度为7的列表之前等等。您可以通过在查询前加上目标长度/2来实现这一点：

   ?- length(L,_), list_ascendings(L,[1,5,10,15,20]).
L = [1,5,10,15,20] ? ;
L = [1,5,10,15,20,_A],
_A in inf..20 ? ;
L = [1,5,10,15,_A,20],
_A in inf..15 ? ;
L = [1,5,10,_A,15,20],
_A in inf..10 ? ;
...
L = [1,5,10,15,20,_A,_B],
_A in inf..20,
_B in inf..20 ? ;
L = [1,5,10,15,_A,20,_B],
_A in inf..15,
_B in inf..20 ? ;
L = [1,5,10,15,_A,_B,20],
_A in inf..15,
_B in inf..15 ? ;
...

您还可以通过使用 ins/2 限制 L 的元素域并对其进行标记来获得具体数字的答案。例如：长度为 7，数字在 0 到 20 之间的列表有哪些，使得 [1,5,10,15,20] 是最大递增子列表？ 相应的查询将提供所有 1997 个答案：

   ?- length(L,7), L ins 0..20, list_ascendings(L,[1,5,10,15,20]), label(L).
L = [1,5,10,15,20,0,0] ? ;
L = [1,5,10,15,20,0,1] ? ;
L = [1,5,10,15,20,0,2] ? ;
...
L = [1,5,10,15,20,2,15] ? ;
...
L = [1,0,5,10,4,15,20] ? ;
...

编辑：

关于你在评论中的问题，从升序版本描述逐步降级子列表其实很简单。你只需要稍微修改两个目标：

list_descendings([],[]).
list_descendings([X|Xs],A) :-
   X0 #= X+1,                                     % <- change
   list_descendings_([X|Xs],A,X0).

list_descendings_([],[],_).
list_descendings_([X|Xs],A,X0) :-
   if_(X#<X0, (A=[X|As], X1=X), (A=As, X1=X0)),   % <- change
   list_descendings_(Xs,As,X1).

这将产生所期望的结果：

   ?- list_descendings([20,15,3,5,7,8,2,6,2],A).
A = [20,15,3,2]

另一方面，如果您指的是一个同时执行两个谓词的谓词（请参见下面的最后一个查询），则需要进行更多更改。首先，您需要添加一个关于降序子列表的关系的再现版本：

#>(X,Y,Truth)  :- X #> Y #<==> B, bool_t(B,Truth).

由于升序和降序子列表的第一个中心值计算方式不同，因此将其委派给一个新的谓词是合适的：

x_pivot_wrt(X,X0,#>) :- X0 #= X+1.
x_pivot_wrt(X,X0,#<) :- X0 #= X-1.

接下来，调用谓词需要一个额外的参数来指定子列表所应该进展的关系。最好将其重命名以反映其新行为：

list_progressives_wrt([],[],_).
list_progressives_wrt([X|Xs],P,Rel) :-
   x_pivot_wrt(X,X0,Rel),
   list_progressives_wrt_([X|Xs],P,Rel,X0).

最后，描述实际关系的谓词也有一个额外的参数，即指定的关系。在if_/3的第一个参数中，调用了指定的关系(Rel)，以及枢轴值(X0)和列表的头部(X)。请注意，此调用缺少最后一个参数(真值)，就像list_ascendings_/3和list_descendings_/3中if_/3的第一个参数一样。

list_progressives_wrt_([],[],_,_).
list_progressives_wrt_([X|Xs],P,Rel,X0) :-
   if_(call(Rel,X0,X), (P=[X|Ps], X1=X), (P=Ps, X1=X0)),
   list_progressives_wrt_(Xs,Ps,Rel,X1).

您的示例所对应的查询产生了所需的结果：

   ?- list_progressives_wrt([1,5,2,3,4,10,15,11,12,13,20],P,#<).
P = [1,5,10,15,20]

由于可以在x_pivot_wrt/3中指定要查询的关系，因此您可以通过将最后一个参数留空来请求两个变体：

   ?- list_progressives_wrt([20,15,3,21,5,7,8,2,6,30,2],P,Rel).
P = [20,15,3,2],
Rel = #> ? ;
P = [20,21,30],
Rel = #<

- tas

---

谢谢你的回答。尽管我对你使用的所有谓词都不熟悉（还没有见过if/3），但我理解这很好。而且，使谓词具有灵活性也很有趣。我承认在我的情况下无法使用它，但我会稍微研究一下。编辑：我已经为执行降序操作创建了第二个谓词。所以，你认为像你一样使用布尔值来实现两种排序方式在谓词中是可能的吗？再次感谢！ - cgss

@cgss：我更新了我的答案以回答那个问题。 - tas

谢谢，真棒！到目前为止，我一直觉得编写通用谓词很困难，但是您解释得非常透彻。 - cgss

Answer 2

您犯了几个小错误：

• temp 不是一个有效的变量名，需要改为 Temp，
• 当输入列表为空时，_ 不是正确的结果，需要改为 []，
• 在扩展列表上进行递归调用时，[XH|Y] 结构不是您要统一的内容。请传递一个新变量，比如说 R，然后通过统一 Y = [XH|R] 来构建 Y。

以下是已应用修复的程序：

local_max([],[],_).
local_max([XH|XT],Y,Temp) :-
    ( XH =< Temp ->
      local_max(XT,Y,Temp)
      ;
      local_max(XT,R,XH), Y = [XH|R]
    ).

这将产生您期望的输出（演示）。

- Sergey Kalinichenko

---

我的前两个错误真的很愚蠢。但是，就第三个错误而言，虽然我理解了你的代码是如何工作的（并且它确实有效，我已经接受了你的答案），你能否请解释一下为什么我的代码不能统一吗？ - cgss

@cgss 递归需要在某个地方“触底反弹”，因此从 local_max(XT,[XH|Y],XH) 中的 [XH|Y] 到某个点，需要与 local_max([],[],_) 中的 [] 统一，但是它无法统一，因为列表 [XH|Y] 至少有一个元素，而列表 [] 没有任何元素。 - Sergey Kalinichenko

是的，我明白了。我必须承认，我没有考虑到这一点，因为我太专注于我的原始代码了。我认为当原始列表为空时，它就完成了，尽管Prolog无法将[a]与_（就像您提到的它无法将[a]与[]）统一起来。我理解了这一点； - cgss