Prolog union for A U B U C

Question

I've started to learn Prolog recently and I can't solve how to make union of three lists.

I was able to make union of 2 lists :

%element
element(X,[X|_]).
element(X,[_|Y]):-
               element(X,Y).

%union

union([],M,M).
union([X|Y],L,S) :- element(X,L),union(Y,L,S).
union([X|Y],L,[X|S]) :- (not(element(X,L))),union(Y,L,S).

can anybody help me please ?

Answer 1

You can make the union of the first two lists and then the union between that result and the third:

union(L1, L2, L3, U):-union(L1, L2, U12), union(U12, L3, U).

You can improve union/3 with a cut operator:

union([],M,M).
union([X|Y],L,S) :- element(X,L), !, union(Y,L,S).
union([X|Y],L,[X|S]) :- union(Y,L,S).

Answer 2

union(A, B, C, U) :-
   union(A, B, V),
   union(C, V, U).

Your definition of union/3 can be improved by replacing

... not(element(X,L)), ...

by

... maplist(dif(X),L), ...

or

... non_member(X, L), ....

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

Here is a case where the difference shows:

?- union([A],[B],[C,D]).
A = C,
B = D,
dif(C, D).

How must [A] and [B] look like such that their union contains 2 elements?

The answer is: they must be different.

Your original version fails for this query, yet, it succeeds for a specialized instance like:

?- A = 1, B = 2, union([A],[B],[C,D]).

So it succeeds for this, but fails for a generalization of it. Therefore it is not a pure, logical relation.

So is everything fine and perfect with dif/2? Unfortunately not. @TudorBerariu has good reason to go for a cut, since it reflects some of the intention we have about the relation. The cut effectively reflects two key intentions

• that the alternative of not being a member is now excluded, which is true for certain modes, like Arg1 and Arg2 being both sufficiently instantiated terms. A safe approximation would be ground terms.

• that there is no need to look at further elements in the list Arg2, which again is only true if Arg1 and Arg2 are sufficiently instantiated.

Problems only show when terms are not sufficiently instantiated..

The drawback of OP's definition and the one above, is that both are unnecessarily too general which can be observed with repeated elements in Arg2:

?- union([a,a],[a,a],Zs).
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
false.

In fact, we get |Arg2|^|Arg1|-1 redundant answers. So the cut had some good reason to be there.

Another reason why union/3 as it stands is not very efficient is that for the (intended) ground case it leaves open unnecessary choice points. Again, @TudorBerariu's solution does not have this problem:

?- union([a],[a],Zs).
Zs = [a] ;    %    <--- Prolog does not know that there is nothing left.
false.

Eliminating redundancy

The actual culprit for that many redundant answers is the first rule. element(a,[a,a]) (commonly called member/2) will succeed twice.

union([X|Y],L,S) :- element(X,L), union(Y,L,S).
                    ^^^^^^^^^^^^

Here is an improved definition:

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),          % new!
   memberd(X, Ys).

The recursive rule, reading it right-to-left, reads as follows:

Assume memberd(X, Ys) is true already for some X and Ys. Given that, and given that we have a fitting Y which is different from X. Then

---

we can conclude that also memberd(X, [Y|Ys]) is true.

So this has eliminated the redundant solutions. But our definition is still not very efficient: it still has to visit Arg2 twice for each element, and then it is unable to conclude that no alternatives are left. In any case: resist to place a cut to remove this.

Introducing determinism via reification.

Compare the definitions of memberd/2 and non_member/2. Although they describe "the opposite" of each other, they look very similar:

non_member(_X, []).
non_member(X, [Y|Ys]) :-
   dif(X,Y),
   non_member(X, Ys).

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X,Y),         
   memberd(X, Ys).

The recursive rule is the same! Only the fact is a different one. Let's merge them into one definition - with an additional argument telling whether we mean memberd (true) or non_member (false):

memberd_t(_X, [], false).
memberd_t(X, [X|_Ys], true).
memberd_t(X, [Y|Ys], Truth) :-
   dif(X, Y),
   memberd_t(X, Ys, Truth).

Now, our definition gets a bit more compact:

unionp([], Ys, Ys).
unionp([X|Xs], Ys, Zs0) :-
  if_( memberd_t(X, Ys), Zs0 = Zs, Zs0 = [X|Zs] ),
  unionp(Xs, Ys, Zs).

memberd_t(_X, [], false).          % see below
memberd_t(X, [Y|Ys], Truth) :-
   if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).

Note the difference between if_(If_1, Then_0, Else_0) and the if-then-else control construct ( If_0 -> Then_0 ; Else_0 ). While If_1 may succeed several times with different truth values (that is, it can be both true and false), the control construct makes If_0 succeed only once for being true only.

if_(If_1, Then_0, Else_0) :-
   call(If_1, T),
   (  T == true -> call(Then_0)
   ;  T == false -> call(Else_0)
   ;  nonvar(T) -> throw(error(type_error(boolean,T),_))
   ;  /* var(T) */ throw(error(instantiation_error,_))
   ).

=(X, Y, T) :-
   (  X == Y -> T = true
   ;  X \= Y -> T = false
   ;  T = true, X = Y
   ;  T = false,
      dif(X, Y)                             % ISO extension
      % throw(error(instantiation_error,_)) % ISO strict
   ).

equal_t(X, Y, T) :-
   =(X, Y, T).

To ensure that memberd_t/3 will always profit from first-argument indexing, rather use the following definition (thanks to @WillNess):

memberd_t(E, Xs, T) :-
   i_memberd_t(Xs, E, T).

i_memberd_t([], _E, false).
i_memberd_t([X|Xs], E, T) :-
   if_( X = E, T = true, i_memberd_t(Xs, E, T) ).