Difference list

In computer science, the term difference list may refer to one of two data structures for representing lists. One of these data structures contains two lists, and represents the difference of those two lists. The second data structure is a functional representation of a list with an efficient concatenation operation. In the second approach, difference lists are implemented as single-argument functions, which take a list as argument and prepend to that list. As a consequence, concatenation of difference lists of the second type is implemented essentially as function composition, which is O(1). However, of course the list still has to be constructed eventually (assuming all of its elements are needed), which is plainly at least O(n).