Difference lists https://github.com/spl/dlist

Version on this page:
LTS Haskell 9.14:
Stackage Nightly 2017-11-25:
Latest on Hackage:
BSD3 licensed by Don Stewart
Maintained by Sean Leather

Module documentation for

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


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.


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


Change Log

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

  • Maintenance and development taken over by Sean Leather (Bas van Dijk)
  • Migrate repository from http://code.haskell.org/~dons/code/dlist/ to https://github.com/spl/dlist
  • Add Travis-CI (Herbert Valerio Riedel)

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
Depends on:
Used by 123 packages:
accelerate-llvm, accelerate-llvm-native, accelerate-llvm-ptx, aeson, aeson-better-errors, algebra-sql, amazonka-s3-streaming, applicative-fail, ascii-table, aws-performance-tests, binembed, bookkeeping, brick, buildable, bytestring-csv, c2hs, cao, cgrep, classy-prelude, computational-algebra, conduit-parse, configuration-tools, configurator-ng, ConstraintKinds, context-free-grammar, copilot-core, CSPM-Frontend, data-default-generics, data-default-instances-dlist, diagrams-postscript, diagrams-tikz, disposable, dlist-instances, dlist-nonempty, DnaProteinAlignment, docvim, DSH, dstring, each, embroidery, filesystem-trees, fixhs, flat, git-annex, glazier-react, glazier-react-examples, glazier-react-widget, Glob, gogol-core, graphviz, hasql, hcltest, heist, heterocephalus, HLearn-classification, hsc3-lang, hsXenCtrl, hunt-searchengine, hw-json, hw-json-lens, hw-mquery, incremental-computing, incremental-maps, inserts, intro, ipc, irc-fun-color, ivory, ivory-opts, json-rpc-generic, jukebox, kafka-client, kure, ListLike, list-tries, log-warper, luminance, marxup, moe, mono-traversable-instances, nemesis, path-io, persistable-record, powerqueue-levelmem, pseudo-boolean, purescript, quiver-groups, quoridor-hs, Rasterific, rdf, rebase, redis-resp, refurb, relational-query, relational-query-HDBC, sexp, simple-c-value, sizes, snap, solga-swagger, spata, tamarin-prover, tamarin-prover-term, tamarin-prover-theory, tamarin-prover-utils, testbench, text-ldap, text-postgresql, twee, typesafe-precure, unordered-graphs, unsequential, uri-templater, vampire, wavefront, write-buffer-core, xhb-ewmh, xml-conduit-writer, YamlReference, yesod-platform, yi-core, yi-frontend-vty, yi-mode-javascript
comments powered byDisqus