Search code examples
prolog

Difference function in prolog for multisets

I want to calculate the difference between two lists -
Here is my attempt at it

difference(X, [], X).
difference(H,[S|T],H):-
 del(S, H, H2),
 difference(H2, T, H2).

del(Y,[Y],[]).
del(X,[X|L1],L1).
del(X,[Y|L],[Y|L1]):-del(X,L,L1).

But when I call it difference([a,a,b,b,b,c,d,d],[b,b,c,c,c,d,d,e],X). false. It returns false instead of giving the difference.
For this case the answer should be {a, a, b}

Solution

  • Try the following code:

    difference(A, [], A).
difference(A, [X|C], D) :- del(X, A, B), difference(B, C, D).

del(_, [], []).
del(X, [X|B], B).
del(X, [Y|B], [Y|C]) :- X \= Y, del(X, B, C).

    Running example:

    ?- difference([a,a,b,b,b,c,d,d],[b,b,c,c,c,d,d,e],X).
X = [a, a, b] ;
false.