BSD-3-Clause licensed by Don Stewart
Maintained by Sean Leather

Module documentation for

There are no documented modules for this package.

Difference Lists in Haskell

Hackage Hackage dependencies Travis CI


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

See for recent changes.



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


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


Change Log

Version (2019-03-29) Martyrs’ Day in Madagascar

Package changes

  • Change QuickCheck upper bound from 2.13 to 2.14

Version (2018-09-13) Day of the Programmer

Package changes

  • Change QuickCheck upper bound from 2.12 to 2.13

Version (2018-01-19) Kokborok Day

Package changes

  • Change QuickCheck upper bound from 2.11 to 2.12
  • Make Data.DList trustworthy (Bertram Felgenhauer)
  • Remove quickcheck-instances dependency for tests

Version (2017-07-04) Independence Day in the United States

Package changes

  • Change QuickCheck upper bound from 2.10 to 2.11 and import the Arbitrary NonEmpty instance from quickcheck-instances for 2.10
  • Fix stimes property in test suite (Oleg Grenrus)

Version (2016-09-04) World Sexual Health Day

Package changes

Version (2016-07-29) 58th Anniversary of the Creation of NASA

Package changes

  • Change QuickCheck lower bound to 2.9 for GHC >= 8 (base >= 4.9) (Adam Bergmark)

Version 0.8 (2016-07-17) Constitution Day in South Korea

New features

  • Add pattern synonyms Nil and Cons for GHC >= 7.8
  • Add Semigroup instance for GHC >= 8 (base >= 4.9)
  • Use inflexible instance for IsString to improve support for overloaded strings (Baldur Blöndal)

Package changes

  • Change QuickCheck upper bound from 2.9 to 2.10

Development changes

  • Add -Wall -Werror testing
  • Add testing for GHC 8.0.1 to Travis-CI

Version (2015-08-23) International Day for the Remembrance of the Slave Trade and its Abolition

Package changes

Version (2015-03-19) St. Joseph’s Day

Package changes

  • Change QuickCheck upper bound from 2.8 to 2.9

Version 0.7.1 (2014-06-28) 100th Anniversary of the Assassination of Franz Ferdinand

New features

Version (2014-03-24) World Tuberculosis Day

Package changes

  • Change QuickCheck upper bound from 2.7 to 2.8

Version 0.7 (2014-03-17) St. Patrick’s Day

New features

  • Add NFData instance (and deepseq dependency)
  • Add IsString instance
  • Remove deprecated entities

Version (2013-12-01) World AIDS Day

Package changes

Version 0.6 (2013-11-29) Black Friday

Development changes

Package changes

  • Stop supporting base < 2
  • Fix tests and use cabal test
  • Add scripts for running hpc
  • Update documentation

New features

  • New type class instances: Eq, Ord, Read, Show, Alternative, and Foldable
  • New function apply to use instead of unDL


  • Deprecate DList constructor and record selector to make it abstract (see #4)
  • Deprecate maybeReturn which is not directly relevant to dlists
comments powered byDisqus