Prolog program to find equality of two lists in any order

Question

I wanted to write a Prolog program to find equality of two lists, where the order of elements
doesn't matter. So I wrote the following:

del(_, [], []) .
del(X, [X|T], T).  
del(X, [H|T], [H|T1]) :-
   X \= H,
   del(X, T, T1).

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

equal([], []).  
equal([X], [X]).  
equal([H1|T], L2) :-
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).  

But when I give input like equal([1,2,3],X)., it doesn't show all possible values of X. Instead, the program hangs in the middle. What could be the reason?

Answer 1

isSubset([],_).
isSubset([H|T],Y):-
    member(H,Y),
    select(H,Y,Z),
    isSubset(T,Z).
equal(X,Y):-
    isSubset(X,Y),
    isSubset(Y,X).

Answer 2

Try using predicate that checks if one of sets is a permutation of other set:

delete(X, [X|T], T).

delete(X, [H|T], [H|S]):-
    delete(X, T, S).


permutation([], []).

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

(Predicate taken from http://www.dreamincode.net/code/snippet3411.htm)

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

Answer 3

The actual reason for the non-termination that you observed is this: the following clause does not constrain L2 in any way, shape, or form.

equal([H1|T], L2) :- 
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).

So your query ?- equal([1,2,3], X). implies proving the goal member(_, L2) which does not terminate universally. Therefore equal([1,2,3], X) cannot terminate universally, too!

For more information on how to explain non-termination of Prolog code read about failure-slice!

---

PS. Looking at the termination problem from a different angle, we see that the non-termination is, in fact, a necessary consequence in this case.

Why? Because you do not constrain the number of multiplicities, which makes the solution set infinite in size. The set cannot be represented by a finite number of answers (provided you do not permit delaying goals).

Answer 4

If you don't care about the multiplicities of the list elements, check for sufficient instantiation with ground/1, enforce it with iwhen/2, and eliminate duplicates with sort/2 like so:

same_elements(As, Bs) :-
   iwhen(ground(As+Bs), (sort(As,Es),sort(Bs,Es))).

Sample use with SWI Prolog 8.0.0:

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

?- same_elements([a,b,b,a], [b,a,b,e]).
false.

?- same_elements([a,b,b,a], Xs).
ERROR: Arguments are not sufficiently instantiated

Answer 5

Try this:

equal([],[]).
equal([Ha|Ta],[Hb|Tb]) :-
   Ha = Hb, lequal(Ta,Tb).

Answer 6

How about:

equal(X, Y) :-
    subtract(X, Y, []),
    subtract(Y, X, []).

Answer 7

So why does equal([1,2,3], X) not terminate universally with your code?

Let's look at a failure-slice of your code! What are failure slices? Here's the tag info:

A failure-slice is a fragment of a Prolog program obtained by adding some goals false. Failure-slices help to localize reasons for universal non-termination of a pure monotonic Prolog program. They also help to give a lower bound for the number of inferences needed. It is a concrete program-slicing technique.

To create a failure slice:

• we insert false goals into the program
• while making sure that the fragment does not terminate with above goal.

del(_, [], [])  :- false.
del(X, [X|T], T) :- false.
del(X, [H|T], [H|T1]) :- false,
   dif(X, H),                    % note that the OP originally used `X \= H`
   del(X, T, T1).

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

equal([], []) :- false.
equal([X], [X]) :- false.
equal([H1|T], L2) :-
   member(H1, L2), false,
   del(H1, L2, L3),
   equal(T, L3).  

?- equal([1,2,3], _), false.     % note that `false` is redundant ...
** LOOPS **                      % ... as above `equal/2` cannot succeed.

So... what does above failure slice tell us? It says:

• To make the goal equal([1,2,3], X) terminate universally ...
• ... we must change at least one of the remaining parts (the ones not striked-through)!

Answer 8

I suggest using built-in predicate msort/2, then comparing the lists. It takes O(nlogn) time on SWI Prolog, whereas checking unsorted lists naively element-by-element would take O(n²) time.

lists_equal(List1, List2) :-
    msort(List1, Sorted1),
    msort(List2, Sorted2),
    Sorted1=Sorted2.

Here, sorting lists takes O(nlogn) time, and comparing them takes O(n) time on SWI Prolog, I don't know about other implementations.

Answer 9

Briefly

equal([],[]).
equal([H|T],[H|T1]):-equal(T,T1).