Difference Lists

Appeared in Volume 6/3, August 1993

Keywords: lists.

lee@munta.cs.mu.oz.au
Lee Naish
22nd October 1992

Paul Singleton writes:
Isn't the difference list just another implementation of the abstraction called "list"?

Absolutely not. A difference pair is two (albeit related) lists, not one. With single lists you can do the following:

list1(L1),
list2(L2),
list3(L3),	% L3 ~= L2
append(L1, L2, L12),
append(L1, L3, L13).

Ie, append two different lists onto a list, getting two different results. With "difference lists" the code above will fail. If you think in terms of difference pairs its very unlikely that you will ever write such code. What does it mean to append two lists to two other lists? Code using difference pairs generally doesn't use append and in the cases it does, append is called with single lists, not pairs of lists.

In summary (intended to amuse, but may confuse):

A difference list is not a list, there is a difference.
A difference pair is not a pair, there is a difference.
A difference list is a pair (of lists).
A difference pair is a list plus another list.
A difference between "a difference pair" and "a pair of lists" (which may refer to a difference list) is the context in which they are used.