dlist-0.7.1: Difference lists

Portability portable stable sean.leather@gmail.com Safe-Inferred

Data.DList

Contents

Description

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

Synopsis

Documentation

data DList a Source

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

Instances

 Monad DList Functor DList MonadPlus DList Applicative DList Foldable DList Alternative DList Eq a => Eq (DList a) Ord a => Ord (DList a) Read a => Read (DList a) Show a => Show (DList a) IsString (DList Char) Monoid (DList a) NFData a => NFData (DList a)

Construction

fromList :: [a] -> DList aSource

Convert a list to a dlist

toList :: DList a -> [a]Source

Convert a dlist to a list

apply :: DList a -> [a] -> [a]Source

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

apply (fromList xs) ys = xs ++ ys

Basic functions

Create a dlist containing no elements

singleton :: a -> DList aSource

Create dlist with a single element

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

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

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

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

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

O(1). Append dlists

concat :: [DList a] -> DList aSource

O(spine). Concatenate dlists

replicate :: Int -> a -> DList aSource

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

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

O(n). List elimination for dlists

head :: DList a -> aSource

O(n). Return the head of the dlist

tail :: DList a -> DList aSource

O(n). Return the tail of the dlist

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

O(n). Unfoldr for dlists

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

O(n). Foldr over difference lists

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

O(n). Map over difference lists.