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?

i.e. Determining the equality of two sets – Numid Nov 18 '13 at 13:42 — Numid, Nov 18 '13 at 13:42

Mr. Berna · Accepted Answer · 2010-04-27T21:28:46.697

9

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

edited Apr 27 '10 at 21:28

answered Apr 27 '10 at 21:05

Mr. Berna

10,525
1
39
42

1

The member/2 before the select/3 is not needed. The equal/2 does not work correctly: It gives only one solution and then on redo it hangs: ?- equal([1,2,3],X). X = [1, 2, 3] ; Error: Execution aborted since memory low. Therefore voting down the answer. – Oct 06 '11 at 08:39

score 4 · Answer 2 · answered Nov 21 '11 at 18:52

4

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

answered Nov 21 '11 at 18:52

ULazdins

1,975
4
25
31

1

The link is dead. – Mateusz Piotrowski Jun 02 '18 at 21:52

score 3 · Answer 3 · answered Dec 15 '15 at 21:45

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

repeat · Answer 4 · 2019-01-30T18:43:11.597

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

score 1 · Answer 5 · edited Mar 20 '12 at 18:24

1

Try this:

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

edited Mar 20 '12 at 18:24

false

10,264
13
101
209

answered Jun 03 '10 at 21:40

score 1 · Answer 6 · answered Dec 15 '15 at 15:57

1

How about:

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

answered Dec 15 '15 at 15:57

DrBeco

11,237
9
59
76

repeat · Answer 7 · 2015-12-16T01:13:48.337

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~~)!

score 0 · Answer 8 · answered Mar 29 '14 at 19:02

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.

score 0 · Answer 9 · answered Apr 12 '14 at 05:11

0

Briefly

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

answered Apr 12 '14 at 05:11

dodushkaxy

19
3

1

This will not work if the lists contain the same items in different order. – repeat Mar 29 '15 at 15:53

Prolog program to find equality of two lists in any order

9 Answers9