给定一个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).
由于你正在使用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的第一条规则是处理空列表.如果您不想包含该情况,则只需省略该规则.第二个规则调用谓词list_ascendings_/3,其枢轴值(X0)小于列表的头部,因此后者包含在逐步升序元素的子列表中.大于关系的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]
请注意,如果第一个参数是基础的,则谓词会确定性地成功(没有选择点保持打开,因此无需;在唯一解决方案之后按下).您也可以提出相反的问题:哪些列表具有[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 ?
...
显然,这个问题有很多答案.但是,以更公平的顺序得到答案会很好,这就是长度为7的列表中长度为6的列表的所有答案,依此类推.您可以通过为查询添加目标长度/ 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 ? ;
...
您还可以通过L使用ins/2 限制域的元素并标记它来获得具体数字的答案.例如:长度为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]
另一方面,如果你的意思是一个谓词同时执行这两个操作(请参阅下面的最后一个查询),则需要进行一些更改.首先,您需要为降序子列表添加关系的reifying版本:
#>(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的第一个参数调用指定的relation(Rel)以及pivot值(X0)和列表的头部(X).需要注意的是呼叫缺少最后一个参数(真值),就像第一个参数if_/3在list_ascendings_/3和list_descendings_/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 = #<
你犯了几个小错误：
temp不是有效的变量名称，它需要是Temp，_当输入列表为空时，这不是正确的结果，它需要是[]，[XH|Y]构造不是您在扩展列表时与递归调用统一的。传递一个新变量，例如R，然后Y通过统一构建Y = [XH|R]这是应用了修复程序的程序：
local_max([],[],_).
local_max([XH|XT],Y,Temp) :-
( XH =< Temp ->
local_max(XT,Y,Temp)
;
local_max(XT,R,XH), Y = [XH|R]
).
这会产生您预期的输出（演示）。