Prologの差分リスト

Question

は、差分リストを使用し、他のではなく、1を次のプログラムを考えてみましょう。両方が同じことを行うので

reverse1(List1,R) :- rev1(List1, R-[]). 
rev1([], A-A). 
rev1([H|T], C-A) :-rev1(T, C - [H|A]). 

reverse2(List1,R) :- rev2(List1, R, []). 
rev2([], A, A). 
rev2([H|T], C, A) :- rev2(T, C, [H|A]). 

、差分リストを使用する利点は何ですか？

Answer 1

与えられた例では、reverse1は真の差分リストを使用していませんが、reverse2の別の表現にすぎません。彼らはどちらも同じ方法で同じ変数を使います。 reverseはそれを添付するのに-ファンクタを使用し、reverse2はそれらを別個のパラメータとして維持します。しかし、それは2つのものの違いです。アルゴリズムの動作は同じです。

実際の差分リストはTが（おそらく時間的に後の時点まで）インスタンス化されていないX-Tようなその中に「穴」を有するリスト構造であり、XはT（例えば、[a,b,c|T]-T）を含みます。 -この中のファンクタは、 "公開された"インスタンス化されていない変数を、それを含む構造体に関連付けます。

よくある単純な例は、差異リストを使用してappendの実装です。 appendの伝統的な、再帰的な実装は次のようになります。

append([], Ys, Ys). 
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs). 

十分にシンプルで、かつ実行時間は、最初のリストの長さに比例します。あなたは、差分リストを使用してリストを追加する必要があるすべてです

append(A-B, B-C, A-C). 

を次のように差分リストを使用して

、あなたはappendを実装することができます。再帰やその他のものはありません。実行時間はリストの長さに関係なくO(1)です。ここでは例の実行です：

append([1,2,3|T]-T, [4,5,6|W]-W, DL). 

収量：

DL = [1,2,3,4,5,6|W]-W 
T = [4,5,6|W] 

あなたが最後のパラメータで空のリストで穴を「埋める」ことで、具体的な答えを得ることができます。

append([1,2,3|T]-T, [4,5,6|W]-W, L-[]). 

あなたは得る：

L = [1,2,3,4,5,6] 
T = [4,5,6] 
W = [] 

Answer 2

あなたの例では、ではなく、という違いのリストがあります。 http://en.wikibooks.org/wiki/Prolog/Difference_Listsを比較してください。差分リストは、テールを既知の変数として保持するというトリックを使用し、直接変更することができます。したがって、リストに一定の時間を追加することができます。しかし、それはあなたの例でやっていることではありません。

あなたの例を見ると、rev1は実際にはコンマであるかのように区切り文字として-を使用しています。私は、rev2ではプロローグインタープリタがパフォーマンスを向上させる方法でルールのインデックスを付ける機会があるという点が唯一の違いだと考えています。この場合、それが何か変わるかどうかは分かりません。審美的に言えば、2番目の解決策は私にとってもよりクリーンなようです。

Answer 3

差別化されたリストが「コンテキスト外」で使用されたことはありませんでした。主なコンテキストはDCGの実装です。

ここはDCGベースの逆です（私は自分で書きましたが、クリスチャンによってリンクされたページでも見つけることができます）。

それはあなたのreverse2がほぼ同じであるか証明リスト

reverse3(L,R) :- phrase(rev3(L),R). 
rev3([]) --> []. 
rev3([H|T]) --> rev3(T),[H]. 

：

?- listing(rev3). 
stackoverflow:rev3([], A, A). 
stackoverflow:rev3([D|A], B, E) :- 
    rev3(A, B, C), 
    C=[D|E]. 

すべてのこれらの定義は、問題を共有する：「後方」モードで使用する場合、それらは、第一の溶液の後にバックトラックに、ループ：

を

?- reverse1(R,[a,b,c]). 
R = [c, b, a] ; (^C here) 
Action (h for help) ? abort 
% Execution Aborted 

正しく、効率的なライブラリの実装を見てみましょう。

?- listing(reverse). 
lists:reverse(A, B) :- 
    reverse(A, [], B, B). 

lists:reverse([], A, A, []). 
lists:reverse([B|A], C, D, [_|E]) :- 
    reverse(A, [B|C], D, E). 

ここには違いがありません！

次に、あなたの質問については、私は、差分リストから、唯一の利点は、プロローグをより良く理解する...タイムリーな答えをすべての