Difference Lists in Haskell

Summary

The Haskell dlist package defines a list-like type supporting O(1) append and snoc operations.

See ChangeLog.md for recent changes.

References

Research

1. 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.

Basic Introduction

1. Difference list. Wikipedia.

2. Difference lists. Haskell.org Wiki.

3. What is a DList?. Stack Overflow.

Blogs and Discussion

1. Using Difference Lists. Douglas M. Auclair. 2008-08-13.

2. A Sort of Difference. Edward Kmett. 2008-09-18.

3. Reference for technique wanted. Richard O'Keefe, et al. 2010-10-31.

4. 24 Days of Hackage: dlist. Oliver Charles. 2012-12-14.

5. Constructing a list in a Monad. Joachim Breitner. 2013-11-13.

6. Demystifying DList. (On Reddit). Tom Ellis. 2014-01-24.

7. keepEquals with Difference Lists, Douglas M. Auclair. 2014-06-21.

Books

1. Chapter 13. Data Structures. Real World Haskell. 2008-12-05.