Difference Lists in 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.
Blogs and Discussion
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.
keepEquals with Difference Lists, Douglas M. Auclair. 2014-06-21.
- Chapter 13. Data Structures. Real World Haskell. 2008-12-05.