BSD-3-Clause licensed by Don Stewart
Maintained by Sean Leather
This version can be pinned in stack with:dlist-1.0@sha256:124cb3aa1decebd5171b46601b1f74cca6cfae12d266ace3799b86dd05ef7cb4,3560

Module documentation for 1.0

Difference Lists

test-badge hackage-badge packdeps-badge

List-like types supporting O(1) append and snoc operations.


dlist is a Haskell package available from Hackage. It can be installed with cabal or stack.

See the change log for the changes in each version.


Here is an example of “flattening” a Tree into a list of the elements in its Leaf constructors:

import qualified Data.DList as DList

data Tree a = Leaf a | Branch (Tree a) (Tree a)

flattenSlow :: Tree a -> [a]
flattenSlow = go
    go (Leaf x) = [x]
    go (Branch left right) = go left ++ go right

flattenFast :: Tree a -> [a]
flattenFast = DList.toList . go
    go (Leaf x) = DList.singleton x
    go (Branch left right) = go left `DList.append` go right

(The above code can be found in the benchmark.)

flattenSlow is likely to be slower than flattenFast:

  1. flattenSlow uses ++ to concatenate lists, each of which is recursively constructed from the left and right Tree values in the Branch constructor.

  2. flattenFast does not use ++ but constructs a composition of functions, each of which is a “cons” introduced by DList.singleton ((x :)). The function DList.toList applies the composed function to [], constructing a list in the end.

To see the difference between flattenSlow and flattenFast, consider some rough evaluations of the functions applied to a Tree:

flattenSlow (Branch (Branch (Leaf 'a') (Leaf 'b')) (Leaf 'c'))
  = go (Branch (Branch (Leaf 'a') (Leaf 'b')) (Leaf 'c'))
  = go (Branch (Leaf 'a') (Leaf 'b')) ++ go (Leaf 'c')
  = (go (Leaf 'a') ++ go (Leaf 'b')) ++ "c"
  = ("a" ++ "b") ++ "c"
  = ('a' : [] ++ "b") ++ "c"
  = ('a' : "b") ++ "c"
  = 'a' : "b" ++ "c"
  = 'a' : 'b' : [] ++ "c"
  = 'a' : 'b' : "c"
flattenFast (Branch (Branch (Leaf 'a') (Leaf 'b')) (Leaf 'c'))
  = toList $ go (Branch (Branch (Leaf 'a') (Leaf 'b')) (Leaf 'c'))
  = toList $ go (Branch (Leaf 'a') (Leaf 'b')) `append` go (Leaf 'c')
  = unsafeApplyDList (go (Branch (Leaf 'a') (Leaf 'b'))) . unsafeApplyDList (go (Leaf 'c')) $ []
  = unsafeApplyDList (go (Branch (Leaf 'a') (Leaf 'b'))) (unsafeApplyDList (go (Leaf 'c')) [])
  = unsafeApplyDList (go (Branch (Leaf 'a') (Leaf 'b'))) (unsafeApplyDList (singleton 'c') [])
  = unsafeApplyDList (go (Branch (Leaf 'a') (Leaf 'b'))) (unsafeApplyDList (UnsafeDList ((:) 'c')) [])
  = unsafeApplyDList (go (Branch (Leaf 'a') (Leaf 'b'))) "c"
  = unsafeApplyDList (UnsafeDList (unsafeApplyDList (go (Leaf 'a')) . unsafeApplyDList (go (Leaf 'b')))) "c"
  = unsafeApplyDList (go (Leaf 'a')) (unsafeApplyDList (go (Leaf 'b')) "c")
  = unsafeApplyDList (go (Leaf 'a')) (unsafeApplyDList (singleton 'b') "c")
  = unsafeApplyDList (go (Leaf 'a')) (unsafeApplyDList (UnsafeDList ((:) 'b')) "c")
  = unsafeApplyDList (go (Leaf 'a')) ('b' : "c")
  = unsafeApplyDList (singleton 'a') ('b' : "c")
  = unsafeApplyDList (UnsafeDList ((:) 'a')) ('b' : "c")
  = 'a' : 'b' : "c"

The left-nested ++ in flattenSlow results in intermediate list constructions that are immediately discarded in the evaluation of the outermost ++. On the other hand, the evaluation of flattenFast involves no intermediate list construction but rather function applications and newtype constructor wrapping and unwrapping. This is where the efficiency comes from.

Warning! Note that there is truth in the above, but there is also a lot of hand-waving and intrinsic complexity. For example, there may be GHC rewrite rules that apply to ++, which will change the actual evaluation. And, of course, strictness, laziness, and sharing all play a significant role. Also, not every function in the dlist package is the most efficient for every situation.

Moral of the story: If you are using dlist to speed up your code, check to be sure that it actually does. Benchmark!

Design Notes

These are some notes on design and development choices made for the dlist package.

Avoid ++

The original intent of Hughes’ representation of lists as first-class functions was to provide an abstraction such that the list append operation found in functional programming languages (and now called ++ in Haskell) would not appear in left-nested positions to avoid duplicated structure as lists are constructed. The lesson learned by many people using list over the years is that the append operation can appear, sometimes surprisingly, in places they don’t expect it.

One of our goals is for the dlist package to avoid surprising its users with unexpected insertions of ++. Towards this end, there should be a minimal set of functions in dlist in which ++ can be directly or indirectly found. The list of known uses of ++ includes:

  • DList: fromList, fromString, read
  • DNonEmpty: fromList, fromNonEmpty, fromString, read

