How to find the difference between 2 lists in XSB Prolog?

We define the difference between two lists A and B as A-B = Elements in A but not B. SWI Prolog has a builtin predicate to do this in the form of subtract/3. It seems that XSB Prolog lacks this predicate. So, here is a simple alternate definition of subtract in XSB prolog-

subtract(A,B,C):- findall(X, (member(X,A), not(member(X,B))), C).

where C = A – B

Advertisements

One thought on “How to find the difference between 2 lists in XSB Prolog?

  1. I havn’t thought about it much, but I was thinking of an optimized method of doing this. You could use tabling to keep a hash of elements visited. Hmm, this is interesting since by default it is O(n^2). If you are interested, check out the concept of difference lists, it blew my mind when I learnt about it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s