prolog - 在序言中为多集编写联合操作

Question

在序言中有一种标准方法来定义两个集合的并集
但我想为多集编写联合函数。这意味着如果第一组有 [1,2] 和
第二个有 [2,3] 那么输出应该是 [1,2,2,3]。
我该如何编写这样的函数。

Answer 1

Prolog 中没有类型集。您所引用的只是列表。 union predicate 将两个具有假定唯一元素的列表组合到一个新列表中，其中元素再次唯一。顺序在集合中无关紧要。当您传递非有序/非设置列表时，您会看到这一点。

% both ordered, but result is not
?- union([1, 2, 5, 6], [3, 4, 7, 8], S).
S = [1, 2, 5, 6, 3, 4, 7, 8].

% sets, not ordered
?- union([1, 2, 3], [3, 2, 4, 5], S).
S = [1, 3, 2, 4, 5].

% multisets, not ordered
?- union([1, 2, 3], [3, 2, 4, 5, 5], S).
S = [1, 3, 2, 4, 5, 5].

要创建一个多重集，即将所有元素保留在集合联合中，您可以组合列表，同时根据需要对它们进行排序。形式上，多重集也没有排序，因此如果排序无关紧要，您可以将第二个列表附加到第一个列表，这也适用于您的示例:

?- append([1, 2, 4], [2, 3, 4, 5], S).
S = [1, 2, 4, 2, 3, 4, 5].

?- append([1, 2], [2, 3], S).
S = [1, 2, 2, 3].

如果您可以假设要对列表进行排序并且希望结果是这种情况，则可以合并它们，从而保持顺序:

?- merge([1, 2, 4], [2, 3, 4, 5], S).
S = [1, 2, 2, 3, 4, 4, 5].

如果您不能假设要对列表进行排序，但希望对结果进行排序，那么您也可以自己进行排序，例如与 msort:

?- append([1, 2, 3], [3, 2, 4, 5, 5], S), msort(S, S1).
S = [1, 2, 3, 3, 2, 4, 5, 5],
S1 = [1, 2, 2, 3, 3, 4, 5, 5].

还有更多的排序谓词，如果更复杂，你也可以自己写一个。