Как создать предикат «пересечение 2 списков»?

Question

Я пытаюсь сделать пересечение двух списков (то есть список C содержит те и только те элементы, которые находятся в A и B), но, насколько я понимаю, я получаю дизъюнкцию из 2 списков + любое количество любых элементов в C .

Предназначен для работы как: (!? Я считаю, что X должен перебирать ВСЕ член C)

• , если X находится в C, то оно должно быть как в а и в В.
• предиката : d(A,B,C) :- (member(X,D)->member(X,A),member(X,B)).

Можете ли вы сказать: Является ли мое предложение и предикат не равными или я сделал еще одну ошибку?

пример:

?- [user]. 

|: d(A,B,C) :- (member(X,D)->(member(X,A),member(X,B))). 
|: % user://1 compiled 0.01 sec, 612 bytes 
true. 

?- d([a,b],[b,c],C) 
| . 
C = [b|_G21] . 

?- d([a,b],[b,c],[b]). 
true . 

Answer 1

O(NlogN) раствор с дубликатами удалены:

% untested 
intersection(A, B, O) :- 
    sort(A, AS), 
    sort(B, BS), 
    intersection1(AS, BS, O). 

intersection1(A, B, O) :- 
    ( A = [AH|AT], 
     B = [BH|BT] 
    -> ( AH == BH 
     -> O = [AH|OT], 
       intersection1(AT, BT, OT) 
     ; ( AH @< BH 
       -> intersection1(AT, B, O) 
       ; intersection1(A, BT, O))) 
    ; O = []). 

Answer 2

ваш предикат д/3 следует изменить в конструктивных терминах, так как Prolog это 'кортеж сразу' реляционный язык:

d(X,Y,Z) :- findall(E, (member(E,X), memberchk(E,Y)), Z). 

, что дает

?- d([a,b],[b,c],C). 
C = [b]. 

memberchk/2 это детерминированный вариант member/2, используемый здесь, чтобы перечислить все элементы X». Вы могли бы лучше понять разницу, если вы замените memberchk на член и попробуйте вызвать d/3 со списками, содержащими дубликаты.

findall/3 это более простой конструктор списка «все решения».

Answer 3

Мне нравится решение, предложенное @salva, хотя я бы сделать более простую сортировку-и-слияние, зажатия ничего, что не соответствует вместо:

intersect(As , Bs , Cs) :- 
    sort(As , SortedAs) , 
    sort(Bs , SortedBs) , 
    merge(SortedAs , SortedBs , Cs) 
    . 

merge([]  , []  , []). 
merge([]  , [_|_] , []). 
merge([_|_] , []  , []). 
merge([C|As] , [C|Bs] , [C|Cs]) :-   merge( As ,  Bs , Cs) . 
merge([A|As] , [B|Bs] , Cs ) :- A @< B , merge( As , [B|Bs] , Cs) . 
merge([A|As] , [B|Bs] , Cs ) :- A @> B , merge([A|As] , Bs , Cs) .