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では、正解を生成した後、無限ループに入ります。この述語を決定論的な述語に変換できますか？または、falseで停止する非決定論的ですか？

はい！しかし、赤いカットを使用しています。参照：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を使用してチェックよりも延期することができます。しかし、それでも1つの問題が残ります。ケース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することは、算術比較が非常に制限されているため、完全に簡単ではありません。つまり、それに応じて成功するのではなく、非常に頻繁にsを生成します。その点を説明するためだけに、後継演算を使用して定義するのは簡単です。var/nonvaris/2(is)/2instantiation_errorlength_sx/2

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

この定義はかなり完璧です。それも失敗しlength_sx(L, L)ます。残念ながら、後継演算は効率的にサポートされていません。つまり、整数iにはO（log i ）ではなくO（ 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のこの関数のソースコードとGNUPrologのソースを提出します。これらはどちらも簡潔でかわいいトリックではありません。どちらも引数をテストし、インスタンス化される引数に応じて処理をさまざまな内部関数に延期することで機能するように見えます。

しかし、私はこれについて間違っていることを望みます。たとえば、なぜそれが正しいことをするのにとても簡単に書くmember/2ことができるのに、それが正しいことをするのがとても難しいのか、私はしばしば疑問に思いましlength/2た。Prologは算数が得意ではありませんが、それは本当に悪いですか？他の誰かがより良い答えを持って来ることを願っています。

于 2013-02-27T21:03:11.503 に答える
-1

（@falseの応答を編集しようとしましたが、拒否されました）

my_len_tail/2リストを生成するとき、（推論の数と実際の時間の両方の点で）buldinよりも高速ですが、制約length/2に問題があります。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 に答える