在 Prolog 中正确使用集合

Question

在 Prolog 中，集合似乎是使用列表来表示的。

例如，以下是union/3SWI-Prolog 的实现：

union([], L, L) :- !.
union([H|T], L, R) :-
    memberchk(H, L), !,
    union(T, L, R).
union([H|T], L, [H|R]) :-
union(T, L, R).

然而这个谓词不是很有声明性，例如：

?- union([1,2,3],X,[1,2,3,4]).
X = [1, 2, 3, 4].

这应该留下一些选择点，或者：

?- union(X,[1,2],[1,2,3,4]).
<infinite loop>

这甚至不起作用！

除此之外，我们还发现以下问题：

?- union([1,2,3],[4,5],[1,2,3,5,4]).
false.

?- union([1,1,1],[4,5],[1,1,1,4,5]).
true.

如果我们真的谈论集合，这显然是错误的。

我们可以清楚地看到，使用列表来讨论集合并不简单，因为：

因此，我们要么发现作用于集合的谓词可以削减可能的解决方案（例如，联合的实现仅在集合有序的情况下才起作用），要么找到根据变量的实例化提供无用选择点的谓词（例如，联合谓词将具有作为许多选择点作为结果集的排列数）。

在 Prolog 中应该如何正确实现适用于集合的谓词？

这个问题非常笼统，并不特定于此处使用的示例union/3。

Answer 1

首先，添加一个我们当前必须处理的额外示例：

?- 联合(A, [], A)。
A = []。

我们可以将其读作：

空集是唯一的集。

谁曾想到？

ECLiPSe 中有一个非常好的用于推理集合的库，作为库（conjunto）：

Conjunto是一个解决有限集域项上的集合约束的系统。它是使用基于元术语的 ECLiPSe 内核开发的。它包含 ECLiPSe 的有限域库。库 conjunto.pl 对包含 Herbrand 术语以及地面集的集合域术语实施约束。

另请注意：

从 ECLiPSe 版本 5.1 开始，本章中描述的库正在逐步淘汰，并由新的集合求解器库取代lib(ic_sets)。

这些都是很棒的库，如果您对设置约束感兴趣，我建议您将它们作为起点。

可以从以下位置获得一个很好的示例，说明可以使用设置约束来完成什么操作：