CODEWITHSUNDEEP
listprologunionmember
ayla
ayla

Reputation: 3546

How Does Prolog print out 2 lists as one list, without any append code?

I have the following code, which is apparently the standard way to show the union between 2 lists:

union([Head|Tail],List2,Result) :- 
    member(Head,List2),  union(Tail,List2,Result).
union([Head|Tail],List2,[Head|Result]) :- 
    \+ member(Head,List2), union(Tail,List2,Result).
union([],List2,List2).

and on the following input:

union([a,b,c,d,2,3], [b,c,3,99], Result).

will give me the following output:

Result = [a,d,2,b,c,3,99] ? 

yes

My question is, How does prolog do this? List2 is never changed throught the recursive calls, but at the end, it prints out all elements that make the union between the 2 original lists.

Please help me understand this code.

Thank you.

Upvotes: 2

Views: 787

Answers (3)

CapelliC
CapelliC

Reputation: 60034

That code it's actually rather inefficient, so we can't assume it as the 'standard way' to compute union. At first glance, there are 2 simple optimizations: avoid repeat the membership test, and use memberchk/2 instead of member/2. So we can rewrite it in the following way:

union([Head|Tail], List2, ResultT) :-
    (  memberchk(Head, List2)
    -> ResultT = Result
    ;  ResultT = [Head|Result] ),
    union(Tail, List2, Result).
union([],List2,List2).

The difference in performance is huge. With relatively small lists:

...
numlist(1, 10000, A),
numlist(5000, 10000, B),
union(A, B, C),
...

we pass from 62,532,499 inferences to 20,002 inferences, and the test doesn't force the evaluation of all alternatives (backtrack points from member): adding this we need 25,015,004 more inferences, albeit no more solution is available. Here the code from SWI-Prolog lists library:

%%  union(+Set1, +Set2, -Set3) is det.
%
%   True if Set3 unifies with the union of Set1 and Set2.
%   The complexity of this predicate is |Set1|*|Set2|
%
%   @see ord_union/3.

union([], L, L) :- !.
union([H|T], L, R) :-
    memberchk(H, L), !,
    union(T, L, R).
union([H|T], L, [H|R]) :-
    union(T, L, R).

It's similar to your version, please note the cut (!)

Upvotes: 1

m09
m09

Reputation: 7493

The algorithm in work here is the following :

1) initialize the result to List2. This part is implemented thanks to :

union([], List2, List2).

2) go through List1 and do the following for each item :
2a) add it to Result if the item is not in List2. That part is implemented thanks to this clause :

union([Head|Tail], List2, [Head|Result]) :- 
    \+ member(Head, List2),
    union(Tail, List2, Result).

2b) don't do anything if the item is in List2. That part is implemented thanks to this clause :

union([Head|Tail], List2, Result) :-
    member(Head, List2),
    union(Tail, List2, Result).

For step by step comprehension of the prolog execution, please refer to @thanosQR answer.

By the way, note that this predicate needs sets to return a good union, else, a duplicate in List1 will stay a duplicate in Result (so will a duplicate in List2).

Upvotes: 1

thanos
thanos

Reputation: 5858

let's assume that you ask union([1,2],[2],R).

according to the first rule, union([1|[2]],[2],R) would be true if member(1,[2]) --> false then prolog will check the second rule union([1|[2]],[2],[1|R]) will be true if +member(1,[2]) --> true and union([2],[2],R)

now, union([2|[]],[2],R) would be true (1st rule) if member(2,[2]) -->true and union([],[2],R)

union([],[2],R) would be true (3rd rule) if R=[2]

so R=[2] and therefore the first call to union returns [1|[2]] = [1,2]

a useful tool to find out "how prolog does it" is trace/0:

    2 ?- trace.
true.

[trace] 2 ?- union([1,2],[2],R).
   Call: (6) union([1, 2], [2], _G543) ? creep
   Call: (7) lists:member(1, [2]) ? creep
   Fail: (7) lists:member(1, [2]) ? creep
   Redo: (6) union([1, 2], [2], _G543) ? creep
   Call: (7) lists:member(1, [2]) ? creep
   Fail: (7) lists:member(1, [2]) ? creep
   Call: (7) union([2], [2], _G619) ? creep
   Call: (8) lists:member(2, [2]) ? creep
   Exit: (8) lists:member(2, [2]) ? creep
   Call: (8) union([], [2], _G619) ? creep
   Exit: (8) union([], [2], [2]) ? creep
   Exit: (7) union([2], [2], [2]) ? creep
   Exit: (6) union([1, 2], [2], [1, 2]) ? creep
R = [1, 2] .

all in all: List2 doesnt not change but the predicate does not return List2 either; it returns a list created by List2 and the unique elements of List1

Upvotes: 1

Related Questions