Prologインタープリタでの差分リストの使い方

Question

this question on an empty list as a difference listを書き留めているとき、私はそれらの構造について知っているものをテストしたかったのです。しかし、違う表記を比べるだけの簡単なことをしようとしたとき、私は間違っているように見えました。ではなく、は実際に違いリストで何が起こっているのか理解しています。

?- L = [a,b,c|[d,e]]-[d,e], L = [a,b,c]. 
false % expected true 

私はこれをSWI-PrologとSICStusでテストしました。この記法はBratkoのProlog Programming for AI（210ページ）に書かれているので、この表記を検証しましたが、明らかに統一は不可能です。何故ですか？これらの記法は同じ宣言的意味を持っていないのですか？

Answer 1

私は、Prologインタープリタが違いリストを特別なものとして扱うという考えを持っていると思います。そうではありません：Prologは相違点リストの概念を認識していません（構文糖を除くほとんどすべての概念の認識もありません）。彼は唯一の見ている：

L=-(|(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, []))) 

-/2と |/2はファンクタあり

、およびa、b、c、d、eと[]は定数です。

差分リストは単にプログラミング技術ある（例えば動的プログラミングためにも技術であるように、コンパイラが検出も異なる動的プログラミング・プログラムを処理することができません）。これは、表現の深い（部分的に）未統一部分を効率的に統一するために使用されます。

append/3 2つのリストが必要です。

%append(A,B,C). 
append([],L,L). 
append([H|T],L,[H|B]) :- 
    append(T,L,B). 

しかし、これはO（n）ので実行されます：あなたは、最初に全体の最初のリストを反復処理する必要があるが、次のようにあなたはこれを行うことができます。リストに何千もの要素が含まれていると、時間がかかることがあります。

今、あなたはあなたがappend_diff/3リストだけでなく、Listは、リストの先頭への参照である、とTailはの終わりへの参照であるタプル-(List,Tail)を供給します契約を自分で定義することができます統一リストではありません。この要件を満たす構造の例は、Tail-Tail,[a|Tail]-Tail,[1,4,2,5|Tail]-Tailです。

今することができます効果的にappend_diff/3でO（1）と：

append_diff(H1-T1,T1-T2,H1-T2). 

なぜ？ を統一すると、最初のリストの未統一テールが2番目のリストと統合されます。今や第2のリストの統一されていない尾が最終リストの末尾になります。だから、例えば取る：

append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L). 

あなたは上記を参照としてあなたはT1が[1,4,2,5|T2]で統一します、述語を呼び出すと、我々はまた、T2への参照を持っているので、今最初のリストは、[a|[1,4,2,5|T2]]または短い[a,1,4,2,5|T2]に崩壊し、 [a,1,4,2,5|T2]-T2：オープンテールの新しい差異リストT2を返すことができます（プロローグでははを返しました）。あなたは特別な意味を自分-を与えるので、しかし、これが唯一である：プロローグ-は、単に-のであるため、それはないマイナスで、それは計算しないの違いなどPrologはファンクタにセマンティクスを添付していません。 -の代わりに+を使用した場合は、それほど大きな違いはありません。

質問に戻るには、L = -([a,b,c,d,e],[d,e])以降でL = [a,b,c]と言ってください。これらの2つの表現を統一することはできません。だからPrologはfalseと言っています。