CODEWITHSUNDEEP
listprolog
Lucian Tarna
Lucian Tarna

Reputation: 1827

Intersect 2 lists in prolog

My task is to intersect 2 lists in prolog. However I can't seem to find a reason for my functions not to work . I don't know what prolog wants from me. This is my attempt at solving the task: 

write_list([]).


write_list([Head|Tail]) :-
  write(Head), nl,
  write_list(Tail).

intersect(L,[],X) :- write_list(X).
intersect([],L,X) :- write_list(X).

intersect([H1|T1],[H2|T2], X) :-
    H1 == H2,
    append([H1],X,Y),
    intersect(T1,T2,Y).

intersect([H1|T1],[H2|T2], X) :-
    H1 > H2,
    intersect(T1,[H2|T2],X).

intersect([H1|T1],[H2|T2], X) :-
    H1 < H2,
    intersect([H1|T1],T2,X).

I try calling it intersect([1,2,3],[2,3,4],X). and the answer I get is []. Can anyone tell me why ?

Update1: Also as a side question how can I make prolog print that X without me calling write_list(X). I saw that some functions return the extra argument...

Upvotes: 2

Views: 2052

Answers (1)

lurker
lurker

Reputation: 58324

Let's think of the problem in logical language. The meaning of intersect(X, Y, Z) might be, Z is the intersection of X and Y. So the base case of intersect(L, [], X) :- write_list(X). could not be correct unless X = []. For the base case, we might say, then:

intersect([], _, []).

Since anything (_) intersect with the empty set ([]) is empty.

Then for the recursive case, you have:

intersect([H1|T1],[H2|T2], X) :-
    H1 == H2,
    append([H1],X,Y),
    intersect(T1,T2,Y).

Let's simplify a little, since we can put the unification of the heads of the lists in the head of the predicate, and we don't need append since append([H1], X, Y) is the same as, [H1|X] = Y:

intersect([H|T1],[H|T2], X) :-
    intersect(T1, T2, [H|X]).

Already we have some trouble since the recursive call should have the shorter list as the result. It was probably meant as:

intersect([H|T1],[H|T2], [H|X]) :-
    intersect(T1, T2, X).

But even so, although improved, it's making the assumption that same elements will be in tandem with each other in the two lists, which may not be the case.

One alternative approach would be to use member/2 and delete/3:

intersect([], _, []).
intersect([H|X], Y, Z) :-
    member(H, Y)
->  delete(Y, H, Y1),
    intersect(X, Y1, Z1),
    Z = [H|Z1]
;   intersect(X, Y, Z).

Here, if the current head of the first list is a member of the second, we remove all occurrences of this element from the second list and determine the intersection of that result with the rest of the first list, which becomes the tail of the result of the clause. Otherwise, we intersect the tail of the first list with the second.

Note that this is an somewhat imperative (and probably a little naive) approach to the problem, and works in the imperative sense, "Given two lists X and Y, find their intersection". But it's not relational or declarative ("Z is the intersection of X and Y"), which would be Prolog's real strength.

As far as your question about avoiding "writing" the results, you can see when you execute a predicate in prolog, it will show you already the possible instanatiations of variables that make it true. So no writing necessary.

Upvotes: 1

Related Questions