能否声明一个升序列表?

5

我可以这样制作升序整数列表:

?- findall(L,between(1,5,L),List).

我知道我也可以使用以下方式生成值:

?- length(_,X).

但我不认为我可以在findall中使用这个,因为像下面的循环一样的东西:

?- findall(X,(length(_,X),X<6),Xs).

我也可以使用生成一个列表。

:- use_module(library(clpfd)).

list_to_n(N,List) :-
   length(List,N),
   List ins 1..N,
   all_different(List),
   once(label(List)).

或者

list_to_n2(N,List) :-
   length(List,N),
   List ins 1..N,
   chain(List,#<),
   label(List).

对我来说,最后一种方法似乎是最好的,因为它是最具声明性的,不使用once/1between/3findall/3等。

还有其他方法可以做到这一点吗?在“纯”Prolog中有没有声明性的方法?是否有“最佳”方法?


谢谢...我有时候会把事情想得太复杂了! - user27815
1
chain(List, #<)恰好做到了你要求的:它可以用于严格升序整数的列表。使用CLP(FD)约束是描述这样一个列表最优雅和通用的方法。使用numlist/3的解决方案不够通用:它只适用于以特定整数开始,并以1为增量进行排序的具体列表,而不是真正描述“升序整数列表”的通用关系。 - mat
3个回答

3
在接下来的内容中,我们将讨论这个之前的回答中提出的代码。
目标是consecutive_ascending_integers_from_1([2,3,5,8|non_list]),但为什么会失败呢?
让我们逐步进行:
以下是我们开始的代码:
:- use_module(library(clpfd)).
equidistant_from_nth_stride([],_,_,_). equidistant_from_nth_stride([Z|Zs],Z0,I0,D) :- Z #= Z0 + I0*D, I1 #= I0 + 1, equidistant_from_nth_stride(Zs,Z0,I1,D).
equidistant_stride([],_). equidistant_stride([Z0|Zs],D) :- equidistant_from_nth_stride(Zs,Z0,1,D).
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).
首先,我们将(一些)统一更加明确:
equidistant_from_nth_stride([],_,_,_). equidistant_from_nth_stride([Z|Zs],Z0,I0,D) :- Z #= Z0 + I0*D, I1 #= I0 + 1, equidistant_from_nth_stride(Zs,Z0,I1,D).
equidistant_stride([],_). equidistant_stride([Z0|Zs],D) :- I = 1, equidistant_from_nth_stride(Zs,Z0,I,D).
consecutive_ascending_integers(Zs) :- D = 1, equidistant_stride(Zs,D).
consecutive_ascending_integers_from(Zs,Z0) :- Zs = [Z0|_], consecutive_ascending_integers(Zs).
consecutive_ascending_integers_from_1(Zs) :- Z0 = 1, consecutive_ascending_integers_from(Zs,Z0).
我们遵循这个好答案介绍的方法和约定
通过删除目标,我们可以概括一个程序。这是我最喜欢的方法。通过添加谓词(*)/1,如下所示:
:- op(950,fy, *).
*_.
@WillNess正确地指出:
consecutive_ascending_integers_from_1([2|_])失败了,因此它的特化consecutive_ascending_integers_from_1([2,3,5,8|non_list])也必须失败。
如果最大程度地概括代码,以使consecutive_ascending_integers_from_1([2|_])失败,则“可以确定:可见剩余部分的某些内容必须修复”。
consecutive_ascending_integers_from(Zs,Z0) :-
       Zs = [Z0|_],
       * consecutive_ascending_integers(Zs).
从Z0开始,对于列表Zs,如果它是连续的递增整数序列,则函数consecutive_ascending_integers_from(Zs,Z0)为真。
consecutive_ascending_integers_from_1(Zs) :- Start = 1, consecutive_ascending_integers_from(Zs,Start). 对于列表Zs,如果它是以1开始的连续递增整数序列,则函数consecutive_ascending_integers_from_1(Zs)为真。
Let's have another explanation! With version #2 (see above), we observe the following generalized goal fails, too:
?- consecutive_ascending_integers_from_1([_,_,_,_|non_list]). false. 为什么这个目标会失败?让我们最大程度地概括代码,使得该目标会失败:
equidistant_from_nth_stride([],_,_,_). equidistant_from_nth_stride([Z|Zs],Z0,I0,D) :- * Z #= Z0 + I0*D, * I1 #= I0 + 1, equidistant_from_nth_stride(Zs,Z0,I1,D).
equidistant_stride([],_). equidistant_stride([Z0|Zs],D) :- * I = 1, equidistant_from_nth_stride(Zs,Z0,I,D).
consecutive_ascending_integers(Zs) :- * D = 1, equidistant_stride(Zs,D).
consecutive_ascending_integers_from(Zs,Z0) :- * Zs = [Z0|_], consecutive_ascending_integers(Zs).
consecutive_ascending_integers_from_1(Zs) :- * Start = 1, consecutive_ascending_integers_from(Zs,Start). 为什么目标consecutive_ascending_integers_from_1([2,3,5,8|non_list])会失败?
到目前为止,我们看到了两个解释,但可能还有更多...
真相在那里:加入寻找的行列!

(顺便说一下,如果你不知道,答案正文中的@提醒不起作用...) - Will Ness
@WillNess。我知道这一点,谢谢。我使用它是为了简洁起见...你觉得这让人恼火吗? - repeat
不,不,我只是为了防止你不知道并期望它能够工作。是的,我们需要以某种方式标记用户;但这方面缺少简单的功能。非常感谢你的慷慨奖励。 :) :) :) 我感觉有点不好意思,就像作弊一样——你解释了一切,我只是两次应用了你的推理。 :) - Will Ness
2
@WillNess。是的,那个功能确实缺失了,但我们不应该让它困扰我们...关于赏金:你得到了你应得的,因为我觉得我已经联系上你了。如果想作弊,那么用户“false”的学生们应该感觉如何呢?他们可以通过按下一个键自动获得这样的解释(以及其他类型的[标签:失败切片]等)。 - repeat
1
@WillNess。我觉得我们(大家)应该一起继续开发这种“调试”方法论。许多想法可能值得考虑。 - repeat

