|
| Data.DList | | Portability | portable (Haskell 98) | | Stability | experimental | | Maintainer | dons@cse.unsw.edu.au |
|
|
|
|
|
| Description |
| Difference lists: a data structure for O(1) append on lists.
|
|
| Synopsis |
|
|
|
| Documentation |
|
|
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
| | Constructors | | Instances | |
|
|
| Construction
|
|
|
| Converting a normal list to a dlist
|
|
|
| Converting a dlist back to a normal list
|
|
| Basic functions
|
|
|
| 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.
|
|
| MonadPlus
|
|
|
|
| Produced by Haddock version 2.4.2 |