CODEWITHSUNDEEP
listrecursionprolog
deckardc
deckardc

Reputation: 29

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

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!

Upvotes: 0

Views: 1681

Answers (1)

lurker
lurker

Reputation: 58324

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

Upvotes: 1

Related Questions