How to get values existing in two lists

Question

I have two lists with song names and the singer - top 10 for EU and top 10 for US. The result should be a list containing the songs which exists in both lists.

Here are the predicates which sets the lists:

top10us([
    song(all_About_That_Bass, "Meghan Trainor"),
    song(shake_It_Off, "Taylor Swift"),
    song(black_Widow, "Iggy Azalea Featuring Rita Ora"),
    song(bang_Bang, "Jessie J, Ariana Grande & Nicki Minaj"),
    song(anaconda, "Nicki Minaj"),
    song(habits, "Tove Lo"),
    song(dont_Tell_Em, "Jeremih Featuring YG"),
    song(animals, "Maroon 5"),
    song(stay_With_Me, "Sam Smith"),
    song(break_Free, "Ariana Grande Featuring Zedd")
]).

top10eu([
    song(prayer_In_C, "Lilly Wood & Prick"),
    song(lovers_On_The_Sun, "David Guetta & Sam Martin"),
    song(chandelier, "Sia"),
    song(rude, "Magic!"),
    song(stay_With_Me, "Sam Smith"),
    song(maps, "Maroon 5"),
    song(all_Of_Me, "John Legend"),
    song(all_About_That_Bass, "Meghan Trainor"),
    song(a_Sky_Full_Of_Stars, "Coldplay"),
    song(bailando, "Enrique Iglesias")
]).

Here are my two attempts to write a predicate doing the job.

Attempt 1:

member(ITEM,[song(ITEM,_)|_],1).
member(_,[],0).
member(ITEM,[_|T],R):-
    member(ITEM,T,R).

both([],[],[]).
both([song(NAME,_)|T1], L2,[NAME|T3]):-
    member(NAME,L2,R),R=1,both(T1, L2, T3).
both([_|T], L2, T3):-
    both(T, L2, T3).

?- top10eu(L1),top10us(L2),both(L1,L2,RESULT),write(RESULT). // the result is false here

Attempt 2:

both(_,[],[],[]).
both(ORIGINAL,[_|T],[],OUTPUT):-
    both(ORIGINAL,T,ORIGINAL,OUTPUT).
both(ORIGINAL, [song(NAME,SINGER)|T1], [song(NAME,_)|T2],[NAME|T3]):-
    both(ORIGINAL, [song(NAME,SINGER)|T1], T2, T3).
both(ORIGINAL, L1, [_|T2], T3):-
    both(ORIGINAL, L1, T2, T3).
?- top10eu(L1),top10us(L2),both(L1,L1,L2,RESULT),write(RESULT). // here a list is returned, but with wrong elements.

I'm hanging my head in wall for hours and hours and can't solve this issue. Could someone more into prolog take a look? I believe this is not too concrete, as the main question is how to get values existing in two lists.

EDIT: My 2nd try happens to be working, but I was calling it with bad parameter list. Calling it with ?- top10eu(L1),top10us(L2),both(L2,L1,L2,RESULT),write(RESULT). returns the correct list: RESULT = [stay_With_Me, all_About_That_Bass]

Anyway, is there more elegant way of doing this?

How about `top10eu(L1), top10us(L2), findall(Song, (member(Song, L1), member(Song, L2)), Songs)`? — Daniel Lyons, Oct 14 '14 at 18:55
@DanielLyons: Wow! I didn't know about findall() nor member(). It does fantastic job, but how to get just the song names, without the artist? The result must be `[stay_With_Me, all_About_That_Bass]`. Can you post this as answer so I can select it? — Stanimir Stoyanov, Oct 14 '14 at 19:10
@CapelliC: I'm using swi-prolog interpreter, and there is `intersection/3`. Same question as for Daniel's comment - how can I get just the song names? — Stanimir Stoyanov, Oct 14 '14 at 19:19
@StanimirStoyanov: you're right, I mispelled the name. Sorry — CapelliC, Oct 14 '14 at 19:19
using findall, it's easier than intersection: ... findall(Song, (E = song(Song,_), member(E, L1), member(E, L2)), Songs) — CapelliC, Oct 14 '14 at 19:21
@CapelliC: works like a charm. I have a lot to learn in Prolog. Could you please post this as answer? — Stanimir Stoyanov, Oct 14 '14 at 19:24

