Set union in prolog with variables-CodePudding

I am searching some SWI-Prolog function which is able to make some set union with variables as parameters inside. My aim is to make the union first and define the parameters at further on in source code.

Means eg. I have some function union and the call union(A, B, A_UNION_B) makes sense. Means further more the call:

union(A, [1,2], C), A=[3].

would give me as result

C = [3, 1, 2].

CodePudding user response：

_{^{(What you call union/3 is most probably just concatenation, so I will use append/3 for keeping this answer short.)}}

What you expect is impossible without delayed goals or constraints. To see this, consider the following failure-slice

?- append(A, [1,2], C), false, A=[3].
   loops, unexpected.  % observed, but for us unexpected
   false.  % expected, but not the case

This query must terminate, in order to make the entire question useful. But there are infinitely many lists of different length for A. So in order to describe all possible solutions, we would need infinitely many answer substitutions, like

?- append(A, [1,2], C).
   A = [], C = [1,2]
;  A = [_A], C = [_A,1,2]
;  A = [_A,_B], C = [_A,_B,1,2]
;  A = [_A,_B,_C], C = [_A,_B,_C,1,2]
;  ... .

The only way around is to describe that set of solutions with finitely many answers. One possibility could be:

?- when((ground(A);ground(C)), append(A,B,C)).
   when((ground(A);ground(C)),append(A,B,C)).

Essentially it reads: Yes, the query is true, provided the query is true.

While this solves your exact problem, it will now delay many otherwise succeeding goals, think of A = [X], B = [].

A more elaborate version could provide more complex tests. But it would require a somehow different definition than append/3 is. Some systems like sicstus-prolog provide block declarations to make this more smoothly (SWI has a coarse emulation for that).

So it is possible to make this even better, but the question remains whether or not this makes much sense. After all, debugging delayed goals becomes more and more difficult with larger programs.

In many situations it is preferable to prevent this and produce an instantiation error in its stead as iwhen/2 does:

?- iwhen((ground(A);ground(C)),append(A,B,C)).
   error(instantiation_error,iwhen/2).

That error is not the nicest answer possible, but at least it is not incorrect. It says: You need to provide more instantiations.

If you really want to solve this problem for the general case you have to delve into E-unification. That is an area with most trivial problem statements and extremely evolved answers. Often, just decidability is non-trivial let alone an effective algorithm. For your particular question, either ACI (for sets) or AN_lr (for concatenation) are of interest. Where ACI requires solving Diophantine Equations and associative unification alone is even more complex than that. I am unaware of any such implementation for a Prolog system that solves the general problem.

Prolog IV offered an associative infix operator for concatenation but simply delayed more complex cases. So debugging these remains non-trivial.