compare the elements of one list with the elements of another list in prolog

Question

First of all, I am completely a beginner at Prolog.

I am trying to compare each element of a list with each element of another list. By compare, I mean sending these 2 elements to a predicate(conflicts) I wrote. So far, I got this:

%iterate over the first list
cmp_list([],_,_).
cmp_list([X|Y],[A|B],Result):-
      cmp_list_inner(X,[A|B],Result),
      cmp_list(Y,[A|B],Result).

%iterate over the second list
cmp_list_inner(_,[],_).
cmp_list_inner(X,[A|B],S):-
    not(conflicts(X,A)), %compare
    cmp_list_inner(X,B,[X-A|S]).%if okay, add their combination, i.e X-A to the main list which will be returned

The predicate cmp_list stands for the recursion of outer list, whereas the one with inner stands for inner list. cmp_list(firstlist, secondlist, new list after the combination which will be returned.)

This doesn't work! Even though it adds the values for a single element in the first value to the main list, it doesn't append the second comparison(for the second element in the first list) to the main list which will be returned. Result should be in the form of: [X1-Y1], [X1-Y2], [X2-Y1], [X2-Y2].... where Xs are from the first list and Ys are from the second list.

Any help would be appreciated. Thanks!

lurker · Accepted Answer · 2014-03-24 18:01:29Z

1

You only need one simple predicate:

cmp_list([], [], []).              % cmp_list succeeds for two empty lists
cmp_list([H1|T1], [H2|T2], [H1-H2|R]) :-
    % cmp_list of [H1|T1] and [H2|T2] succeeds if...
    \+ conflicts(H1, H2),          % conflicts fails for H1 and H2
    cmp_list(T1, T2, R).           % cmp_list succeeds for T1 and T2, result R

% Otherwise, cmp_list fails (e.g., lists are diff length)

A little more compact would be to use the built-in predicate, maplist:

cmp_list(L1, L2, R) :-                % cmp_list succeeds on L1, L2 if...
    maplist(no_conflicts, L1, L2, R). % no_conflicts succeeds for every
                                      %   corresponding pair of L1, L2 elements

no_conflicts(X, Y, X-Y) :- \+ conflicts(X-Y).

If you just want to capture all the corresponding pairs that don't conflict and ignore the rest, then:

cmp_list([], _, []).
cmp_list([_|_], [], []).
cmp_list([H1|T1], [H2|T2], R) :-
    (   conflicts(H1, H2)
    ->  cmp_list(T1, T2, R)
    ;   R = [H1-H2|R1],
        cmp_list(T1, T2, R1)
    ).

This uses the "if-then-else" pattern in Prolog formed by grouping -> with ;. This will create a result that looks like, [x1-y1, x3-y3, ...]. You can choose however you want to form your result elements by changing this line:

R = [H1-H2|R1]

For example, R = [[H1,H2]|R1] would yield a result that looks like, [[x1,y1], [x3,y3], ...].

For the more general problem (i.e., the one you were really looking for :)), I'll start with the original code but modify it where it's needed:

%iterate over the first list
cmp_list([], _, []).
cmp_list([X|T], L2, Result):-
    cmp_list_inner(X, L2, R1),
    cmp_list(T, L2, R2),
    append(R1, R2, Result).

%iterate over the second list
cmp_list_inner(_, [], []).
cmp_list_inner(X, [A|B], R) :-
    (   conflicts(X, A)
    ->  cmp_list_inner(X, B, R)
    ;   R = [X-A|T],
        cmp_list_inner(X, B, T)
    ).

edited Mar 24, 2014 at 18:01

answered Mar 24, 2014 at 16:45

lurker

58.5k9 gold badges74 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

deckardc Over a year ago

Thanks! The result should be like [X1-Y3],[X2-Y4], [X5-Y1] etc. where Xs are in list1 and Ys are in list2. It should be a list of non conflicting pairs and pairs are all the combination of list1's elements and list2's elements. Doesn't your solution check index by index? I am trying to compare X1 with Y1,Y2,Y3.. X2 with Y1,Y2,Y3... etc.

deckardc Over a year ago

I mean, it shouldn't fail if the lists are different lengths.

lurker Over a year ago

@user3450161 do you want it to capture all that match then, and ignore those that don't?

deckardc Over a year ago

Exactly! Any pair of non conflicting elements should be in the Result in the form of [X1-Y3] etc.

deckardc Over a year ago

Thanks so that I learned if else in Prolog. However, it is still trying to match the lists with respect to their indexes. After I call the predicate, I got something like: [X1-Y1],[X2-Y2] whereas I should have something like [X1-Y1][X1-Y2][X2-Y1][X2-Y2]. What am I doing wrong? Sorry I bother you but this is my first attempt at Prolog.

|

Collectives™ on Stack Overflow

compare the elements of one list with the elements of another list in prolog

1 Answer 1

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related