score 2 · Accepted Answer · answered Oct 14 '14 at 19:45

a join between two unsorted lists is easily obtained with the help of library predicates:

both(L1,L2,L) :-
 findall(E, (member(E, L1), memberchk(E, L2)), L).

to extract only part of the matched structures, or to perform more elaborate matching, we can refine the goal:

bothSong(L1,L2,L) :-
 findall(Song, (E = song(Song, _), member(E, L1), memberchk(E, L2)), L).

note that only songs having the same author will be retrieved. This because the variable E will bind to song(Title, Author).

score 2 · Answer 2 · answered Oct 14 '14 at 20:45

To find the intersection two lists, you could say say something like this:

intersection( []     , _  , []     ) .  % once the source list is exhausted, we're done.
intersection( [X|Xs] , Ys , [X|Zs] ) :- % otherwise, add X to the results...
  member(X,Ys)                          % - if X is found in Y (built-in predicate)
  ! ,                                   % - cut off alternatives
  intersection(Xs,Ys,Zs)                % - recurse down
  .                                     %
intersection( [_|Xs] , Ys , Zs     ) :- % otherwise (X not in Y), discard X
   intersection(Xs,Ys,Zs)               % - and recurse down
   .                                    % Easy!

If you're not allowed to use the built-in member/2, it can be pretty trivial so just roll your own:

member(X,[X|_]) :- ! .
member(X,[_|L]) :- member(X,L) .

But from your post, it looks like you might want to do a little remodelling of your data structure, along these lines, making it a bunch of facts:

top10( us , all_About_That_Bass   , "Meghan Trainor"                        ).
top10( us , shake_It_Off          , "Taylor Swift"                          ).
top10( us , black_Widow           , "Iggy Azalea Featuring Rita Ora"        ).
top10( us , bang_Bang             , "Jessie J, Ariana Grande & Nicki Minaj" ).
top10( us , anaconda              , "Nicki Minaj"                           ).
top10( us , habits                , "Tove Lo"                               ).
top10( us , dont_Tell_Em          , "Jeremih Featuring YG"                  ).
top10( us , animals               , "Maroon 5"                              ).
top10( us , stay_With_Me          , "Sam Smith"                             ).
top10( us , break_Free            , "Ariana Grande Featuring Zedd"          ).
top10( eu , prayer_In_C            , "Lilly Wood & Prick"                   ).
top10( eu , lovers_On_The_Sun      , "David Guetta & Sam Martin"            ).
top10( eu , chandelier             , "Sia"                                  ).
top10( eu , rude                   ,  "Magic!"                              ).
top10( eu , stay_With_Me           , "Sam Smith"                            ).
top10( eu , maps                   , "Maroon 5"                             ).
top10( eu , all_Of_Me              , "John Legend"                          ).
top10( eu , all_About_That_Bass    , "Meghan Trainor"                       ).
top10( eu , a_Sky_Full_Of_Stars    , "Coldplay"                             ).
top10( eu , bailando               , "Enrique Iglesias"                     ).

Then you could just say something like:

both( Country1 , Country2 , Common ) :-
  findall(
    song(Title,Performer) ,
    ( top10(Country1,Title,Performer) ,
      top10(Country2,Title,Performer)
    ) ,
    Common
  ) .

And if you just wanted the song names:

both( Country1 , Country2 , Common ) :-
  findall(
    Title ,
    ( top10(Country1,Title,_) ,
      top10(Country2,Title,_)
    ) ,
    Common
  ) .

I'm accepting CapelliC's answer just because he was first with an complete solution last night. Thank you for the comprehensive answer. — Stanimir Stoyanov, Oct 15 '14 at 13:33

score 2 · Answer 3 · edited May 23 '17 at 11:43

What you are looking for is commonly called set intersection. Check out the related question "Intersection and union of 2 lists".

All code presented in other answers is logically impure. Logically impure code often breaks when it is used in a slightly different way than the implementer intented.

The code I presented in my answer to above question OTOH is logically pure and monotone. It thus remains logically sound even when non-ground terms are being used.

How to get values existing in two lists

3 Answers3