Difference List

The term Difference List ( difference list) can refer to two different data structures in computer science. For one, it indicates a data structure that contains two lists and represents the difference between them. The second data structure is a functional representation of a list which allows efficient concatenation. In this case, a difference list is implemented as a single-argument function which takes as its argument and a list to append to this front. Therefore, the concatenation is implemented by differential lists of the second type as a function of composition, which has a constant duration.