A difference list is a function that, given a list, returns the original contents of the difference list prepended to the given list.

This structure supports O(1) append and snoc operations on lists, making it very useful for append-heavy uses (esp. left-nested uses of ++), such as logging and pretty printing.

Here is an example using DList as the state type when printing a tree with the Writer monad:

 import Control.Monad.Writer
 import Data.DList

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

 flatten_writer :: Tree x -> DList x
 flatten_writer = snd . runWriter . flatten
     where
       flatten (Leaf x)     = tell (singleton x)
       flatten (Branch x y) = flatten x >> flatten y

Convert a list to a dlist

Convert a dlist to a list

Apply a dlist to a list to get the underlying list with an extension

 apply (fromList xs) ys = xs ++ ys

Create a dlist containing no elements

Create dlist with a single element

O(1). Prepend a single element to a dlist

O(1). Append a single element to a dlist

O(1). Append dlists

O(spine). Concatenate dlists

O(n). Create a dlist of the given number of elements

O(n). List elimination for dlists

O(n). Return the head of the dlist

O(n). Return the tail of the dlist

O(n). Unfoldr for dlists

O(n). Foldr over difference lists

O(n). Map over difference lists.