10

我正在尝试复制标准 length/2 谓词的行为。特别是，我希望我的谓词适用于有界和无界参数，如下例所示：

% Case 1
?- length(X, Y).
X = [],
Y = 0 ;
X = [_G4326],
Y = 1 ;
X = [_G4326, _G4329],
Y = 2 ;
X = [_G4326, _G4329, _G4332],
Y = 3 .

% Case 2    
?- length([a,b,c], X).
X = 3.

% Case 3
?- length(X, 4).
X = [_G4314, _G4317, _G4320, _G4323].

% Case 4
?- length([a,b,c,d,e], 5).
true.

简单明了的实现：

my_length([], 0).
my_length([_|T], N) :- my_length(T, X), N is 1+X.

有一些问题。在案例 3 中，在产生正确答案后，它进入了一个无限循环。这个谓词可以转化为确定性的吗？还是因错误而停止的不确定性？

是的！但使用红色切割。请参阅：https ://stackoverflow.com/a/15123016/1545971

一段时间后，我设法编写了一组谓词，它们模仿了内置长度/2 的行为。my_len_tail 是确定性的，并且在所有情况 1-4 中都能正常工作。可以做得更简单吗？

my_len_tail(List, Len) :- var(Len)->my_len_tailv(List, 0, Len);
                          my_len_tailnv(List, 0, Len).

my_len_tailv([], Acc, Acc).
my_len_tailv([_|T], Acc, Len) :-
    M is Acc+1,
    my_len_tailv(T, M, Len).

my_len_tailnv([], Acc, Acc) :- !. % green!
my_len_tailnv([_|T], Acc, Len) :-
    Acc<Len,
    M is Acc+1,
    my_len_tailnv(T, M, Len).

正如@DanielLyons 在评论中建议的那样，可以使用clpfd来推迟检查。但它仍然留下一个问题：在案例 3 ( ) 中，谓词是不确定的。怎么可能修好？my_len_clp(X, 3)

:-use_module(library(clpfd)).
my_len_clp(List, Len) :- my_len_clp(List, 0, Len).

my_len_clp([], Acc, Acc).
my_len_clp([_|T], Acc, Len) :-
    Acc#<Len,
    M is Acc+1,
    my_len_clp(T, M, Len).

可以使用zcompare/3CLP(FD) 库修复它。请参阅：https ://stackoverflow.com/a/15123146/1545971

4

6 回答 6

5

在 SWI-Prolog 中，可以使用 CLP(FD) 解决不确定性问题zcompare/3，这将不等式具体化为可用于索引的术语：

:- use_module(library(clpfd)).

my_length(Ls, L) :-
        zcompare(C, 0, L),
        my_length(Ls, C, 0, L).

my_length([], =, L, L).
my_length([_|Ls], <, L0, L) :-
        L1 #= L0 + 1,
        zcompare(C, L1, L),
        my_length(Ls, C, L1, L).

您的示例现在是确定性的（因为 SWI-Prolog 的最新版本执行即时索引）：

?- my_length(Ls, 3).
Ls = [_G356, _G420, _G484].

所有严肃的 Prolog 实现都附带 CLP(FD)，在这里使用它非常有意义。zcompare/3如果尚未提供，请让您的供应商也实施或更好的替代方案。

于 2013-02-27T21:50:41.667 回答
3

对于一组测试用例，请参阅此表和序言中的当前定义。还有很多奇怪的情况需要考虑。

length/2用var/nonvar,等定义is/2并不完全是微不足道的，因为(is)/2和算术比较是如此有限。也就是说，他们非常频繁地产生instantiation_errors 而不是相应地成功。只是为了说明这一点：length_sx/2使用successor-arithmetics定义是微不足道的。

length_sx([], 0).
length_sx([_E|Es], s(X)) :-
   length_sx(Es, X).

这个定义非常完美。它甚至失败了length_sx(L, L)。唉，没有有效地支持后继算术。也就是说，整数i需要 O( i ) 空间，而不是人们期望的O(log i )。

我更喜欢的定义是：

length_fd([],0).
length_fd([_E|Es], L0) :-
   L0 #> 0,
   L1 #= L0-1,
   length_fd(Es, L1).

哪个是最直接的翻译。它在已知长度的情况下非常有效，但在其他情况下会产生显示背后的约束开销。此外，还有这种不对称性：

?- length_fd(L,0+0).
false.

?- length_fd(L,0+1).
L = [_G919] ;
false.

但是，即使对于更复杂的情况，您的使用定义library(clpfd)也特别优雅和高效。它不如内置长度快...

