CODEWITHSUNDEEP
prologsetset-union
user1897691
user1897691

Reputation: 2451

Prolog - union doesn't check for duplicates or that the list is in order

I'm trying to write a union function in Prolog and I'm running into some trouble. I have looked up examples and listed the built in example for union but I am writing my own for an assignment. I have noticed some strange results when a list has duplicate values and/or when the order of the list is not ascending. The following is the built in union code:

union([], A, A) :- !.
union([A|C], B, D) :-
        memberchk(A, B), !,
        union(C, B, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

I believe that the pseudocode here is that we're looking to find all of list 1 inside of our result and once it's exhausted, we compare list 2 and list 3. They should be the same. However, this does not check for order.

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

Why is this false? List 1 and List 3 are the same set even though the order is different!

24 ?- union([a],[a,a],[a,a]).
true.

25 ?- union([a,a],[a],[a,a]).
false.

What is different between these two? They should yield the same result. However, due to the way that the function is written, in the end we just compare list 2 and list 3 which are different for line 25.

My question is. . . Is there a better way to write these functions such that duplicates are handled properly and order does not matter? One would assume that the built in methods would do the trick but no dice.

Upvotes: 0

Views: 1173

Answers (3)

DrBeco
DrBeco

Reputation: 11793

To have a union(?A, ?B, ?C) (that is, you can use any variable as input or output) I create a new union

uniao(?A, ?B, ?C)

that uses list:union among other stuff, as:

uniao([], [], []) :- !.

uniao(X, [], X) :- !.

uniao([], X, X) :- !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    var(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    union(Xs, Ys, Z), 
    !.  

uniao(X, Y, Z) :-
    nonvar(X),
    var(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Z, Zs),
    subset(Xs, Zs),
    subtract(Zs, Xs, Y), 
    !.  

uniao(X, Y, Z) :-
    var(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    subset(Ys, Zs),
    subtract(Zs, Ys, X),
    !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    union(Xs, Ys, Ts),
    subtract(Zs, Ts, []),
    subtract(Ts, Zs, []),
    !.

Upvotes: 0

Will Ness
Will Ness

Reputation: 71119

First, it's easier to read a code written with consistent naming:

union([], A, A) :- !.
union([A|B], C, D) :-
        memberchk(A, B), !,
        union(B, C, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

What does it do? Given two lists A and B, it produces the result with a prefix of all elements of A not present in B, and then B itself. So, union([1,2,3],[],[1,2,3]). And also union([1,2,3],[2],[1,3,2]). You see that order is preserved here. So if you want to compare lists regardless of their order, you should write a special, additional predicate for that: union([1,2,3],[],X), regardless(X,[3,2,1]) should work then.

Same with the duplicates - your set equality predicate should disregard any. union as presented above OTOH is not about sets, but about lists. There are many different lists representing the same set, but as lists they are considered different.

In your 25 you hit the issue of duplicates: union([a,a],[a],X) produces X=[a]. Again, as set it is the same as [a,a], but as lists they are different.

One strategy for coping with this is to represent sets as strictly increasing lists - if your elements have order well defined for them. Then we can write union such that given two sets according to that definition, it will also produce a set, and it will work efficiently at that:

union([],X,X):-!.
union(X,[],X):-!.
union([A|B],[C|D],[H|T]):-
  A @< C -> H=A, union(B,[C|D],T) ;
  C @< A -> H=C, union([A|B],D,T) ;
  H=A, union(B,D,T).

We will have to define make_set/2 predicate here too. Even better (in some respects) is representing sets (again, of comparable elements) by self-balancing binary trees.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

you are implementing a concept using the 'tools' that the language (Prolog, in your case) put in your hands. Then you should better define (in natural language, first) what's your target, considering that also append/3 could fit the union concept.

you can call list C a union among lists A,B if....

I would fill the ellipsis this way

  • each A element appears once in C and
  • each B element appears once in C and
  • each C element appears in A or B

If you agree on this definition, then an implementation could be

union(A, B, C) :-
  elems_once(A, [], C1),
  elems_once(A, C1, C2),
  each_elems(C2, A, B, C).

That is far less efficient that the library code shown, but it's the price of generality...

Upvotes: 0

Related Questions