In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented using first-class functions or using unification. Whether a difference list is more efficient than another list representations depends on usage patterns. If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, then use of difference lists can improve performance by effectively "flattening" the list building computations.
Implementation using functions
A difference list f is a single-argument function append L, which when given a linked list X as argument, returns a linked list containing L prepended to X. Concatenation of difference lists is implemented as function composition. The contents may be retrieved using f .
As functions, difference lists are a Cayley representation of lists as monoids, or more specifically their transformation monoid induced by left multiplication.
Implementation using unification
Another implementation in the logic programming language Prolog uses unification variables. A difference list is a pair OpenList-Hole, where the first element OpenList is a list containing an unbound unification variable (hole) and the second element Hole is a reference to the hole.
- A Novel Representation of Lists and Its Application to the Function "Reverse" by John Hughes (1986)
- Difference Lists in Haskell (programming language)
- Open Lists and Difference Lists in Prolog Retrieved 2019-02-17