?- time(( length_fd(L,N),N=1000 )).
% 29,171,112 inferences, 4.110 CPU in 4.118 seconds (100% CPU, 7097691 Lips)
L = [_G67, _G98, _G123, _G159, _G195, _G231, _G267, _G303, _G339|...],
N = 1000 .

?- time(( my_len_clp(L,N),N=10000 )).
% 1,289,977 inferences, 0.288 CPU in 0.288 seconds (100% CPU, 4484310 Lips)
L = [_G67, _G79, _G82, _G85, _G88, _G91, _G94, _G97, _G100|...],
N = 10000 .

?- time(( length(L,N),N=10000 )).
% 30,003 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 4685643 Lips)
L = [_G67, _G70, _G73, _G76, _G79, _G82, _G85, _G88, _G91|...],
N = 10000 .

...但随后它能够正确处理约束：

?- N in 1..2, my_len_clp(L,N).
N = 1,
L = [_G1439] ;
N = 2,
L = [_G1439, _G1494] ;
false.

?- N in 1..2, length(L,N).
N = 1,
L = [_G1445] ;
N = 2,
L = [_G1445, _G1448] ;
*LOOPS*
于 2013-02-28T16:14:01.920 回答
1

我对这个答案不是特别有信心，但我的想法是否定的，你必须做一些额外的工作才能让 Prolog 为length/2.

我在 SWI-Prolog 中提交该函数的源代码和 GNU Prolog 中的源代码作为证据。这些都不是一个简洁、可爱的技巧，在我看来，它们都通过测试参数来工作，然后根据实例化的参数将处理推迟到不同的内部函数。

不过，我很想错了。例如，我经常想知道为什么写member/2哪个做正确的事很容易，但写哪个做对却很难length/2。Prolog 不擅长算术，但它真的那么糟糕吗？希望其他人能提供更好的答案。

于 2013-02-27T21:03:11.503 回答
-1

（我试图编辑@false 的回复，但被拒绝了）

my_len_tail/2length/2生成列表时（就推理次数和实际时间而言）比 buldin 更快，但存在N in 1..2约束问题。

?- time(( my_len_tail(L,N),N=10000000 )).
% 20,000,002 inferences, 2.839 CPU in 3.093 seconds (92% CPU, 7044193 Lips)
L = [_G67, _G70, _G73, _G76, _G79, _G82, _G85, _G88, _G91|...],
N = 10000000 .

?- time(( length(L,N),N=10000000 )).
% 30,000,004 inferences, 3.557 CPU in 3.809 seconds (93% CPU, 8434495 Lips)
L = [_G67, _G70, _G73, _G76, _G79, _G82, _G85, _G88, _G91|...],
N = 10000000 .
于 2013-02-28T16:44:46.110 回答
-1

这适用于您的所有测试用例（但它有红色切割）：

my_length([], 0).
my_length([_|T], N) :- 
    ( integer(N) ->
        !, 
        N > 0, 
        my_length(T, X), N is 1 + X, !
    ;
        my_length(T, X), N is 1 + X
    ).
于 2013-02-27T21:43:41.447 回答
-1

执行

goal_expansion((_lhs_ =:= _rhs_),(when(ground(_rhs_),(_lhs_ is _rhs_))))  .

:- op(2'1,'yfx','list')  .

_list_ list [size:_size_] :-
_list_ list [size:_size_,shrink:_shrink_] ,
_list_ list [size:_size_,shrink:_shrink_,size:_SIZE_]  .

_list_ list [size:0,shrink:false]  .

_list_ list [size:_size_,shrink:true] :-
when(ground(_size_),(_size_ > 0))  .

[] list [size:0,shrink:false,size:0] .

[_car_|_cdr_] list [size:_size_,shrink:true,size:_SIZE_] :-
(_SIZE_ =:= _size_ - 1) ,
(_size_ =:= _SIZE_ + 1) ,
_cdr_ list [size:_SIZE_]  .

测试

/*
   ?- L list Z .
L = [],
Z = [size:0] ? ;
L = [_A],
Z = [size:1] ? ;
L = [_A,_B],
Z = [size:2] ? ;
L = [_A,_B,_C],
Z = [size:3] ?
yes

   ?- L list [size:0] .
L = [] ? ;
no
   ?- L list [size:1] .
L = [_A] ? ;
no
   ?- L list [size:2] .
L = [_A,_B] ? ;
no

   ?- [] list [size:S] .
S = 0 ? ;
no
   ?- [a] list [size:S] .
S = 1 ? ;
no
   ?- [a,b] list [size:S] .
S = 2 ? ;
no
   ?- [a,b,c] list [size:S] .
S = 3 ? ;
no
   ?- 
*/
于 2019-03-07T15:31:14.120 回答