The Haskell dlist
package defines a list-like type supporting O(1) append and snoc operations.
See ChangeLog.md for recent changes.
-
A novel representation of lists and its application to the function “reverse.” John Hughes. Information Processing Letters. Volume 22, Issue 3. 1986-03. Pages 141-144. [PDF]
This is the original source for a representation of lists as first-class functions.
-
Difference list. Wikipedia.
-
Difference lists. Haskell.org Wiki.
-
What is a DList?. Stack Overflow.
-
Using Difference Lists. Douglas M. Auclair. 2008-08-13.
-
A Sort of Difference. Edward Kmett. 2008-09-18.
-
Reference for technique wanted. Richard O'Keefe, et al. 2010-10-31.
-
24 Days of Hackage: dlist. Oliver Charles. 2012-12-14.
-
Constructing a list in a Monad. Joachim Breitner. 2013-11-13.
-
Demystifying DList. (On Reddit). Tom Ellis. 2014-01-24.
-
keepEquals with Difference Lists, Douglas M. Auclair. 2014-06-21.
- Chapter 13. Data Structures. Real World Haskell. 2008-12-05.