In the prolog there is a standard way to define union of two sets
But I want to write union function for multisets. That would mean if first set has [1,2] and
second has [2,3] then the output should be [1,2,2,3].
How do I go about writing such a function.
Writing a union operation in prolog for multisets
Viewed 176
1 Answers
There is no type Set in Prolog. What you are referencing are just lists. The union predicate combines two lists with assumed unique elements to a new list where the elements are again unique. The order does not matter in a set. You see that when you pass a non-ordered/non-set list.
% 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].
To create a multiset, i.e. keep all elements in the set union, you can just combine the lists, while ordering them as you please. Formally, a multiset is not ordered as well, so if sorting does not matter, you can just append the second list to the first, which also works with your example:
?- 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].
If you can assume the lists to be ordered and you want that to be the case in the result, you can just merge them, which keeps the order:
?- merge([1, 2, 4], [2, 3, 4, 5], S).
S = [1, 2, 2, 3, 4, 4, 5].
If you can not assume the lists to be sorted, but you want to have the result sorted, you can also take care of the sorting yourself, e.g. with 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].
There are also more sorting predicates around, and if it's more complicated you can write one yourself, too.
Related