Difference List
The term Difference List can refer to two different data structures in computer science. On the one hand, it describes a data structure that contains two lists and represents the difference between them. The second data structure is a functional representation of a list that enables efficient concatenation . In this case, a differences list is implemented as a one- argument function that takes a list as an argument and appends it to the front. Therefore, concatenation of difference lists of the second type is implemented as a function composition which has a constant running time .