Difference Lists

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

Installation

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.

Usage

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
  where
    go (Leaf x) = [x]
    go (Branch left right) = go left ++ go right

flattenFast :: Tree a -> [a]
flattenFast = DList.toList . go
  where
    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.

Abstraction

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.

References

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

Research

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

Background

• Wikipedia
• Haskell Wiki
• Stack Overflow

Blogs and Mailing Lists

• 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.
• Demystifying DList (Reddit). Tom Ellis. 2014-01-24.
• keepEquals with Difference Lists. Douglas M. Auclair. 2014-06-21.

Books

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

License

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