Prolog-получить только те же элементы из списков

Question

Я начинаю программировать в Прологе. У меня есть эта программа, которая удаляет те же элементы из списка? но мне нужны только те же элементы из списка.

Пример запроса с ожидаемым ответом:

?- set([1,2,3,4,2,3], Xs). 
Xs = [2,3]. 

Пролог Код:

ismember(X, SET) :- 
    member(X, SET). 

set([], []). 
set([H|T], [H|Out]) :- 
    not(ismember(H,T)), 
    set(T, Out). 
set([H|T], Out) :- 
    ismember(H, T), 
    set(T, Out). 

Спасибо!

Answer 1

быстрый и грязный

?- S=[1,2,3,4,2,3], setof(C, R^(select(C,S,R),memberchk(C,R)), L). 
S = [1, 2, 3, 4, 2, 3], 
L = [2, 3]. 

Является специализация 'создания и проверки' шаблон.

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

'slow quick and dirty'(S0, S) :- 
    setof(C, R^(select(C,S0,R),member(C,R)), S). 

'better quick and dirty'(S0, S) :- 
    setof(C, R^(select(C,S0,R),memberchk(C,R)), S). 

'still better quick and dirty'(S0, S) :- 
    setof(H, Done^H^R^(append(Done,[H|R],S0),memberchk(H,R)), S). 

test(N) :- 
    findall(R, (between(1,N,_), random_between(10,100,R)), S), 
    time('slow quick and dirty'(S, Sa)), 
    time('better quick and dirty'(S, Sb)), 
    time('still better quick and dirty'(S, Sc)), 
    Sa = Sb, Sb = Sc, 
    time(remove_uniq(S, Sd)), 
    maplist(length, [Sa, Sb, Sc, Sd], Ls), 
    writeln(Ls). 

25 ?- so:test(100). 
% 10,225 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 3506071 Lips) 
% 282 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 226231 Lips) 
% 254 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 347891 Lips) 
% 22,697 inferences, 0.018 CPU in 0.028 seconds (65% CPU, 1272020 Lips) 
[28,28,28,28] 
true. 

26 ?- so:test(1000). 
% 1,011,929 inferences, 0.275 CPU in 0.276 seconds (100% CPU, 3674049 Lips) 
% 3,015 inferences, 0.013 CPU in 0.013 seconds (98% CPU, 239535 Lips) 
% 2,924 inferences, 0.013 CPU in 0.016 seconds (82% CPU, 216598 Lips) 
% 351,724 inferences, 0.262 CPU in 0.272 seconds (96% CPU, 1343870 Lips) 
[91,91,91,91] 
true. 

Из любопытства, я включил remove_uniq/2, но, я думаю, что это не вполне сопоставимы, учитывая разные семантический.

Используя член/2, мы имеем квадратичную сложность. Эффективность исполнения memberchk (реализованная как встроенная в C) просто сжимает задержку фильтра: эффективность становится почти линейной.

append/3 вместо select/3 позволяет дальнейшее небольшое улучшение.

Answer 2

В связи с вопросом "Remove unique elements only" получено следующее сообщение: this answer.

Использование tpartition/4 в тандеме с if_/3 и (=)/3, мы определяем remove_uniq/2 так:

 
remove_uniq([], []). 
remove_uniq([E|Es], Xs0) :- 
    tpartition (= (E), Es, Ts, Fs), 
    if_ (Ts  = [], 
     Xs0 = Xs, 
     Xs0 = [E|Xs]), 
    remove_uniq(Fs, Xs). 

Примеры запросов:

:- remove_uniq([1,2,3,4,2,3], [2,3]). 
%    ^^  ^^ 
%     |-+--------- take leftmost occurrence 
%     v v   v v 
:- remove_uniq([1,2,3,4,3,2], [2,3]). 
%    ^^  ^^ 
%     |-+--------- preserve the original order 
%     v v    v v 
:- remove_uniq([5,3,2,1,2,3,2,3], [3,2]).