dlist-0.4.1: Differences lists

Portability portable (Haskell 98) experimental dons@cse.unsw.edu.au

Data.DList

Contents

Description

Difference lists: a data structure for O(1) append on lists.

Synopsis

Documentation

newtype DList a Source

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

 DL FieldsunDL :: [a] -> [a]

Instances

 Monad DList Functor DList MonadPlus DList Applicative DList Monoid (DList a)

Construction

fromList :: [a] -> DList aSource

Converting a normal list to a dlist

toList :: DList a -> [a]Source

Converting a dlist back to a normal list

Basic functions

Create a difference list containing no elements

singleton :: a -> DList aSource

Create difference list with given single element

cons :: a -> DList a -> DList aSource

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

snoc :: DList a -> a -> DList aSource

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

append :: DList a -> DList a -> DList aSource

O(1), Appending difference lists

concat :: [DList a] -> DList aSource

O(spine), Concatenate difference lists

list :: b -> (a -> DList a -> b) -> DList a -> bSource

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

head :: DList a -> aSource

Return the head of the list

tail :: DList a -> DList aSource

Return the tail of the list

unfoldr :: (b -> Maybe (a, b)) -> b -> DList aSource

Unfoldr for difference lists

foldr :: (a -> b -> b) -> b -> DList a -> bSource

Foldr over difference lists

map :: (a -> b) -> DList a -> DList bSource

Map over difference lists.