Making a union of two lists in prolog

Question

I need to make a sum of two lists which has no repeated elements inside the result (i.e a union). For example:

?- union([3,4,c,5], [7,f,c,3], X).
X = [3, 4, c, 5, 7, f].

The basic idea seems to be to get each element of List A and add them onto the output while doing so.
After list A is empty, go over list B and only add those elements that were also not in list A.
What I have thus far is this:

union([],[],[]).
union(List1,[],List1).
union([Head1|Tail1],List2,[Head1|Output]):- 
    union(Head1,List2,Output).

This predicate will
result in an empty list upon calling it using empty lists,
result in List1 upon calling it with an empty List2 and
Use list recursion to pass all the List1 elements onto the Output.
The issue I'm having is with checking whether or not the elements of List2 are in also in List1.

My attempt:

union(List1, [Head2|Tail2], [Head2|Output]):-
    not(member(Head2,List1)), union(List1,Tail2,Output).
union(List1, [Head2|Tail2], Output):-
    member(Head2,List1), union(List1,Tail2,Output).

This did not result in the correct answer. I assume it is because when the program reaches

not(member(Head2,List1))

at this point List1 would be empty as a result of

union([Head1|Tail1],List2,[Head1|Output]):- 
        union(Head1,List2,Output).

which would mean all elements of List2 get appended onto the Output.
How exactly would I be able to make the check that an element of List2 is not in List1 if List1 is empty by the time I get to checking? Or is there another solution to this whole problem?

Well, I used \+ instead but I'm afraid the answer is still the same. — T44v1
I would probably do this: union(X, Y, Z) :- setof(E, (member(E, X); member(E, Y)), Z). because if you read it out loud it sounds just like your problem. — Daniel Lyons

T44v1 T44v1 · Accepted Answer · 2017-10-24T09:33:25

Well, it seems that the order of the elements inside the union doesnt matter so I changed the code a bit:

union([],[],[]).
union(List1,[],List1).
union(List1, [Head2|Tail2], [Head2|Output]):-
    \+(member(Head2,List1)), union(List1,Tail2,Output).
union(List1, [Head2|Tail2], Output):-
    member(Head2,List1), union(List1,Tail2,Output).

This predicate will go through List2, append all elements that aren't in also in List1 to the Output and once List2 is empty, will append the entire List1 onto the Output.
In this case:

?- union([3,4,c,5], [7,f,c,3], X).

will get me

X = [7, f, 3, 4, c, 5].

Which is okay since the order is not important in the assignment.

Making a union of two lists in prolog

1 Answers