#### [SOLVED] Prolog union for A U B U C

By 5oo

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 ?

#### @false 2014-12-08 13:00:02

``````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).
``````

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) ).
``````

#### @Tudor Berariu 2014-12-08 13:41:29

You missed the second argument there: `maplist(dif(X), L)`. Excellent answer!

#### @false 2014-12-08 14:10:30

@TudorBerariu: Thank you! It's not that higher order that I can even omit the `L`.

#### @Will Ness 2015-10-25 20:51:08

@false strange behaviour: gist.github.com/WillNess/cf47a4117331f949fbd9 (?) -- I don't autoload clpfd, maybe that's the reason?... (run in SWI-Prolog 64bit, 7.2.0, Win7PRO).

#### @false 2015-10-26 01:34:38

@WillNess: Ugly, thx! It seems the multiple argument indexing heuristics in SWI has changed. For, `memberd_t(E, [3], T), E = 1.` is determinate but `E = 1, memberd_t(E, [3], T)` is not. So I added the first-argument indexing version that also works for SICStus.

#### @false 2015-10-26 01:48:59

@WillNess: Wait! Try this first: Before making a query like `memberd_t(1,[3],T)` rather ask `membed_t(E,[3],T)`. In this manner, indexing for the second argument is created. Then, the original programs runs like a charm. So maybe SWI has not changed, but simply the history of actions prior to entering this test has changed.

#### @Will Ness 2015-10-26 09:48:45

@false yes, history - that's what the transcript was showing too, after `memberd_t(4,[3],T)` it was suddenly working.

#### @false 2015-10-26 10:31:54

@WillNess: My guess: After `10 ?- memberd_t(X,[1,2,3],T).` the indexing was present.

#### @false 2015-10-26 19:46:31

@WillNess: See this for more complex cases.

#### @j4n bur53 2016-04-04 19:32:32

Normally reification is not only introduced to combine a negative and a positive predicate, still non-determinstic. The reified (# \ /)/2 of CLP(FD) is able to eliminate non-determinism. See also: stackoverflow.com/a/36410996/502187

#### @j4n bur53 2016-04-04 21:53:15

Also of course we should start thinking about a combination of (=)/2 and (#=)/2. To then have CLP(FD) and CLP(H) at the same time.

#### @false 2016-04-05 09:20:48

`(=)/2` in SICStus/SWI/YAP/B is already extended to express equality between both. `(#=)/2` only serves to have compact arithmetic expressions.

#### @j4n bur53 2016-04-04 19:14:24

Using only predicates with an extra argument such as memberd_t/3 leads only to weak reification. For strong reification we also need to generate constraints. Strong reification is a further approach to eliminate non-determinism.

But strong reification is difficult, a possible way to archive this is to use a `CLP(*)` instance which has also reified logical operators. Here is an example if using `CLP(FD)` for the union problem. Unfortunately this covers only the domain `Z`:

Strong Reification Code:

``````member(_, [], 0).
member(X, [Y|Z], B) :-
(X #= Y) #\/ C #<==> B,
member(X, Z, C).

union([], X, X).
union([X|Y], Z, T) :-
freeze(B, (B==1 -> T=R; T=[X|R])),
member(X, Z, B),
union(Y, Z, R).
``````

The above doesn't suffer from unnecessary choice points. Here are some example that show that this isn't happening anymore:

Running a Ground Example:

``````?- union([1,2],[2,3],X).
X = [1, 2, 3].
``````

Also the above example even doesn't create choice points, if we use variables somewhere. But we might see a lot of constraints:

Running a Non-Ground Example:

``````?- union([1,X],[X,3],Y).
X#=3#<==>_G316,
1#=X#<==>_G322,
_G316 in 0..1,
freeze(_G322,  (_G322==1->Y=[X, 3];Y=[1, X, 3])),
_G322 in 0..1.

?- union([1,X],[X,3],Y), X=2.
X = 2,
Y = [1, 2, 3].
``````

Since we didn't formulate some input invariants, the interpreter isn't able to see that producing constraints in the above case doesn't make any sense. We can use the `all_different/1` constraint to help the interpreter a little bit:

Providing Invariants:

``````?- all_different([1,X]), all_different([X,3]), union([1,X],[X,3],Y).
Y = [1, X, 3],
X in inf..0\/2\/4..sup,
all_different([X, 3]),
all_different([1, X]).
``````

But we shouldn't expect too much from this singular example. Since the `CLP(FD)` and the `freeze/2` is only an incomplete decision procedure for propositions and Z equations, the approach might not work as smooth as here in every situation.

Bye

#### @Tudor Berariu 2014-12-08 13:00:21

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).
``````

#### @5oo 2014-12-08 13:23:37

this is working just fine, but i need to write union(L1, L2, L3, U):-union(L1, L2, U12), union(U12, L3, U). as predicate

#### @Tudor Berariu 2014-12-08 13:25:45

I don't understand. Why isn't that clause suitable for you?

### [SOLVED] Getting a list item by index

• 2013-03-17 02:05:56
• user1909486
• 570900 View
• 259 Score
• Tags:   c# list

### [SOLVED] Make function check objects in predicate Prolog

• 2017-11-11 19:18:20
• ProPall
• 52 View
• 0 Score
• Tags:   prolog

• 2017-09-17 08:49:25
• Meal App
• 311 View
• 0 Score
• Tags:   prolog

### [SOLVED] How to remove sub-lists in prolog?

• 2014-12-02 08:55:08
• user3671805
• 392 View
• 4 Score
• Tags:   list prolog sublist

### [SOLVED] List in SWI-Prolog

• 2012-11-14 21:03:48
• lolopolosko
• 972 View
• 1 Score
• Tags:   list prolog

### [SOLVED] Prolog Undefined procedure and Operator priority clash error?

• 2013-12-13 04:35:19
• user3098032
• 2678 View
• -3 Score
• Tags:   prolog