I'm really new to Prolog and I am trying to make an isIntersection that gives me the intersection of two lists and puts the answer in the third list. I cannot use any Prolog list predicates because it's for a class and that's just the rules. This is what I have and I'm having trouble debugging and seeing why this implementation is wrong. Anyone have any ideas?
/* Checks if the item is in the list */
in(Item, [Item|Rest]).
in(Item, [Not|Rest]) :- in(Item, Rest).
/* Makes the intersection list */
isIntersection([], [], []).
isIntersection([H|R], List, [H|Final]) :-
in(H, List),
isIntersection(R, List, Final),
write(H).
isIntersection([Discard|Rest], List, Final) :-
isIntersection(Rest, List, Final),
write(Discard).
Prolog is a very versatile query language, so let's use Prolog to find the problem!
?- isIntersection([a,b],[c,b],Zs).
false.
This failure is not what we expect. To better localize the problem we might a) generalize the query or b) reduce input size. I will try generalizing it first:
?- isIntersection([a,b],Ys,Zs).
loops. % ERROR: Out of global stack
Seems we have no luck, but then this query would have to produce infinitely many lists for Ys so it might be OK to loop.
I could continue that way, but why not let Prolog do the thinking for me? I will try all possible lists:
?- length(L,_),append(Xs,Ys,L), isIntersection(Xs,Ys,Zs).
L = Xs, Xs = Ys, Ys = Zs, Zs = []
; L = Xs, Xs = [_A], Ys = Zs, Zs = []
; L = Xs, Xs = [_A, _B], Ys = Zs, Zs = []
; L = Xs, Xs = [_A, _B, _C], Ys = Zs, Zs = []
; L = Xs, Xs = [_A, _B, _C, _D], Ys = Zs, Zs = []
; ... .
So for each list length (so far), there is only one solution with Ys and Zs being an empty list... Is there any solution for Ys being larger?
?- length(L,_),Ys = [_|_], append(Xs,Ys,L), isIntersection(Xs,Ys,Zs).
loops.
So lets take the minimal missing example from above with Ys having one element:
?- isIntersection([],[a],[]).
false.
With this goal, now look at your code!
But there is another problem (after fixing above):
?- isIntersection([a],[a],Xs).
Xs = [a]
; Xs = [].
The rule discards any element! But it should only discard those that are not in List. So:
isIntersection([Discard|Rest], List, Final) :-
list_without(List,Discard), % maplist(dif(Discard),List)
isIntersection(Rest, List, Final).
list_without([], _).
list_without([E|Es], F) :-
dif(E, F),
list_without(Es, F).
Finally, always keep an eye on negative examples. Many attempts here (incorrectly) succeeds for queries like isIntersection([a],[a],[]).
(Your relation in/2 might better be called element_in/2)