SICStus Prolog Lists

Question

Having trouble understanding how Prolog works. I'm tryig to write a rule that takes three lists of integers as input (representing sets) and puts the integers that belong to both the first and second list in the third list.

Example:

?-inter([10,20,30,40],[10,50,40,60], List3 )
List3 = [10, 40]

So far I have this, that can recognize if a list contains a certain letter:

mymember(X,[X|T]).
mymember(X,[H|T]) :- mymember(X,T).

Answer 1

Try something like this, using the builtins member/2 and setof\3:

set_intersection( As , Bs , Xs ) :-
  set_of( X , ( member(X,As) , member(X,Bs) ) , Xs )
  .

One should note that this will fail if the lists As and Bs have no elements in common. An alternative would be use findall/3 rather than set_of/3. findall/3 will hand back and empty list rather than failure if the goal is not satisfied:

set_intersection( As , Bs , Xs ) :-
  findall( X , ( member(X,As) , member(X,Bs) ) , Xs )
  .

However findall/3 returns a bag (duplicates are allowed) rather than a set (no duplicates allowed), so if your two source lists aren't sets, you won't get a set out.

member/2 is a builtin predicate that unifies its first argument with an element of the list — the equivalent of

member(X,[X|_).
member(X,[_|Xs) :- member(X,Xs) .

And, finally, as @chac noted in his answer, you can recursively traverse the list.

set_intersection( [] , _ , [] ) .            % the intersection of the empty set with anything is the empty set.
set_intersection( [A|As] , Bs , [A|Xs] ) :-  % if the list is non-empty,
  member(A,Bs) ,                             % - and A is a member of the 2nd set
  ! ,                                        % - we cut off alternatives at this point (deterministic)
  set_intersection( As , Bs , Xs )           % - and recurse down on the tail of the list.
  .
set_intersection( [_|As] , Bs , Xs ) :-      % if the list is non-empty, and A is NOT a embmer of the 2nd set
  set_intersection( As , Bs , Xs )           % we just recurse down on the tail of the list.
  .

@chac's technique builds the result list as he goes, something like:

[a|X]
[a,b|X]
[a,b,c|X]

The final unification, the special case of the empty list unifies the unbound tail of the list with [] making the list complete, so the final [a,b,c|X] becomes

[a,b,c]

A little prolog magic. An alternative that might be easier to understand is to use a worker predicate with an accumulator:

%
% set_intersection/3: the public interface predicate
%
set_intersection( As , Bs , Xs ) :-
   set_intersection( As , Bc , [] , T ) % we seed our accumulator with the empty list here
   .


%
% set_intersection/4: the private worker bee predicate
%    
set_intersection( []     , _  , T , Xs ) :-   % since our accumulator is essentially a stack
  reverse(T,Xs)                               % we need to reverse the accumulator to 
  .                                           % put things in the expected sequence
 set_intersection( [A|As] , Bs , T  , Xs ) :-
  member( A, Bs ) ,
  ! ,
  T1 = [A|T] ,
  set_intersection( As , Bs , T1 , Xs )
  .
set_intersection( [_|As] , Bs , T , Xs ) :-
  set_intersection( As , Bs , T , Xs )
  .

Answer 2

inter(Xs, Ys, Zs) will be true when each element in Zs also is in Xs and in Ys.

But Zs are unknown, then a more constructive approach is required. Here it is: iterate on Xs and store in Zs each element that is in Ys.

An example of iteration is mymember/2, you can see that it requires a recursive predicate. The other idiomatic part of the above statement is store in Zs, Prolog has a peculiar way to do such things, using pattern matching.

inter([X|Xs], Ys, [X|Zs]) :-
   mymember(X, Ys), inter(Xs, Ys, Zs).

You will need to complete inter/3 with other 2 clauses: base recursion, i.e. when all Xs elements have been processed, and the case where X is not a member of Ys.

Answer 3

There's actually an inbuilt library to sort that all out for you, known as ordsets.

inter(X, Y, Z) :-
    list_to_ord_set(X, L1),
    list_to_ord_set(Y, L2),
    ord_intersection(L1, L2, Z).

Using your example input you get the following

| ?- inter([10,20,30,40],[10,50,40,60],X).
X = [10,40] ? ;
no