CODEWITHSUNDEEP
listprolog
Ave
Ave

Reputation: 39

Prolog-get only same elements from lists

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!

Upvotes: 3

Views: 151

Answers (2)

repeat
repeat

Reputation: 18726

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

Upvotes: 3

CapelliC
CapelliC

Reputation: 60004

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.

Upvotes: 2

Related Questions