14

我知道一些 Prologs 支持开箱即用的类字典关联数据结构。对于这样做的实现，它们是否支持与另一个实际上不包含所有键的结构部分统一的概念？

例如，在 core.logic/miniKanren 的语法中：

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

这将返回 q 绑定为 1 的单个结果。

Prologs 是否给这个操作或这个部分结构命名？

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 的正常统一机制就会处理剩下的事情——不需要对这种或那种数据类型的特殊支持。根据您的要求，我认为您想要的是一个子集关系，除了检查一个关联的所有都在另一个关联中并且它们都具有相同的值。我想这看起来像这样：

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 回答
3

某些 Prolog 系统（例如 Eclipse）具有记录符号。当您事先知道地图的可能键时，可以使用此功能。但它需要一个类型声明。记录符号也出现在 Prolog 的后代语言中，例如 Erlang。

这个想法很简单。您首先声明一个记录类型（这里发明了一些语法）：

:- rectype T{K1,...,Kn}.

现在您可以在您的 Prolog 程序记录中使用，只需编写（这里再次发明了一些语法）：

... T{F1 = V1, .., Fn = Vm} ...

在编译类型时，记录将被转换为复合，然后可以很容易地用于正常的统一。转换根据记录类型声明重新排序键值对，然后删除键并仅使用位置。如果记录类型声明也涵盖了这一点，则未使用的位置将被匿名变量或默认值替换。

... T(W1, ..., Wn) ...

您的示例将按如下方式工作：

:- rectype myrec{foo, bar}

?- myrec{foo=1,bar=2} = myrec{foo=q}

后一个查询将在内部执行为：

?- myrec(1,2) = myrec(q,_).

有关 Eclipse 如何执行此操作的更多详细信息，请参见此处的示例：http:
//www.eclipseclp.org/doc/bips/kernel/syntax/struct-1.html

对于键集不是静态的动态映射，您可以实现动态数据结构，如关于 SWI-Prolog AVL 树的另一篇文章所示。或者向您的 Prolog 系统询问特定数据结构的句柄。使用 FFI（外部功能接口）实现这些或访问已与 Prolog 系统捆绑的这些。例如 Eclipse 捆绑了一对，请参阅下面文章中的“描述”部分：http:
//www.eclipseclp.org/doc/bips/kernel/record/index.html

再见

于 2012-10-10T09:06:09.943 回答
1

我不清楚你真正想要什么（你已经删除了散列方面），但也许你更想要特征术语或特征结构？

它们很受语言学家的欢迎，并已成为生活的一部分。

可以在属性变量的帮助下实现它们，但到目前为止，我还没有看到对它们的太多需求。

您还可以使用句法统一来稍微笨拙地模拟它们。这很笨拙，因为您需要用一个单独的参数来表示每个特征（您可以做得更好，但它也更复杂）。因此，如果您的程序包含 n 个特征，则一个特征结构将包含 n 个不同的参数，其中大多数永远不会被触及。但是，统一将按预期直接工作。

于 2012-10-10T14:36:26.940 回答