CODEWITHSUNDEEP
prolog
Tzu ng
Tzu ng

Reputation: 9244

prolog - need to explain union and intersection

/* e */
union([A|B], C, D) :- member(A,C), !, union(B,C,D).
union([A|B], C, [A|D]) :- union(B,C,D).
union([],Z,Z).

/* f */
intersection([A|B], C, D) :- member(A,C), !, intersection(B,C,D).
intersection([A|B], C, [A|D]) :- intersection(B,C,D).
intersection([],Z,[]).

Can you guys explain clearly how these expression, maybe in a tree, thanks much. I'm very new to prolog :)

Upvotes: 2

Views: 6949

Answers (1)

olliej
olliej

Reputation: 36793

My memory of prolog is somewhat rusty, but i think it goes like this:

The union rule essentially takes two lists and returns a union of them, eg. union(List1, List2, UnionOfList1AndList2)

The first rule

union([A|B], C, D) :- member(A, C), !, union(B, C, D)

This will match if member(A, C) matches (presumably member(A, C) matches if C is a list containing the value bound to A), ! is a cut so if we reach this we can't back track from here. We then resolve the rest of the list on the left hand side.

Basically we're saying if the HEAD of List1 is in List2 then the result is the union of the tail of List1 unioned with List2. (This is technically an incorrect description of what's happening but i'm sure it will do :D )

union([A|B], C, [A|D]) :- union(B, C, D)

Given we've dealt with the case where A is in List2, we know the this time A is not in List2 so we prepend it to the "result" of union(B, C, D).

Finally union([], Z, Z) is saying that if List1 is empty the union of List1 and List2 is List2.

The intersection rules are not substantially different.

Upvotes: 4

Related Questions