Prolog: check if two lists have the same elements

Question

I am new to Prolog and I am having a problems checking if two lists have exactly the same elements. It is possible for the elements to be in different orders. I have this code:

myremove(X, [X|T], T).   
myremove(X, [H|T], [H|R]) :-
   myremove(X, T, R).

 same_elements([], []).
 same_elements([H1|T1], L2) :-      
    myremove(H1, L2, Nl2),  
    same_elements(T1, Nl2).

It works except that

?- same_elements([b,c,a], X).

causes an out of memory error after returning the first result. So then I tried to narrow down the result set by checking that the length of the lists are equal and checking that H1 is a member of L2:

mylength([], 0).
mylength([_|T], R) :-
   mylength(T, Nr),
   R is Nr+1.

mymember(X, [X|_]).
mymember(X, [_|T]) :-
   mymember(X, T).

same_elements([], []).
same_elements([H1|T1], L2) :- 
   mylength([H1|T1], X),
   mylength(L2, Y),
   Y = X,
   mymember(H1, L2),
   myremove(H1, L2, Nl2),
   same_elements(T1, Nl2).

Now both

?- same_elements([b,c,a], X).
?- same_elements(X, [b,c,a]). 

return all of the results, but then they just hang at the end. Is there a better way to do this?

Answer 1

Short answer: Yes.

But, before going into this, there is a more interesting question around: How did you find those problems? You must have been really lucky to find them! I tried:

?- same_elements([a,b,c,d,e,f,g],Xs).
Xs = [a, b, c, d, e, f, g] ;
Xs = [a, b, c, d, e, g, f] ;
Xs = [a, b, c, d, f, e, g] ;
Xs = [a, b, c, d, g, e, f] ;
...

... and was only overwhelmed by the solutions produced. No, I did not have the patience to go through all answers. But there is a simpler way to test a concrete query: Simply remove the answers and only concentrate on whether or not the query stops. To this end, I add the goal false:

?- same_elements([a,b,c,d,e,f,g],Xs), false.

Now, we will never see any solution. But we might observe the termination of the query. Alas, this query now probably loops. At least we no longer wade through irrelevant solutions.

To further narrow down the reason for non-termination, we will add false goals into your program. That modified program is called a failure slice. In this manner we try to narrow down the part that is responsible for non-termination. If we succeed in adding the false goals such that the program still does not terminate, we will have an excellent clue how to fix the problem. For example:

same_elements([], []).
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X), false,
  mylength(L2, Y),
  Y = X,
  mymember(H1, L2),
  myremove(H1, L2, Nl2),
  same_elements(T1, Nl2).

So this is almost your program, except that there is a goal false in it. The goals behind false are striked through to make clear that they are irrelevant.

Now, the query terminates:

?- same_elements([a,b,c,d,e,f,g],Xs), false.
false.

So, we removed too much already. Next try:

same_elements([], []).
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X),
  mylength(L2, Y), false,
  Y = X,
  mymember(H1, L2),
  myremove(H1, L2, Nl2),
  same_elements(T1, Nl2).

Now, the query does not terminate!

That means: Don't look at the remaining parts of your program. Whatever is written there, cannot undo this loop!

So we can now ponder about the visible part: It does neither terminate for

?- same_elements([a,b,c,d,e,f,g],Xs).

nor for

?- same_elements(Xs,[a,b,c,d,e,f,g]).

And the culprit is just this very tiny part of the program.

Your idea was to ensure that both lists are of same length.

Instead of using a length-predicate, define a new one:

list_same_length([], []).
list_same_length([_|Xs], [_|Ys]) :-
    list_same_length(Xs, Ys).

This now terminates for "both directions".