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

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

For 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

Converting a normal list to a dlist

Converting a dlist back to a normal list

Create a difference list containing no elements

Create difference list with given single element

O(1), Prepend a single element to a difference list

O(1), Append a single element at a difference list

O(1), Appending difference lists

O(spine), Concatenate difference lists

O(n), Create a difference list of the given number of elements

O(length dl), List elimination, head, tail.

Return the head of the list

Return the tail of the list

Unfoldr for difference lists

Foldr over difference lists

Map over difference lists.