Prolog: List Difference

Today I was implementing a Prolog program to find the difference between two lists.

Here is the problem statement and the expected output.

minus([1,2,3,4],[1,3],W).

W=[2,4]

yes

As a beginner in Prolog, I tend use the accumulator based approach to find the solution. Here is what I came up with spending some significant time at the Prolog interpreter and debugger.


minusAcc(L,[],_,L) :- !.
minusAcc([],_,A,A) :- !.
minusAcc([H|T],SL,A,W) :- \+memberchk(H,SL),!,
                            append([H],A,AL),
                            minusAcc(T,SL,AL,W).
minusAcc([_|T],SL,A,W) :- minusAcc(T,SL,A,W).
minus(L,SL,W) :- minusAcc(L,SL,[],W).

This program gives the expected output but does not preserve the order. It actually gives the output in the reverse order because of the inherent recursion in the program.  Following is output generated by this program.

minus([1,2,3,4],[1,3],W).

W=[4,2]

yes

Since, I wrote this routine for use in list sorting, the order did not matter and I decided to live with this program.

Meanwhile, I had a look at the implementation available on the web for the same purpose and I found the following program on stackoverflow very interesting.

minus(L,[],L) :- !.

minus([],_,[]) :- !.

minus([H|T],SL,W) :- memberchk(H,SL),!,minus(T,SL,W).

minus([H|T1],SL,[H|T2]) :- minus(T1,SL,T2).

This program gives the expected output and preserves the order too. This program also uses the classic accumulator (unlike mine) based approach, but here the result itself is the accumulator. I had to trace it on debugger for about 10 mins (this is my 2nd day on prolog) to understand the control flow. It was totally worth it!

Gem of a program! Made my weekend!

BTW, here is the gist of my Day 2 of Prolog using Seven Languages in Seven Weeks!