是否可以声明升序列表? [英] Is it possible to declare an ascending list?
问题描述
我可以像这样制作升序整数列表:
?- findall(L,between(1,5,L),List).我知道我也可以使用以下方法生成值:
?- 长度(_,X).但我认为我不能在 findall 中使用它，就像下面的循环一样:
?- findall(X,(length(_,X),X<6),Xs).我还可以使用 clpfd 生成一个列表.
:- use_module(library(clpfd)).list_to_n(N,List) :-长度(列表，N)，列出ins 1..N，all_different(列表)，一次(标签(列表)).或
list_to_n2(N,List) :-长度(列表，N)，列出ins 1..N，链(列表，#<)，标签(列表).最后一种方法对我来说似乎是最好的，因为它是最具声明性的，并且不使用 once/1 或 between/3 或 findall/3等
还有其他方法可以做到这一点吗?在纯"Prolog 中是否有一种声明方式来执行此操作?有没有最好"的方法?
最佳"方式取决于您的具体用例！这是使用 clpfd 的另一种方法:p>
:- use_module(library(clpfd)).我们定义谓词 equidistant_stride/2 正如@mat 在对 a 的先前答案的评论中所建议的那样相关问题:
equidistant_stride([],_).equidistant_stride([Z|Zs],D) :-foldl(equidistant_stride_(D),Zs,Z,_).equidistant_stride_(D,Z1,Z0,Z1) :-Z1 #= Z0+D.基于equidistant_stride/2，我们定义:
consecutive_ascending_integers(Zs) :-equidistant_stride(Zs,1).Continuous_ascending_integers_from(Zs,Z0) :-Zs = [Z0|_],连续升序整数(Zs).Continuous_ascending_integers_from_1(Zs) :-Continuous_ascending_integers_from(Zs,1).让我们运行一些查询！首先，您的原始用例:
?- 长度(Zs,N), Continuous_ascending_integers_from_1(Zs).N = 1，Zs = [1];N = 2, Zs = [1,2];N = 3，Zs = [1,2,3];N = 4，Zs = [1,2,3,4];N = 5, Zs = [1,2,3,4,5]...使用 clpfd，我们可以问的很笼统查询 - 并获得逻辑合理的答案！
<上一页>?- Continuous_ascending_integers([A,B,0,D,E]).A = -2，B = -1，D = 1，E = 2.?- Continuous_ascending_integers([A,B,C,D,E]).A+1#=B，B+1#=C，C+1#=D，D+1#=E.<小时>
equidistant_stride/2 的替代实现:
我希望新代码更好地利用约束传播.
感谢@WillNess 提出了促使这次重写的测试用例！
equidistant_from_nth_stride([],_,_,_).equidistant_from_nth_stride([Z|Zs],Z0,N,D) :-Z #= Z0 + N*D,N1 #= N+1,equidistant_from_nth_stride(Zs,Z0,N1,D).等距步幅([]，_).equidistant_stride([Z0|Zs],D) :-equidistant_from_nth_stride(Zs,Z0,1,D).新旧版本与@mat 的 clpfd 的比较:
首先，旧版本:
?- equidistant_stride([1,_,_,_,14],D)._G1133+D#=14,_G1145+D#=_G1133,_G1157+D#=_G1145,1+D#=_G1157.% 成功使用 Scheinlösung?- equidistant_stride([1,_,_,_,14|_],D)._G1136+D#=14, _G1148+D#=_G1136, _G1160+D#=_G1148, 1+D#=_G1160;14+D#=_G1340, _G1354+D#=14, _G1366+D#=_G1354, _G1378+D#=_G1366, 1+D#=_G1378... % 不会普遍终止现在让我们切换到新版本，问同样的问题！
<上一页>?- equidistant_stride([1,_,_,_,14],D).错误.% 失败，因为它应该?- equidistant_stride([1,_,_,_,14|_],D).错误.% 失败，因为它应该<小时>
更多，现在，再次！我们可以通过尝试性地使用冗余约束来更早地失败吗?
之前，我们建议使用约束 Z1 #= Z0+D*1, Z2 #= Z0+D*2, Z3 #= Z0+D*3 而不是 Z1 #=Z0+D, Z2 #= Z1+D, Z3 #= Z2+D(这个答案中的第一个版本的代码就是这样做的).
再次感谢 @WillNess 通过注意到目标 equidistant_stride([_,4,_,_,14],D) 不会失败，而是会成功完成未决目标:
?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D).Zs = [_G2650, 4, _G2656, _G2659, 14],14#=_G2650+4*D,_G2659#=_G2650+3*D,_G2656#=_G2650+2*D,_G2650+D#=4.让我们用 equidistantRED_stride/2 添加一些冗余约束:
equidistantRED_stride([],_).等距RED_stride([Z|Zs],D) :-equidistant_from_nth_stride(Zs,Z,1,D),等距RED_stride(Zs，D).示例查询:
?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D), equidistantRED_stride(Zs,D).错误的.完成了吗?还没有！一般来说，我们不想要二次数量的冗余约束.原因如下:
?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D).Zs = [_G2683, _G2686, _G2689, _G2692, 14],14#=_G2683+4*D,_G2692#=_G2683+3*D,_G2689#=_G2683+2*D,_G2686#=_G2683+D.?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D), equidistantRED_stride(Zs,D).Zs = [_G831, _G834, _G837, _G840, 14],14#=_G831+4*D,_G840#=_G831+3*D,_G837#=_G831+2*D,_G834#=_G831+D,14#=_G831+4*D,_G840#=_G831+3*D,_G837#=_G831+2*D,_G834#=_G831+D,D+_G840#=14,14#=2*D+_G837,_G840#=D+_G837,14#=_G834+3*D,_G840#=_G834+2*D,_G837#=_G834+D.但是，如果我们使用双重否定技巧，那么在成功的情况下，余数仍然存在......
?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D).Zs = [_G454, _G457, _G460, _G463, 14],14#=_G454+4*D,_G463#=_G454+3*D,_G460#=_G454+2*D,_G457#=_G454+D....和...
<上一页>?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D).错误....我们检测到的失败案例比以前更多！
<小时>让我们再深入一点！我们能否在更通用的用途中及早发现故障?
到目前为止，这两个逻辑错误的查询不会终止:
<上一页>?- Zs = [_,4,_,_,14|_], + + equidistantRED_stride(Zs,D), equidistant_stride(Zs,D).... % 执行中止?- Zs = [_,4,_,_,14|_], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D).... % 执行中止解决了吗?被黑了！
<上一页>?- 使用模块(库(lambda)).真的.?- Zs = [_,4,_,_,14|_],+ ( term_variables(Zs,Vs),maplist(X^when(nonvar(X),integer(X)),Vs),+ 等距RED_stride(Zs,D)),equidistant_stride(Zs,D).错误.hack 不能保证冗余约束部分"的终止，但 IMO 对于快速的第一枪来说还不错.在 Zs 中实例化任何变量时的测试 integer/1 意味着允许 clpfd 求解器将变量域约束为单例，而使用 cons-pairs 进行实例化(直接导致基于列表的谓词不终止)被压制了.
我确实意识到黑客可以通过多种方式很容易地破解(例如，使用循环术语).欢迎任何建议和意见！
I can make lists of ascending integer like so:
?- findall(L,between(1,5,L),List).
I know I can also generate values using:
?- length(_,X).
But I don't think I can use this in a findall, as things like the following loop:
?- findall(X,(length(_,X),X<6),Xs).
I can also generate a list using clpfd.
:- use_module(library(clpfd)).
list_to_n(N,List) :-
length(List,N),
List ins 1..N,
all_different(List),
once(label(List)).
or
list_to_n2(N,List) :-
length(List,N),
List ins 1..N,
chain(List,#<),
label(List).
The last method seems best to me as it is the most declarative, and does not use once/1 or between/3 or findall/3 etc.
Are there other ways to do this? Is there a declarative way to do this in 'pure' Prolog? Is there a 'best' way?
The "best" way depends on your concrete use cases! Here's another way to do it using clpfd:
:- use_module(library(clpfd)).
We define predicate equidistant_stride/2 as suggested by @mat in a comment to a previous answer of a related question:
equidistant_stride([],_).
equidistant_stride([Z|Zs],D) :-
foldl(equidistant_stride_(D),Zs,Z,_).
equidistant_stride_(D,Z1,Z0,Z1) :-
Z1 #= Z0+D.
Based on equidistant_stride/2, we define:
consecutive_ascending_integers(Zs) :-
equidistant_stride(Zs,1).
consecutive_ascending_integers_from(Zs,Z0) :-
Zs = [Z0|_],
consecutive_ascending_integers(Zs).
consecutive_ascending_integers_from_1(Zs) :-
consecutive_ascending_integers_from(Zs,1).
Let's run some queries! First, your original use case:
?- length(Zs,N), consecutive_ascending_integers_from_1(Zs).
N = 1, Zs = [1]
; N = 2, Zs = [1,2]
; N = 3, Zs = [1,2,3]
; N = 4, Zs = [1,2,3,4]
; N = 5, Zs = [1,2,3,4,5]
...
With clpfd, we can ask quite general queries—and get logically sound answers, too!
?- consecutive_ascending_integers([A,B,0,D,E]). A = -2, B = -1, D = 1, E = 2. ?- consecutive_ascending_integers([A,B,C,D,E]). A+1#=B, B+1#=C, C+1#=D, D+1#=E.
An alternative implementation of equidistant_stride/2:
I hope the new code makes better use of constraint propagation.
Thanks to @WillNess for suggesting the test-cases that motivated this rewrite!
equidistant_from_nth_stride([],_,_,_).
equidistant_from_nth_stride([Z|Zs],Z0,N,D) :-
Z #= Z0 + N*D,
N1 #= N+1,
equidistant_from_nth_stride(Zs,Z0,N1,D).
equidistant_stride([],_).
equidistant_stride([Z0|Zs],D) :-
equidistant_from_nth_stride(Zs,Z0,1,D).
Comparison of old vs new version with @mat's clpfd:
First up, the old version:
?- equidistant_stride([1,_,_,_,14],D).
_G1133+D#=14,
_G1145+D#=_G1133,
_G1157+D#=_G1145,
1+D#=_G1157. % succeeds with Scheinlösung
?- equidistant_stride([1,_,_,_,14|_],D).
_G1136+D#=14, _G1148+D#=_G1136, _G1160+D#=_G1148, 1+D#=_G1160
; 14+D#=_G1340, _G1354+D#=14, _G1366+D#=_G1354, _G1378+D#=_G1366, 1+D#=_G1378
... % does not terminate universally
Now let's switch to the new version and ask the same queries!
?- equidistant_stride([1,_,_,_,14],D). false. % fails, as it should ?- equidistant_stride([1,_,_,_,14|_],D). false. % fails, as it should
More, now, again! Can we fail earlier by tentatively employing redundant constraints?
Previously, we proposed using constraints Z1 #= Z0+D*1, Z2 #= Z0+D*2, Z3 #= Z0+D*3 instead of Z1 #= Z0+D, Z2 #= Z1+D, Z3 #= Z2+D
(which the 1st version of code in this answer did).
Again, thanks to @WillNess for motivating this little experiment by
noting that the goal equidistant_stride([_,4,_,_,14],D) does not fail but instead succeeds with pending goals:
?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D).
Zs = [_G2650, 4, _G2656, _G2659, 14],
14#=_G2650+4*D,
_G2659#=_G2650+3*D,
_G2656#=_G2650+2*D,
_G2650+D#=4.
Let's add some redundant constraints with equidistantRED_stride/2:
equidistantRED_stride([],_).
equidistantRED_stride([Z|Zs],D) :-
equidistant_from_nth_stride(Zs,Z,1,D),
equidistantRED_stride(Zs,D).
Sample query:
?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D), equidistantRED_stride(Zs,D).
false.
Done? Not yet! In general we don't want a quadratic number of redundant constraints. Here's why:
?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D).
Zs = [_G2683, _G2686, _G2689, _G2692, 14],
14#=_G2683+4*D,
_G2692#=_G2683+3*D,
_G2689#=_G2683+2*D,
_G2686#=_G2683+D.
?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D), equidistantRED_stride(Zs,D).
Zs = [_G831, _G834, _G837, _G840, 14],
14#=_G831+4*D,
_G840#=_G831+3*D,
_G837#=_G831+2*D,
_G834#=_G831+D,
14#=_G831+4*D,
_G840#=_G831+3*D,
_G837#=_G831+2*D,
_G834#=_G831+D,
D+_G840#=14,
14#=2*D+_G837,
_G840#=D+_G837,
14#=_G834+3*D,
_G840#=_G834+2*D,
_G837#=_G834+D.
But if we use the double-negation trick, the residuum remains in cases that succeed ...
?- Zs = [_,_,_,_,14], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D).
Zs = [_G454, _G457, _G460, _G463, 14],
14#=_G454+4*D,
_G463#=_G454+3*D,
_G460#=_G454+2*D,
_G457#=_G454+D.
... and ...
?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D). false.
... we detect failure in more cases than we did before!
Let's dig a little deeper! Can we detect failure early in even more generalized uses?
With code presented so far, these two logically false queries do not terminate:
?- Zs = [_,4,_,_,14|_], + + equidistantRED_stride(Zs,D), equidistant_stride(Zs,D). ... % Execution Aborted ?- Zs = [_,4,_,_,14|_], equidistant_stride(Zs,D), + + equidistantRED_stride(Zs,D). ... % Execution Aborted
Got fix? Got hack!
?- use_module(library(lambda)).
true.
?- Zs = [_,4,_,_,14|_],
+ ( term_variables(Zs,Vs),
maplist(X^when(nonvar(X),integer(X)),Vs),
+ equidistantRED_stride(Zs,D)),
equidistant_stride(Zs,D).
false.
The hack doesn't guarantee termination of the redundant constraint "part", but IMO it's not too bad for a quick first shot. The test integer/1 upon instantiation of any variable in Zs is meant to allow the clpfd solver to constrain variable domains to singletons, while the instantiation with cons-pairs (which directly leads to non-termination of list-based predicates) is suppressed.
I do realize that the hack can be broken quite easily in more than one way (e.g., using cyclic terms). Any suggestions and comments are welcome!
这篇关于是否可以声明升序列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
