Prolog-get only same elements from lists

Question

I am beginner in Prolog programming. I got this program which remove same elements from list? but I want only same elements from list.

Sample query with expected answer:

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

Prolog Code:

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).

Thank You!

How about `[1,2,3,4,3,2]`? Which result do you want to get? `[2,3]` (keeping the leftmost occurrence), or `[3,2]` (keeping the rightmost occurrence) or "either one is ok"? — repeat, Dec 05 '15 at 10:15
What's the purpose of `ismember(X, SET) :- member(X, SET).`? Have you made any attempt at changes to that existing code to try to solve your problem? — lurker, Dec 05 '15 at 13:14

score 3 · Answer 1 · edited May 23 '17 at 10:27

The following is derived from this answer to the related question "Remove unique elements only".

Using tpartition/4 in tandem with if_/3 and (=)/3, we define remove_uniq/2 like this:

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

Sample queries:

:- 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]).

CapelliC · Answer 2 · 2015-12-05T16:14:42.447

2

quick and dirty

?- 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].

Is a specialization of 'generate and test' pattern.

How about performance ?

'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.

Out of curiosity, I've included remove_uniq/2, but, I think it's not strictly comparable, given the different semantic.

Using member/2 we have a quadratic complexity. The runtime efficiency of memberchk (implemented as builtin, in C) just squeeze away the filter delay: efficiency become almost linear.

append/3 instead of select/3 allows a further small improvement.

edited Dec 05 '15 at 16:14

answered Dec 05 '15 at 09:00

CapelliC

59,646
5
47
90

The comparison is rigged. Consider `?- numlist(1,1000000,Xs), time(memberchk(0,Xs)).` I get `3 inferences, 0.029 CPU in 0.029 seconds (100% CPU, 102 Lips)` and `false`. – repeat Dec 05 '15 at 17:29
Not really. I feel that two messages got mixed up: First, `setof(append&memberchk)` is faster than `setof(select&member)`. And second, when using `memberchk/2` the inference count is spuriously low. (This is what I wanted to point at with my comment.) – repeat Dec 05 '15 at 18:32
If we compare `test(100)` with `test(1000)`, we need to take the PRNG into account, too. `remove_uniq/2` is based on memberd, not member. So with 1000 integers between 10 and 100, there must be a lot of duplicates! – repeat Dec 05 '15 at 18:43
s(X) for conducting interesting experiments! – repeat Dec 05 '15 at 18:45
@repeat: thanks ! please see this [this swish pad](http://swish.swi-prolog.org/p/compare%20simple%20filter%20out%20uniques%20in%20random%20list.swinb). I've changed the density of random base (see test/1), but remove_uniq doesn't handle it very well. I got `?- test(10000). ... 129,561,295 inferences` – CapelliC Dec 05 '15 at 20:08
I understand. I don't expect it to. In general, this use case is a kind of worst case scenario for remove_uniq (few to no duplicates). I will add a quasi "best case" into the pad. (for the sake of completeness). – repeat Dec 05 '15 at 21:14
In the swish pad of yours, I split `remove_uniq` into two variants `remove_uniq1` and `remove_uniq2`. `remove_uniq1` actually calls `if_/3`, `remove_uniq2` is "compiled by hand". Effect on timing: ~32s -> ~7s. – repeat Dec 05 '15 at 22:00

Prolog-get only same elements from lists

2 Answers2