3

“最好”的方法取决于您具体的使用情况!这是另一种使用的方法:

:- use_module(library(clpfd)).

我们根据@mat在对相关问题的先前答案的评论中提出的建议,定义谓词 equidistant_stride/2
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).

consecutive_ascending_integers_from(Zs,Z0) :-
   Zs = [Z0|_],
   consecutive_ascending_integers(Zs).

consecutive_ascending_integers_from_1(Zs) :-
   consecutive_ascending_integers_from(Zs,1).

让我们运行一些查询!首先是您的原始用例:

?- 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]
...

使用 ,我们可以提出相当普遍的查询,并获得逻辑上正确的答案!

?- 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。

一个替代实现的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([],_).
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.                               % 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

现在让我们切换到新版本并询问相同的查询!
?- equidistant_stride([1,_,_,_,14],D)。
false。                                     %失败,正如应该的那样
?- equidistant_stride([1,_,_,_,14 | _],D)。 false。 %失败,正如应该的那样

再来一些!我们是否可以通过暂时使用冗余约束条件更早地失败?

以前,我们建议使用约束条件 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([],_).
equidistantRED_stride([Z|Zs],D) :-
   equidistant_from_nth_stride(Zs,Z,1,D),
   equidistantRED_stride(Zs,D).

示例查询:

?- Zs = [_,4,_,_,14], equidistant_stride(Zs,D), equidistantRED_stride(Zs,D).
false.

完成了吗?还没有!通常情况下,我们不希望有二次冗余约束条件。原因如下:

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

... and ...

?- 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).
...                                        % 执行已终止

有修复方法吗?有黑客技巧!

?- 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.
该 hack 不能保证冗余约束“part”的终止,但在我看来,这对于快速第一次尝试来说并不太糟糕。在任何变量实例化为Zs中的单个变量时,测试integer/1旨在允许求解器将变量域约束为单例,而使用 cons-pairs 进行实例化(直接导致基于列表的谓词的非终止)被抑制。

我确实意识到这种 hack 可以很容易地以多种方式被破解(例如,使用循环术语)。欢迎任何建议和评论!


@WillNess。请查看我改进后的equidistant_stride/2替代实现,非常棒! - repeat
1
所以现在他们“全都在一起”,不仅仅是成对的。很好!(顺便说一句,我没有收到提醒;-at-name 只有在名字在收件人列表中时才有效 - 这是一个 OP、一个回答者和可能的编辑)。 - Will Ness
1
仍然,equidistant_stride([_,4,_,_,14],D). 成功了...也许可以创建更多的连接,但我担心它们会成为二次数量级,并可能影响效率。现在我们有{4=x+d1,14=x+d4}。第一个元素仍被视为特权。 - Will Ness
1
@WillNess。clpfd 必须保持平衡。事实上,我很惊讶 clpfd 可以在没有“标记”情况下推断出很多信息。即使存在缺陷,我仍然喜欢这种获取解释的方法:如果某些概括成功了(但仍应该失败),我们的分析只会变得不那么精确,但仍然正确。同样的基本规则也适用于引发“实例化错误”异常的概括。 - repeat
@WillNess。首先,唯一需要保留的信息是失败/成功,例如:post_linear(Xs), \+ \+ post_quadratic(Xs)。当然,我不想支持那种编码风格,但在某些情况下,这可能实际上效果很好。另一方面,这很容易导致过度工程化某些不那么重要的边角情况... - repeat
显示剩余4条评论

1
我们将升序列表定义为至少包含两个递增的整数元素的列表(非递减列表可以为空或单例,但“升序”是一个更明确的属性)。这是一个有点武断的决定。
在SWI Prolog中:
ascending( [A,B|R] ):-
   freeze(A, 
      freeze(B, (A < B, freeze(R, (R=[] -> true ; ascending([B|R])))) )).

