Prolog Connection for AUBUC

Question

I recently started studying Prolog, and I cannot decide how to create a union of the three lists.

I managed to create a union from two 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?

Answer 1

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

Your union/3 definition 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 the case when the difference shows:

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

What should [A] and [B] look like so that their union contains 2 elements?

Answer: they must be different.

The original version is not suitable for this request, but a specialized instance of the type can be created for it

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

Thus, it succeeds for this, but does not allow generalizing it. Therefore, this is not a pure, logical relation.

So everything is perfect and perfect with dif/2 ? Unfortunately not. @TudorBerariu has good reason to cut back, as it reflects some of the intentions we have about the relationship. Reduction effectively reflects two key intentions

• that the alternative of not being a member is now excluded, which is true for certain modes, such as Arg1 and Arg2, which are both sufficiently specific terms. A safe approach would be a reason.

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

Problems are displayed only if the terms are not created sufficiently.

The disadvantage of defining ODs and higher is that both of them are unnecessarily too general, which can be observed with repeating 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 redundant answers | Arg2 | ^{| Arg1 |} -one. So the cut has a good reason to be there.

Another reason union/3 is not very efficient because it is worth it is because it leaves open unnecessary selection points for the (intended) main case. 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. 

Redundancy Elimination

The actual culprit of many redundant answers is the first rule. element(a,[a,a]) (usually 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). 

A recursive rule reading it from right to left reads as follows:

Suppose memberd(X, Ys) is already true for some X and Ys . Given this, and considering that we have a fitting Y that is different from X Then

---

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

Thus, it eliminated redundant solutions. But our definition is still not very effective: he still has to visit Arg2 twice for each element, and then he cannot come to the conclusion that there is no alternative left. In any case: resist the placement of the cut to remove it.

Introducing determinism through 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 one and the same! Only the fact is different. Let us combine them into one definition - with an additional argument indicating whether we will understand 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 is getting a little 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 can be executed several times with different truth values ​​(that is, it can be either true or false), the control constructor makes If_0 succeed only once in order to be 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 indexing the first argument, rather use the following definition (thanks @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) ). 

Answer 2

You can merge the first two lists, and then merge between this result and the third:

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

You can improve union/3 with the cut statement:

 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 3

Using only predicates with an additional argument, such as memberd_t / 3 , leads only to weak reification. For strong materialization, we also need to create limitations. Strong reification is another approach to eliminating non-determinism.

But strong reification is difficult, a possible way to archive is to use an instance of CLP(*) , which also reanimated the logical operators. The following is an example of using CLP(FD) for a join problem. Unfortunately, this only applies to the Z domain:

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 does not suffer from unnecessary selection points. Here is an example that shows that this is no longer happening:

Starting soil Example:

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

Also the above example does not even create selection points if we use variables somewhere. But we can see many limitations:

Starting without land 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 have not formulated some input invariants, the interpreter cannot see that the generating constraints in the above case make no sense. We can use the all_different/1 constraint to help the interpreter a 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 should not expect too much of this single example. Since CLP(FD) and freeze/2 are just an incomplete procedure for accepting sentences and Z-equations, the approach may not work as smoothly as here, in any situation.

Bye