10

私はPrologプログラミングの初心者です。リストの長さを計算するためにこのプログラムを書きました。以下のプログラムが間違っているのはなぜですか？

length(0, []).
length(L+l, H|T) :- length(L, T).

以下のプログラムを書きましたが、正しく動作します。

length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.

順番を変えたらエラーになりました。なんで？

length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
4

5 に答える 5

11

アキュムレータを使用する必要があります。あなたはこのようなことをすることができますが：

list_length([]     , 0 ).
list_length([_|Xs] , L ) :- list_length(Xs,N) , L is N+1 .

これは、リストの最後まで再帰し、各呼び出しが戻るたびに、正しい結果でトップレベルに戻るまで、長さに 1 を追加します。

このアプローチの問題は、各再帰がスタックに新しいスタック フレームをプッシュすることです。つまり、十分な長さのリストを指定すると、[最終的に] スタック スペースが不足することになります。

代わりに、次のような末尾再帰仲介を使用します。

list_length(Xs,L) :- list_length(Xs,0,L) .

list_length( []     , L , L ) .
list_length( [_|Xs] , T , L ) :-
  T1 is T+1 ,
  list_length(Xs,T1,L)
  .

このコードは、0 でシードされたアキュムレータを運ぶワーカー述語をシードします。再帰ごとに、値が現在の値 + 1 である新しいアキュムレータを作成します。リストの最後に到達すると、アキュムレータの値は望ましい結果。

プロローグ エンジンは十分にスマート (TRO/末尾再帰の最適化) であるため、各呼び出しでスタック フレームを再利用できることがわかります (再帰呼び出しの後にローカルは使用されないため)。したがって、再帰を反復にきちんと変換します。

于 2013-10-07T20:28:57.377 に答える
7

このコード

length_1(0,[]).
length_1(L+1, [H|T]) :- length_1(L,T).

動作しますが (追加された角括弧に注意してください)、予期しない方法で。後で評価できる式ツリーを構築します。

?- length_1(X, [1,2,3]), L is X.
X = 0+1+1+1,
L = 3.

書き直したコード (2 番目のバージョン) では、is/2 を呼び出した時点で N1 がまだインスタンス化されていないため、エラーが発生します。

于 2013-10-07T17:19:14.393 に答える
4 
len([], LenResult):-
    LenResult is 0.

len([X|Y], LenResult):-
    len(Y, L),
    LenResult is L + 1.
于 2016-05-13T11:10:42.853 に答える