Implementing Difference Lists in Prolog

Di fference lists are not difficult conceptually. Just as we are free to think of the integer 5 as the di fference between, say, 7 and 2 (represented by 7-2), so too we can think of the list [1,3,2] as the diff erence between, say, [1,3,2,5,4] and [5,4] (represented as [1,3,2,5,4]-[5,4]). This representation of lists becomes rather useful when we use it in its most general form, where the list being subtracted is an uninstantiated variable. By unifying this variable with the head of another diff erence list, we can implement a very efficient list append function.

So much so easy. The tricky part is when we come to implement predicates that use di fference lists instead of ordinary lists. Consider the following predicate that counts the number of elements in a di fference list.

For an ordinary list this would be easy:

count([], 0).
count([H|T], N) :- count(T,M), N is M+1.

One might try to adapt this for di fference lists as follows:

count(X-X, 0).
count([H|T]-T1, N) :- count(T-T1, M), N is M+1.

However, this fails; the query ?-count([1,2,3|A]-A, N) gives utterly bogus results and fails to terminate. One fix is to instantiate A to a ground term before executing the query. Then, the execution of ?-count([1,2,3]-[],N) gives the desired result. However, we are not particularly happy with our ‘fix’ because we are prohibited from using the general di fference lists that we described above.

The reason our original query failed has to do with Prolog’s unifi cation. The problem is that the term [1,2,3|A]-A is in fact able to unify with the supposedly empty di fference list X-X. Prolog is able to achieve this by foregoing the occurs-check and setting A to [1,2,3,1,2,3,1,2,3,...]. On the flip side, when we invoke the query ?-count(A-A, N), we also get bogus results, and that’s because Prolog can unify A-A with [H|T]-T1 in the second clause.

To rephrase, the problem is that the non-empty di fference list matches the empty di fference list pattern as well as the non-empty pattern, and the empty di fference list also matches both patterns. Note that we don’t get this problem with ordinary lists: the empty list matches [] but not [H|T], while the non-empty list matches [H|T] but not [].

The fix for both problems is to force Prolog to do the occurs-check. To make the explanation clearer, first consider a slight rewriting of our problematic program.

count(X-X1, 0) :- X=X1.
count([H|T]-T1, N) :- count(T-T1, M), N is M+1.

Now, the fix is firstly to ensure that when we unify X and X1, we perform the occurs-check, so we know that the diff erence list really is empty. Secondly, we make sure that [H|T] and T1 certainly do not unify with the occurs-check, so we can be sure that the di fference list really is non-empty.

count(X-X1, 0) :- unify_with_occurs_check(X,X1).
count([H|T]-T1, N) :- not(unify_with_occurs_check([H|T],T1)),
count(T-T1, M), N is M+1.


1 thought on “Implementing Difference Lists in Prolog”

  1. NB: We can use a cut to make the fixed program more succinct (and efficient):

    count(X-X1, 0) :- unify_with_occurs_check(X,X1), !.
    count([H|T]-T1, N) :- count(T-T1, M), N is M+1.

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s