14

一部の Prologs は辞書のような連想データ構造をそのままサポートしていることを理解しています。そうする実装では、実際にはすべてのキーを含まない別の構造との部分的な統合の概念をサポートしていますか?

たとえば、core.logic/miniKanren の構文では次のようになります。

(run* [q]
  (== {:foo 1 :bar 2} (partial-map :foo q)))

これは、q が 1 にバインドされた単一の結果を返します。

プロローグは、この操作またはこの部分構造に名前を付けますか?

4

3 に答える 3

4

一般に、Prolog の基本的なデータ型の不適切な選択を標準的な方法で回避します。つまり、ライブラリを追加し、インターフェイスを使用します。たとえば、SWI-Prologには、AVL ツリーベースの関連付けデータ構造を実装するassocライブラリが付属しています。(余談ですが、バランス ツリーはハッシュ テーブルよりも関数型およびロジック プログラミングでより一般的です。これは、ハッシュ テーブルよりもツリー上に「永続的な」データ構造を作成する方が簡単であるためです。内部構造を共有するという FP の意味で永続的です。)

このライブラリを使用すると、次のようになります。

?- [library(assoc)].
% library(assoc) compiled into assoc 0.00 sec, 97 clauses
true.

?- empty_assoc(Assoc).
Assoc = t.

?- empty_assoc(Assoc), get_assoc(test, Assoc, V).
false.

?- empty_assoc(Assoc), put_assoc(test, Assoc, foo, Assoc2).
Assoc = t,
Assoc2 = t(test, foo, -, t, t).

?- empty_assoc(Assoc), 
   put_assoc(test, Assoc, foo, Assoc2), 
   get_assoc(test, Assoc2, Value).
Assoc = t,
Assoc2 = t(test, foo, -, t, t),
Value = foo.

このようなインターフェイスを提供するものがあれば、その上にあらゆる種類の論理関係を定義できます。論理関係が確立されると、Prolog の通常の統合機構が残りを処理します。このデータ型またはそのデータ型に対する特別なサポートは必要ありません。あなたの要件に基づいて、あなたが望むのはサブセット関係のようなものだと思います.1つの関連がすべて他の関連にあり、それらがすべて同じ値を持っていることの両方をチェックすることを除いて. それは次のようになると思います：

association_subset(Left, Right) :-
  forall(gen_assoc(Assoc, Left, Value), get_assoc(Assoc, Right, Value)).

この述語は、上で定義したように、左の関連付けが右の関連付けのサブセットである場合にのみ真になります。それをテストして、目的の動作をしているかどうかを確認できます。

simple(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, foo_test, V1),
  put_assoc(bar, V1, bar_test, Assoc).

complex(Assoc) :-
  simple(Assoc1),
  put_assoc(baz, Assoc1, bazzle, Assoc).

unrelated(Assoc) :-
  empty_assoc(Empty),
  put_assoc(baz, Empty, bazzle, Assoc).

...

?- simple(X), complex(Y), association_subset(X, Y).
X = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t),
Y = t(baz, bazzle, -, t(bar, bar_test, -, t, t), t(foo, foo_test, -, t, t)).

?- simple(X), simple(Y), association_subset(X, Y).
X = Y, Y = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t).

?- simple(X), unrelated(Y), association_subset(X, Y).
false.

?- complex(X), simple(Y), association_subset(X, Y).
false.

これを次のように正確な質問に翻訳できます。

left(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, 1, Assoc).

right(Assoc) :-
  left(Assoc1),
  put_assoc(bar, Assoc1, 2, Assoc).

?- left(L), right(R), association_subset(L, R), get_assoc(foo, L, Q).
L = t(foo, 1, -, t, t),
R = t(foo, 1, <, t(bar, 2, -, t, t), t),
Q = 1.

この回答は、あなたが尋ねた質問に実際には答えていないことを認識していますが、質問の下の質問に答えてくれることを願っています. 言い換えれば、これらのデータ構造を特別にサポートする必要はありません— 上記の述語は連想リストに対しても定義できます。必要なのは空の連想を作成する通常の方法であり、関連付けのキー/値のテストと生成、および基礎となるデータ構造は無関係になります。データ構造に関しても統合に関しても、特別なサポートは必要ありません。特別な構文は確かに見やすくなります! しかし、あなたが望む行動を得る必要はありません。

于 2012-10-10T06:29:00.520 に答える
1

あなたが実際に何を望んでいるのかは私にははっきりしていませんが (ハッシュの側面を削除しました)、機能用語や機能構造が必要なのでしょうか?

それらは言語学者に人気があり、生活の一部となっています。

属性付き変数の助けを借りてそれらを実装することは可能ですが、これまでのところ、それらの需要はあまり見られません.

また、構文の統一を使用して、少しぎこちなくシミュレートすることもできます。各機能を個別の引数で表す必要があるため、扱いにくいです (これは多少改善できますが、その場合はより複雑になります)。したがって、プログラムに n 個の機能が含まれている場合、機能構造には n 個の異なる引数が含まれ、そのほとんどは決して変更されません。ただし、統合は意図したとおりに直接機能します。

于 2012-10-10T14:36:26.940 に答える