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