Difference lists are not difficult conceptually. Just as we are free to think of the integer 5 as the difference between, say, 7 and 2 (represented by 7-2), so too we can think of the list `[1,3,2]`

as the difference 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 difference 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 difference lists instead of ordinary lists. Consider the following predicate that counts the number of elements in a difference 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 difference 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 difference lists that we described above.

The reason our original query failed has to do with Prolog’s unification. The problem is that the term `[1,2,3|A]-A`

is in fact able to unify with the supposedly empty difference 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 difference list matches the empty difference list pattern as well as the non-empty pattern, and the empty difference 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 difference 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 difference 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.

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.