prolog - 「自由記述式リスト」と「相違リスト」の違い

Question

「自由回答リスト」と「差分リスト」の違いは何ですか?

Answer 1

http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.htmlで説明されているように、オープン リストは差分リストを実装するために使用されるツールです。

オープンリストは、リストのある時点で割り当てられていない変数があるリストです[a,b,c|X]。オープン リストを使用して、違いリストと呼ばれるデータ構造を実装できます。これは、最初の要素とオープン エンドを指す 2 つの項の構造を正式に指定し、伝統的に次のように定義されています: [a,b,c|X]-X、そのようなリストの操作を容易にします。

たとえば、開いているリストしかない場合、要素を最後に追加することは可能ですが、すべてのアイテムを反復処理する必要があります。差分リストでは、リストの終わりの変数 (Hole上記のページでは a と呼ばれる) を使用して反復をスキップし、一定時間で操作を実行できます。

Answer 2

どちらの概念もリストのように見えますが、実際にはそうではありません。1 つは具体的な用語であり、もう 1 つは慣例です。

自由記述リスト、部分リスト

制限のないリストは、リストではないが、リストになるようにインスタンス化できる用語です。標準用語では、部分リストと呼ばれます。ここに部分リストがあります: X、[a|X]、[X|X]はすべて部分リストです。

制限のないリストという概念は、制限のない状態をシミュレートするために、そのようなリストの特定の使用法を示唆しています。自由形式のリストで表される辞書を考えてみてください。新しいアイテムを追加するたびに、「部分リストの最後にある」変数が新しい要素にインスタンス化されます。このプログラミング手法は Prolog で十分に可能ですが、大きな欠点が 1 つあります。それは、プログラムが手続き型の解釈に大きく依存することです。そして、多くの場合、宣言的な解釈を行う方法はまったくありません。

相違点リスト

差分リストは事実上リストそのものではありませんが、目的のリストが 2 つの変数 (リストの開始用と終了用) で表されるようにリストが使用される特定の方法です。このため、差分リストの代わりにリストの差分について話す方がはるかに役に立ちます。

検討：

el(E, [E|L],L).

ここで、最後の 2 つの引数は違いを形成していると見なすことができます: 単一の要素を含むリストです[E]。基本的に 2 番目の引数が先に渡されるだけであるという特定の規則を尊重すれば、より単純なリストからより複雑なリストを作成できるようになりました。そのような違いは、互いに比較されることはありません！

el2(E, F, L0,L) :-
   el(E, L0,L1),
   el(F, L1,L).

これは単なる規則であることに注意してください。リストは強制されません。のことを考える：

?- el2(E, F, L, nonlist).
L = [E,F|nonlist].

この手法は、dcgのエンコードにも使用されます。

Answer 3

例えば

無制限: [a,b,c | _]

差分リスト: [a,b,c|U]-U.