If any future requested functions involve ++ (e.g. via fromList), the burden of inclusion is higher than it would be otherwise.


The DList representation and its supporting functions (e.g. append, snoc, etc.) rely on an invariant to preserve its safe use. That is, without this invariant, a user may encounter unexpected outcomes.

(We use safety in the sense that the semantics are well-defined and expected, not in the sense of side of referential transparency. The invariant does not directly lead to side effects in the dlist package, but a program that uses an unsafely generated DList may do something surprising.)

The invariant is that, for any xs :: DList a:

fromList (toList xs) = xs

To see how this invariant can be broken, consider this example:

xs :: DList a
xs = UnsafeDList (const [])

fromList (toList (xs `snoc` 1))
  = fromList (toList (UnsafeDList (const []) `snoc` 1))
  = fromList (toList (UnsafeDList (unsafeApplyDList (UnsafeDList (const [])) . (x :))))
  = fromList (toList (UnsafeDList (const [] . (x :))))
  = fromList (($ []) . unsafeApplyDList $ UnsafeDList (const [] . (x :)))
  = fromList (const [] . (x :) $ [])
  = fromList (const [] [x])
  = fromList []
  = UnsafeDList (++ [])

The invariant can also be stated as:

toList (fromList (toList xs)) = toList xs

And we can restate the example as:

toList (fromList (toList (xs `snoc` 1)))
  = toList (UnsafeDList (++ []))
  = []

It would be rather unhelpful and surprising to find (xs `snoc` 1) turned out to be the empty list.

To preserve the invariant on DList, we provide it as an abstract type in the Data.DList module. The constructor, UnsafeDList, and record label, unsafeApplyDList, are not exported because these can be used, as shown above, to break the invariant.

All of that said, there have been numerous requests to export the DList constructor. We are not convinced that it is necessary, but we are convinced that users should decide for themselves.

To use the constructor and record label of DList, you import them as follows:

import Data.DList.Unsafe (DList(UnsafeDList, unsafeApplyDList))

If you are using Safe Haskell, you may need to add this at the top of your module:

{-# LANGUAGE Trustworthy #-}

Just be aware that the burden of proof for safety is on you.


These are various references where you can learn more about difference lists.


  • 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 published source for a representation of lists as first-class functions.


Blogs and Mailing Lists



BSD 3-Clause “New” or “Revised” License © Don Stewart, Sean Leather, contributors


Change Log


No unreleased changes at this time.


Released on 2020-07-18, Nelson Mandela International Day.


  • intercalate for DList (#43, Jacob Leach)
  • Traversable instance for DList (#45, Veronika Romashkina)
  • Data.DList.Internal for the DList implementation, Data.DList.Unsafe for exporting the DList constructor UnsafeDList and record label unsafeApplyDList (#55, #59)
  • Data.DList.DNonEmpty (#60)
  • GitHub Action for uploading a release (#74)
  • dlist-bench, a benchmark package (#71)


  • stimes for DList defined with stimesMonoid (#46, Janek Spaderna)
  • Type of tail: DList a -> DList a to DList a -> [a] (#69)
  • GitHub Action for continuous integration testing to replace Travis-CI (#47, #50)
  • GHC warning and error improvements (#72, #73)
  • Improved documentation (#55, #70, #76, #77)


  • list :: b -> (a -> DList a -> b) -> DList a -> b (#69)


Released on 2020-04-02, World Autism Awareness Day.



  • QuickCheck upper bound: 2.14 to 2.15 (a7ea60d)



Released on 2019-08-05, Independence Day in Burkina Faso.




Released on 2019-03-29, Martyrs’ Day in Madagascar.


  • QuickCheck upper bound: 2.13 to 2.14 (242511c)


Released on 2018-09-13, Day of the Programmer.


  • QuickCheck upper bound: 2.12 to 2.13 (0e2b3a5)


Released on 2018-01-19, Kokborok Day.



  • QuickCheck upper bound: 2.11 to 2.12 (3d9c8ad)
  • QuickCheck lower bound: 2.7/2.9 to 2.10 (4f92012)
  • Arbitrary, Arbitrary1 instances for NonEmpty in the test suite copied from quickcheck-instances (4f92012)


Released on 2017-07-04, Independence Day in the United States.


  • quickcheck-instances dependency in the test suite for the Arbitrary, Arbitrary1 instances for NonEmpty (5b41d0d)


  • QuickCheck upper bound: 2.10 to 2.11 (b2f791a)



Released on 2016-09-04, World Sexual Health Day.



Released on 2016-07-29, the 58th Anniversary of the Creation of NASA.



Released on 2016-07-17, Constitution Day in South Korea.




Released on 2015-08-23, International Day for the Remembrance of the Slave Trade and its Abolition.



Released on 2015-03-19, St. Joseph’s Day.


  • QuickCheck lower bound: 2.5 to 2.7 (2d8ec37)
  • QuickCheck upper bound: 2.8 to 2.9 (3176153)


Released on 2014-06-28, the 100th Anniversary of the Assassination of Franz Ferdinand.



Released on 2014-03-24, World Tuberculosis Day.


  • QuickCheck upper bound: 2.7 to 2.8 (7494dbc)


Released on 2014-03-17, St. Patrick’s Day.



  • base lower bound: 2 to 4 (77f6898)


  • DList constructor and record label, maybeReturn (62c0c09)


Released on 2013-12-01, World AIDS Day.



Released on 2013-11-29, Black Friday.




  • Test suite simplified and changed to use cabal test (9f58759)


  • Exported DList constructor and record label, maybeReturn (#4)