"为了轻松填充它们,我们可以使用:"
mselect([A|B],S,S2):- select(A,S,S1), mselect(B,S1,S2).
mselect([], S2, S2).

测试:

15 ?- 升序(LS),选择(LS,[10,2,8,5],[]).
LS = [2, 5, 8, 10] ;
false.


16 ?- 选择(LS,[10,2,8,5],[]), 升序(LS).
LS = [2, 5, 8, 10] ;
false.


关于赏金问题,根据https://stackoverflow.com/tags/logical-purity/info
只有单调(也称为:“单调”)谓词是纯的:如果谓词对于任何参数都成功,则它不会失败于这些参数的任何概括,如果它对于任何参数组合失败,则它不会成功于这些参数的任何特化。 consecutive_ascending_integers_from_1([2|B]) 失败了,所以它的特化 consecutive_ascending_integers_from_1([2,3,5,8|non_list]) 也必须失败。

对于扩展赏金"consecutive_ascending_integers_from_1([2,3,5,8|non_list])为什么失败了?",额外的失败目标是:(1)

consecutive_ascending_integers_from_1([_,3|_])

对于代码

equidistant_from_nth_stride([],_,_,_).     
equidistant_from_nth_stride([Z|Zs],Z0,I0,D) :-
   Z  #= Z0 + I0*D,                        % C1
   *( I1 #= I0 + 1 ),
   equidistant_from_nth_stride(Zs,Z0,I1,D).

其余部分不变,因为C1变成了3 #= 1 + 1*1。同时,(23)

consecutive_ascending_integers_from_1([A,B,5|_])
consecutive_ascending_integers_from_1([A,B,C,8|_])

两种方法在未更改代码的情况下均失败,因为第一个定义了。
A = 1, B #= 1 + 1*1, 5 #= 1 + 2*1

第二个定义了


A = 1, B #= 1 + 1*1, C #= 1 + 2*1, 8 #= 1 + 3*1

另一种可能性(4)是:
consecutive_ascending_integers_from_1([_,3,5|_])

使用通用化的

标签

consecutive_ascending_integers_from_1(Zs) :-
   *( Z0 = 1 ),
   consecutive_ascending_integers_from(Zs,Z0).

consecutive_ascending_integers_from(Zs,Z0) :-
   *( Zs = [Z0|_] ),
   consecutive_ascending_integers(Zs).

由于。
26 ?- 3 #= Z + 1*1, 5 #= Z + 2*1.
false.

同样地,通过类似修改的代码,目标(5)也可以实现。
consecutive_ascending_integers_from_1([_,3,_,8|_])

由于
27 ?- 3 #= Z + 1*1, 8 #= Z + 3*1.
false.

还有(6 ... 9

consecutive_ascending_integers_from_1([2,3,_,8|_])
consecutive_ascending_integers_from_1([2,_,_,8|_])
consecutive_ascending_integers_from_1([2,_,5,8|_])
consecutive_ascending_integers_from_1([2,_,5|_])

由于同样的原因,另一种可能的代码泛化是将D保持未初始化(其余原始代码不变):
consecutive_ascending_integers(Zs) :-
   *( D = 1 ),
   equidistant_stride(Zs,D).

为了使目标(5...[_,3,_,8|_]... 再次失败,因为

49 ?- 3 #= 1 + 1*D, 8 #= 1 + 3*D.
false.

但是,
50 ?- 3 #= 1 + 1*D, 5 #= 1 + 2*D.
D = 2.

所以...[_,3,5|_]...会成功(事实上也确实成功了)。(10)

consecutive_ascending_integers_from_1([_,_,5,8|_])

由于同样的原因,它也会失败。

可能还有一些其他的组合,但总体意思变得更加清晰:所有这些都取决于由谓词创建的约束条件如何操作。


1
如果consecutive_ascending_integers_from_1([2|B])失败了,那么它的特化版本consecutive_ascending_integers_from_1([2,3,5,8|non_list])也必须失败。这是你的意思吗? - Will Ness
1
没错!其他不同的专业呢?如果我没记错的话,至少还有4个。提示:尝试将 [2,3,5,8|non_list] 的一些子术语概括。 - repeat
1
好的,我的规格相当模糊 :) 将整数值泛化为整数约束是一个非常好的想法A #> 1包括A=2;但为什么不使用更通用的形式,如A #\= 1 - repeat
2
我提供的代码还有改进的空间。?- equidistant_stride([1,X,Y,Z,14],D). 成功了,但是带有延迟目标,?- equidistant_stride([1,X,Y,Z,14],D), 1+D*K#=14. 也是如此。但是 ?- equidistant_stride([1,X,Y,Z,14],D), 1+D*K#=14, (D #> 0 ; D #=< 0). 失败了。 - repeat
2
关于“控制流”的另一件事。如果您将协程视为Prolog执行模型的有效扩展,则我们别无选择,只能承认“约束求解”也是如此。例如,请考虑@mat的clpfd实现:具有属性变量的100% Prolog。太棒了! - repeat
显示剩余27条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接