PROLOG: Determining if elements in list are equal if order does not matter

Question

I'm trying to figure out a way to check if two lists are equal regardless of their order of elements.

My first attempt was:

areq([],[]).
areq([],[_|_]).
areq([H1|T1], L):- member(H1, L), areq(T1, L).

However, this only checks if all elements of the list on the left exist in the list on the right; meaning areq([1,2,3],[1,2,3,4]) => true. At this point, I need to find a way to be able to test thing in a bi-directional sense. My second attempt was the following:

areq([],[]).
areq([],[_|_]).
areq([H1|T1], L):- member(H1, L), areq(T1, L), append([H1], T1, U), areq(U, L).

Where I would try to rebuild the lest on the left and swap lists in the end; but this failed miserably.

My sense of recursion is extremely poor and simply don't know how to improve it, especially with Prolog. Any hints or suggestions would be appreciated at this point.

Answer 1

As a starting point, let's take the second implementation of equal_elements/2 by @CapelliC:

equal_elements([], []).
equal_elements([X|Xs], Ys) :-
   select(X, Ys, Zs),
   equal_elements(Xs, Zs).

Above implementation leaves useless choicepoints for queries like this one:

?- equal_elements([1,2,3],[3,2,1]).
true ;                                 % succeeds, but leaves choicepoint
false.

What could we do? We could fix the efficiency issue by using selectchk/3 instead of select/3, but by doing so we would lose logical-purity! Can we do better?

We can! Introducing selectd/3, a logically pure predicate that combines the determinism of selectchk/3 and the purity of select/3. selectd/3 is based on if_/3 and (=)/3:

selectd(E,[A|As],Bs1) :-
    if_(A = E, As = Bs1, 
               (Bs1 = [A|Bs], selectd(E,As,Bs))).

selectd/3 can be used a drop-in replacement for select/3, so putting it to use is easy!

equal_elementsB([], []).
equal_elementsB([X|Xs], Ys) :-
   selectd(X, Ys, Zs),
   equal_elementsB(Xs, Zs).

Let's see it in action!

?- equal_elementsB([1,2,3],[3,2,1]).
true.                                  % succeeds deterministically

?- equal_elementsB([1,2,3],[A,B,C]), C=3,B=2,A=1.
A = 1, B = 2, C = 3 ;                  % still logically pure
false.

---

Edit 2015-05-14

The OP wasn't specific if the predicate should enforce that items occur on both sides with the same multiplicities. equal_elementsB/2 does it like that, as shown by these two queries:

?- equal_elementsB([1,2,3,2,3],[3,3,2,1,2]).
true.
?- equal_elementsB([1,2,3,2,3],[3,3,2,1,2,3]).
false.

If we wanted the second query to succeed, we could relax the definition in a logically pure way by using meta-predicate tfilter/3 and reified inequality dif/3:

equal_elementsC([],[]).
equal_elementsC([X|Xs],Ys2) :-
   selectd(X,Ys2,Ys1),
   tfilter(dif(X),Ys1,Ys0),
   tfilter(dif(X),Xs ,Xs0),
   equal_elementsC(Xs0,Ys0).

Let's run two queries like the ones above, this time using equal_elementsC/2:

?- equal_elementsC([1,2,3,2,3],[3,3,2,1,2]).
true.
?- equal_elementsC([1,2,3,2,3],[3,3,2,1,2,3]).
true.

---

Edit 2015-05-17

As it is, equal_elementsB/2 does not universally terminate in cases like the following:

?- equal_elementsB([],Xs), false.         % terminates universally
false.    
?- equal_elementsB([_],Xs), false.        % gives a single answer, but ...
%%% wait forever                          % ... does not terminate universally

If we flip the first and second argument, however, we get termination!

?- equal_elementsB(Xs,[]), false.         % terminates universally
false.
?- equal_elementsB(Xs,[_]), false.        % terminates universally
false.

Inspired by an answer given by @AmiTavory, we can improve the implementation of equal_elementsB/2 by "sharpening" the solution set like so:

equal_elementsBB(Xs,Ys) :-
   same_length(Xs,Ys),
   equal_elementsB(Xs,Ys).

To check if non-termination is gone, we put queries using both predicates head to head:

?- equal_elementsB([_],Xs), false.
%%% wait forever                          % does not terminate universally

?- equal_elementsBB([_],Xs), false.
false.                                    % terminates universally

Note that the same "trick" does not work with equal_elementsC/2, because of the size of solution set is infinite (for all but the most trivial instances of interest).

Answer 2

A simple solution using the sort/2 ISO standard built-in predicate, assuming that neither list contains duplicated elements:

equal_elements(List1, List2) :-
    sort(List1, Sorted1),
    sort(List2, Sorted2),
    Sorted1 == Sorted2.

Some sample queries:

| ?- equal_elements([1,2,3],[1,2,3,4]).
no

| ?- equal_elements([1,2,3],[3,1,2]).    
yes

| ?- equal_elements([a(X),a(Y),a(Z)],[a(1),a(2),a(3)]).
no

| ?- equal_elements([a(X),a(Y),a(Z)],[a(Z),a(X),a(Y)]).
yes