1

この質問を差分リストとして空のリストに書き留めていたとき、それらの構造について知っていることをテストしたいと思いました。しかし、異なる記法を比較するという単純なことを試みたとき、私は間違っているように見え、違いリストで実際に何が起こっているのか理解していませんでした。

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

これを SWI-Prolog と SICStus でテストしました。Bratko の Prolog Programming for AI の 210 ページにこのように書かれているので、表記法を確認しましたが、どうやら統一はできないようです。何故ですか？これらの表記法は同じ宣言的な意味を持っていませんか?

4

1 に答える 1

5

Prolog インタープリターは差分リストを特別なものとして扱うという考えをお持ちだと思います。そうではありません: Prolog は差分リストの概念を認識していません (また、いくつかの構文上の砂糖を除くほぼすべての概念も認識していません)。彼は次のことしか見ていません。

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

ここで-/2、 と|/2はファンクタでありa、b、 、c、d、eおよび[]は定数です。

差分リストは単なるプログラミング手法です (たとえば、動的プログラミングも手法であり、コンパイラーは動的プログラミング プログラムを別の方法で検出したり処理したりすることはできません)。式の奥にある (部分的に) 未統一な部分を効率的に統一するために使用されます。

2 つのリストが必要だとしappend/3ます。これは次のように行うことができます。

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

しかし、これはO(n)で実行されます。最初のリスト全体を最初に反復処理する必要があります。そのリストに何千もの要素が含まれている場合、多くの時間がかかります。

これで、リストだけでなく、 がリストの先頭への参照であり、 が統一されていないリストの末尾への参照であるタプルをフィードするコントラクトを自分で定義できます。この要件を満たす構造の例は、 、、です。append_diff/3-(List,Tail)ListTailTail-Tail[a|Tail]-Tail[1,4,2,5|Tail]-Tail

O（1）append_diff/3で効果的にできるようになりました：

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]のように折りたたまれ[a|[1,4,2,5|T2]]ます。開いた尾を持つリスト。しかし、これはあなた自身が特別な意味を与えているからにすぎません: Prologは単にであり、マイナスではなく、差を計算しません。Prolog はファンクタにセマンティクスを付加しません。の代わりにを使用したとしても、わずかな違いはありませんでした。[a,1,4,2,5|T2]T2[a,1,4,2,5|T2]-T2T2---+-

したがって、質問に戻ると、Prolog にそれを述べL = -([a,b,c,d,e],[d,e])、後でそれを述べるだけですL = [a,b,c]。これで、これら 2 つの表現を統一できないことが明らかになりました。だからプロローグは言うfalse。

于 2017-01-11T13:50:53.303 に答える