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

Module documentation for 1.0

Difference Lists

test-badge hackage-badge packdeps-badge

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

Blogs and Mailing Lists

Books

License

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

Changes

Change Log

Unreleased

No unreleased changes at this time.

v1.0

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

Added

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

Changed

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

Removed

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

v0.8.0.8

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

Added

Changed

  • QuickCheck upper bound: 2.14 to 2.15 (a7ea60d)

Fixed

v0.8.0.7

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

Added

Changed

v0.8.0.6

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

Changed

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

v0.8.0.5

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

Changed

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

v0.8.0.4

Released on 2018-01-19, Kokborok Day.

Added

Changed

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

v0.8.0.3

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

Added

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

Changed

  • QuickCheck upper bound: 2.10 to 2.11 (b2f791a)

Fixed

v0.8.0.2

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

Fixed

v0.8.0.1

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

Changed

v0.8

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

Added

Changed

v0.7.1.2

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

Fixed

v0.7.1.1

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

Changed

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

v0.7.1

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

Added

v0.7.0.1

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

Changed

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

v0.7

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

Added

Changed

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

Removed

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

v0.6.0.1

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

Changed

v0.6

Released on 2013-11-29, Black Friday.

Added

Changed

Fixed

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

Deprecated

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