Prolog two list intersection - why does it keep checking?

Question

I need to find elements which exist in both lists S1 and S2 and I need to print out these elements (R). The problem is that when I type bendri([a,b,c,d],[d,b,e],R), it returns the correct result [b,d], but it doesn't stop. If you press ; symbol, then it keeps on checking again and returns b, after that - d.

Why is this happening? It should only return [b,d] and end its job.

bendri(S1,S2,R) :-
    skaiciavimai(S1,S2,R).

skaiciavimai([],_,[]).
skaiciavimai([First|Tail], S2, [First|Rest]) :-
    member(First, S2),
    skaiciavimai(Tail, S2, Rest).
skaiciavimai([_|Tail], S2, Rest) :-
    skaiciavimai(Tail, S2, Rest).

Answer 1

Your problem is that the third clause of skaiciavimai/3 also succeeds on backtracking even if the second clause succeeded. I guess you want to skip the third clause if the second clause succeeds.

To do that you can add a check in the third clause:

skaiciavimai([First|Tail], S2, Rest) :-
    \+ (member(First, S2)),
    skaiciavimai(Tail, S2, Rest).

so that the third clause fails if the head of the first list is found in S2.

Answer 2

Simple story: ; means that Prolog should look for alternatives, and since bendri(A,B,C) is defined as "C is a list of elements that occur in both A and B" (according to your definition), it will print all possible results. You can see this on the trace below (added below because the trace is rather long).

Resolution

The problem is that you introduce a decision point in your skaiciavimai/3 predicate: indeed given the first argument is a list with at least one element (of the form [_|_]), the Prolog environment can select both the second and third clause: after it has tried the skaiciavimai([First|Tail], S2, [First|Rest]) clause successfully, it can also aim to select the next clause skaiciavimai([_|Tail], S2, Rest). Since there is no predicate that prevents that selection from being successful, it will also find a solution omitting the head element. You can solve this by adding an additional constraint in the last clause:

skaiciavimai([],_,[]).
skaiciavimai([First|Tail], S2, [First|Rest]) :-
    member(First, S2),
    skaiciavimai(Tail, S2, Rest).
skaiciavimai([First|Tail], S2, Rest) :-
    \+ member(First,S2),
    skaiciavimai(Tail, S2, Rest).

The \+ means something like the logical not (although one must be careful, because not is a problematic topic in Logic Programming). So now we prevent Prolog from selecting the third clause successfully given First is a member of S2. When you use this code the result of your query is:

?- bendri([a,b,c,d],[d,b,e],R).
R = [b, d] ;
false.

We have thus altered the definition of skaiciavimai/3 it now reads something like: "C is a list of all elements that occur in A that occur in B as well." since in order to omit an element from A (third clause), it should not be a member of B.

Towards a better predicate

In Prolog the aim is to make predicate multidirectional. Indeed, you want to be able to call predicates in different directions. bendri/3 can be implemented such that bendri(A,B,[a,c]) also returns A = [a, c], B = [a, c] ;, etc. (which is the case here). In designing predicates one needs to take into account multiple uses of the predicate.

Trace

?- trace.
true.

[trace]  ?- bendri([a,b,c,d],[d,b,e],R).
   Call: (6) bendri([a, b, c, d], [d, b, e], _G360) ? creep
   Call: (7) skaiciavimai([a, b, c, d], [d, b, e], _G360) ? creep
   Call: (8) lists:member(a, [d, b, e]) ? creep
   Fail: (8) lists:member(a, [d, b, e]) ? creep
   Redo: (7) skaiciavimai([a, b, c, d], [d, b, e], _G360) ? creep
   Call: (8) skaiciavimai([b, c, d], [d, b, e], _G360) ? creep
   Call: (9) lists:member(b, [d, b, e]) ? creep
   Exit: (9) lists:member(b, [d, b, e]) ? creep
   Call: (9) skaiciavimai([c, d], [d, b, e], _G448) ? creep
   Call: (10) lists:member(c, [d, b, e]) ? creep
   Fail: (10) lists:member(c, [d, b, e]) ? creep
   Redo: (9) skaiciavimai([c, d], [d, b, e], _G448) ? creep
   Call: (10) skaiciavimai([d], [d, b, e], _G448) ? creep
   Call: (11) lists:member(d, [d, b, e]) ? creep
   Exit: (11) lists:member(d, [d, b, e]) ? creep
   Call: (11) skaiciavimai([], [d, b, e], _G451) ? creep
   Exit: (11) skaiciavimai([], [d, b, e], []) ? creep
   Exit: (10) skaiciavimai([d], [d, b, e], [d]) ? creep
   Exit: (9) skaiciavimai([c, d], [d, b, e], [d]) ? creep
   Exit: (8) skaiciavimai([b, c, d], [d, b, e], [b, d]) ? creep
   Exit: (7) skaiciavimai([a, b, c, d], [d, b, e], [b, d]) ? creep
   Exit: (6) bendri([a, b, c, d], [d, b, e], [b, d]) ? creep
R = [b, d] ;
   Redo: (11) lists:member(d, [d, b, e]) ? creep
   Fail: (11) lists:member(d, [d, b, e]) ? creep
   Redo: (10) skaiciavimai([d], [d, b, e], _G448) ? creep
   Call: (11) skaiciavimai([], [d, b, e], _G448) ? creep
   Exit: (11) skaiciavimai([], [d, b, e], []) ? creep
   Exit: (10) skaiciavimai([d], [d, b, e], []) ? creep
   Exit: (9) skaiciavimai([c, d], [d, b, e], []) ? creep
   Exit: (8) skaiciavimai([b, c, d], [d, b, e], [b]) ? creep
   Exit: (7) skaiciavimai([a, b, c, d], [d, b, e], [b]) ? creep
   Exit: (6) bendri([a, b, c, d], [d, b, e], [b]) ? creep
R = [b] ;

Answer 3

This answer follows up on @gusbro's answer... Why not preserve logical purity? It's easy!

Simply replace the third clause by:

skaiciavimai([First|Tail], S2, Rest) :-
   non_member(First, S2),
   skaiciavimai(Tail, S2, Rest).

And define non_member/2 like this:

non_member(X, Es) :-
   maplist(dif(X), Es).

Answer 4

This is a follow-up to this logically-pure answer presented earlier.

:- use_module(library(lambda)).

bendri(Es, Fs, Xs) :-
%          ^^
%          ||
%          |+----------------+\
%          ||                ||
%          vv                vv
   tfilter(Fs+\E^memberd_t(E,Fs), Es, Xs).
%            ^^
%            || 
%            \+------------------ Fs has global scope

Sample query given by the OP:

?- bendri([a,b,c,d], [d,b,e], Xs).
Xs = [b,d].