在Prolog中从列表创建一个集合

Question

所以基本上我的任务是从给定的List中创建一个带有包含2个参数的谓词的Set。

第一个参数是列表，第二个参数是Set的值。

但不知怎么的，它给我返回了一个包含Set作为头部和尾部变量的List：

2 ?- list2set([2,3,4,4] , X).
X = [2, 3, 4|_G2840] .

这是代码：

list2set( [] , _).
list2set([ListH|ListT] , Set ) :- member(ListH, Set) , list2set(ListT , Set).

我似乎犯了一个非常基础的错误。

- wsad1000

---

在您的定义中，什么使得一组成为一个集合？您只是想要一个具有唯一元素的列表吗？按照传统定义，“集合”意味着元素的顺序无关紧要，并且它们都是唯一的。元素的排序只有在考虑要对集合执行哪些操作时才变得有意义。 - lurker

集合是一种代数数据类型，其对象配备了一个函数，该函数给定一个对象并测试该对象是否在集合中，时间复杂度为O(1)。本质上，它是一个哈希映射，其键未使用。列表具有O(n)的最坏查找时间，并且通常由不连续的分配链接，保证缓存未命中。要使集合成为集合，它必须具有摊销的O(1)访问时间。 - Dmytro

“set”是一个数学概念，没有时间的概念。 - Will Ness

Answer 1

首先，在Prolog中没有集合，我们只有列表¹。因此，您可以将一个包含重复元素的列表与一个不含重复元素的列表相关联。list_nub/2 就是这样一个定义。

关于您当前的定义：

已经可以通过 list2set([], [a])，这显然是不正确的。因此，您的定义过于笼统。您需要将 list2set([],_) 替换为 list2set([],[])。

然后，将 member(ListH, Set) 替换为 member(ListH,ListT)。

另外，您需要为元素不存在的情况添加另一条规则。

list2set([] , []).
list2set([E|Es] , Set ) :-
   member(E, Es) ,
   list2set(Es , Set).
list2set([E|Es] , [E|Set] ) :-
   maplist(dif(E), Es),
   list2set(Es , Set).

更为简洁的定义，避免了冗余的答案，是 list_nub/2。

---

严格来说，可以通过带属性变量扩展统一化²来实现ACI-统一化以获得真正的集合。

据我粗略的理解，这将需要在SICStus中实现带属性变量。像SWI或YAP这样的其他接口很可能是不足够的；正如它们已经对CLP(B)不足够一样。有关更多信息，请参见this discussion。

- false

Answer 2

这里是一个只使用 member/2 的定义。最初的回答。

% base case
set([], []).
% here we say that if the head is in the tail of the list
% we discard the head and create a set with the tail
% the exclamation mark is a "cut" which means that if member(H, T) was true
% prolog cannot backtrack from set([H|T], X) to set([H|T], [H|X]).
% this prevents giving extra answers that aren't sets, try removing it. 
set([H|T], X):- member(H, T), !, set(T, X).
% and here we say that if the previous clause didn't match because
% head is not a member of tail then we create a set of the tail adding head.
set([H|T], [H|X]):- set(T, X).

最初的回答

希望对你有所帮助！

- nicoabie

Answer 3

不错的方法来填充一个独特的列表，保持它的开放性。您可以使用调用length(Set, _)或手工编写等效代码（也要使其确定性），在完成时关闭它。

list2set([], S):- 
    % length( S, _), !
    close_it(S).         % use var/1 

此外，考虑使用memberchk/2而不是member/2。

您还可以通过定义“智能”答案来提供帮助。

list2set(X, X).

并且表示您允许在集合的表达中存在重复项。

- Will Ness

---

声称你允许在集合表示中存在重复项，这与数学中集合的定义相违背，即“一组不同对象的集合，被视为一个整体对象”。 - nicoabie

不，这只是一个解释问题。列表 [2,2,4] 可以作为集合 {2,4} 的表示。没有问题。多重性的问题从未出现，因为根据定义，关于集合从未提出这个问题。成员资格也同样适用。并集也是如此。集合差异将需要以特定方式实现，考虑到这一点。因此，它将更加复杂，与唯一元素列表表示不同。 - Will Ness