computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, the term difference list refers to a

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

representing a

list A list is a Set (mathematics), set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of t ...

with an efficient O(1)

concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalizations of concatenati ...

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 other 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 the usage 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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...

X as

argument An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persu ...

, 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 []. This implementation is typically used in functional programming languages such as Haskell (programming language), Haskell, although it could be used in imperative languages as well. As functions, difference lists are a Cayley representation of lists as monoids, or more specifically their transformation monoid induced by left multiplication. Examples of use are in the ''ShowS'' type in the Prelude of Haskell, and in Donald Bruce Stewart'
difference list library for Haskell

Implementation using unification

Another implementation in the logic programming language

Prolog Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics. Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...

uses unification variables.Open Lists and Difference Lists
in

Retrieved 2019-02-17 A difference list is a pair ''OpenList-Hole'', where the first element ''OpenList'' is a

containing an unbound unification variable (hole) and the second element ''Hole'' is a reference to the hole.

References

Linked lists {{datastructure-stub