Union of two variable sets

Question

Given two lists of variables, what is the most compact and canonical way in ISO Prolog to determine the union of both? That is, we want a definition for the (meta-logical) predicates

varset_union(VarSet1, VarSet2, Union)

and for a list of lists

varset_union(VarSets, Union)

where Union is a list of unique variables of the given VarSets.

Here is an overview of the built-ins in ISO/IEC 13211-1:1995 including Cor.2:2012.

score 13 · Accepted Answer · edited Dec 10 '14 at 19:13

13

Solution using term_variables/2:

varset_union(VarSet1, VarSet2, Union):-
    term_variables([VarSet1|VarSet2], Union).

varset_union(VarSets, Union):-
    term_variables(VarSets, Union).

Solution using setof/3:

varset_union(VarSet1, Varset2, Union):-
    varset_union([VarSet1, VarSet2], Union).

varset_union([], []).
varset_union(VarSets, Union):-
    setof(Var, VarSet^(member(VarSet, VarSets), member(Var, VarSet)), Union).

edited Dec 10 '14 at 19:13

false

10,264
13
101
209

answered Dec 10 '14 at 13:26

Tudor Berariu

4,910
2
18
29

1

Note that the definition with `setof/3` will produce a list of variables in implementation dependent order - which means essentially random order - whereas `term_variables/2` has a well defined order. – false Dec 10 '14 at 17:26
1

And in terms of efficiency the `setof/3` solution is much worse [at least in SWI-Prolog]. – Tudor Berariu Dec 10 '14 at 17:50
1

`setof/3` uses `term_variables/2` to determine the variables to be processed. And that is only the first step ... – false Dec 10 '14 at 19:15

score 2 · Answer 2 · answered Dec 24 '15 at 14:05

2

Based on Tudor's great answer, I have devised a definition of varset_union/3 that is more compact by 2 characters:

varset_union(VarSet1, VarSet2, Union):-
        term_variables(VarSet1+VarSet2, Union).

;-)

answered Dec 24 '15 at 14:05

mat

40,498
3
51
78

1

In many implementations, this will be slower (like in SWI) and/or consume more space (like in SICStus, YAP). – false Dec 25 '15 at 16:22
I have strived for the criteria you asked for: Compact and canonical. Union and `+` are closely related, so it is at least very natural to use `+` here. – mat Dec 25 '15 at 16:41

Union of two variable sets

2 Answers2