By 5oo


2014-12-08 12:51:05 8 Comments

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 ?

3 comments

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

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

@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.

@Will Ness 2015-10-26 21:03:14

@false thanks for the link.

@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?

Related Questions

Sponsored Content

26 Answered Questions

[SOLVED] Why not inherit from List<T>?

5 Answered Questions

[SOLVED] Getting a list item by index

  • 2013-03-17 02:05:56
  • user1909486
  • 598318 View
  • 265 Score
  • 5 Answer
  • Tags:   c# list

5 Answered Questions

[SOLVED] Why is [] faster than list()?

1 Answered Questions

[SOLVED] Prolog union fails

1 Answered Questions

[SOLVED] Make function check objects in predicate Prolog

  • 2017-11-11 19:18:20
  • ProPall
  • 53 View
  • 0 Score
  • 1 Answer
  • Tags:   prolog

1 Answered Questions

Solving Quadratic Equation Prolog

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

4 Answered Questions

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

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

1 Answered Questions

[SOLVED] List in SWI-Prolog

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

1 Answered Questions

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

  • 2013-12-13 04:35:19
  • user3098032
  • 2713 View
  • -3 Score
  • 1 Answer
  • Tags:   prolog

1 Answered Questions

[SOLVED] Prolog - solving problems with lists

  • 2013-10-22 21:08:52
  • jojuk
  • 639 View
  • 2 Score
  • 1 Answer
  • Tags:   prolog

Sponsored Content