dlist-0.8.0.6: Difference lists

Copyright | (c) 2006-2009 Don Stewart 2013-2016 Sean Leather
License | See LICENSE file
Maintainer | sean.leather@gmail.com
Stability | stable
Portability | portable
Safe Haskell | Trustworthy
Language | Haskell98

Data.DList

Contents

- Construction
- Basic functions

Description

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

Synopsis

- data DList a where
  - pattern Nil :: DList a
  - pattern Cons :: a -> [a] -> DList a
- fromList :: [a] -> DList a
- toList :: DList a -> [a]
- apply :: DList a -> [a] -> [a]
- empty :: DList a
- singleton :: a -> DList a
- cons :: a -> DList a -> DList a
- snoc :: DList a -> a -> DList a
- append :: DList a -> DList a -> DList a
- concat :: [DList a] -> DList a
- replicate :: Int -> a -> DList a
- list :: b -> (a -> DList a -> b) -> DList a -> b
- head :: DList a -> a
- tail :: DList a -> DList a
- unfoldr :: (b -> Maybe (a, b)) -> b -> DList a
- foldr :: (a -> b -> b) -> b -> DList a -> b
- map :: (a -> b) -> DList a -> DList b

# Documentation

data DList a where 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 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

Bundled Patterns

pattern Nil :: DList a | A unidirectional pattern synonym using `toList` in a view pattern and matching on `[]`
pattern Cons :: a -> [a] -> DList a | A unidirectional pattern synonym using `toList` in a view pattern and matching on `x:xs` such that you have the pattern `Cons x xs`

Instances

Monad DList Source # |
Instance details Defined in Data.DList Methods (>>=) :: DList a -> (a -> DList b) -> DList b Source # (>>) :: DList a -> DList b -> DList b Source # return :: a -> DList a Source # fail :: String -> DList a Source #
Functor DList Source # |
Instance details Defined in Data.DList Methods fmap :: (a -> b) -> DList a -> DList b Source # (<$) :: a -> DList b -> DList a Source #
Applicative DList Source # |
Instance details Defined in Data.DList Methods pure :: a -> DList a Source # (<*>) :: DList (a -> b) -> DList a -> DList b Source # liftA2 :: (a -> b -> c) -> DList a -> DList b -> DList c Source # (*>) :: DList a -> DList b -> DList b Source # (<*) :: DList a -> DList b -> DList a Source #
Foldable DList Source # |

Instance details

Defined in Data.DList

Methods

fold :: Monoid m => DList m -> m Source #

foldMap :: Monoid m => (a -> m) -> DList a -> m Source #

foldr :: (a -> b -> b) -> b -> DList a -> b Source #

foldr' :: (a -> b -> b) -> b -> DList a -> b Source #

foldl :: (b -> a -> b) -> b -> DList a -> b Source #

foldl' :: (b -> a -> b) -> b -> DList a -> b Source #

foldr1 :: (a -> a -> a) -> DList a -> a Source #

foldl1 :: (a -> a -> a) -> DList a -> a Source #

toList :: DList a -> [a] Source #

null :: DList a -> Bool Source #

length :: DList a -> Int Source #

elem :: Eq a => a -> DList a -> Bool Source #

maximum :: Ord a => DList a -> a Source #

minimum :: Ord a => DList a -> a Source #

sum :: Num a => DList a -> a Source #

product :: Num a => DList a -> a Source #

Alternative DList Source # |
Instance details Defined in Data.DList Methods empty :: DList a Source # (<|>) :: DList a -> DList a -> DList a Source # some :: DList a -> DList [a] Source # many :: DList a -> DList [a] Source #
MonadPlus DList Source # |
Instance details Defined in Data.DList Methods mzero :: DList a Source # mplus :: DList a -> DList a -> DList a Source #
IsList (DList a) Source # |
Instance details Defined in Data.DList Associated Types type Item (DList a) :: Type Source # Methods fromList :: [Item (DList a)] -> DList a Source # fromListN :: Int -> [Item (DList a)] -> DList a Source # toList :: DList a -> [Item (DList a)] Source #
Eq a => Eq (DList a) Source # |
Instance details Defined in Data.DList Methods (==) :: DList a -> DList a -> Bool Source # (/=) :: DList a -> DList a -> Bool Source #
Ord a => Ord (DList a) Source # |
Instance details Defined in Data.DList Methods compare :: DList a -> DList a -> Ordering Source # (<) :: DList a -> DList a -> Bool Source # (<=) :: DList a -> DList a -> Bool Source # (>) :: DList a -> DList a -> Bool Source # (>=) :: DList a -> DList a -> Bool Source # max :: DList a -> DList a -> DList a Source # min :: DList a -> DList a -> DList a Source #
Read a => Read (DList a) Source # |
Instance details Defined in Data.DList Methods readsPrec :: Int -> ReadS (DList a) Source # readList :: ReadS [DList a] Source # readPrec :: ReadPrec (DList a) Source # readListPrec :: ReadPrec [DList a] Source #
Show a => Show (DList a) Source # |
Instance details Defined in Data.DList Methods showsPrec :: Int -> DList a -> ShowS Source # show :: DList a -> String Source # showList :: [DList a] -> ShowS Source #
a ~ Char => IsString (DList a) Source # |
Instance details Defined in Data.DList Methods fromString :: String -> DList a Source #
Semigroup (DList a) Source # |
Instance details Defined in Data.DList Methods (<>) :: DList a -> DList a -> DList a Source # sconcat :: NonEmpty (DList a) -> DList a Source # stimes :: Integral b => b -> DList a -> DList a Source #
Monoid (DList a) Source # |
Instance details Defined in Data.DList Methods mempty :: DList a Source # mappend :: DList a -> DList a -> DList a Source # mconcat :: [DList a] -> DList a Source #
NFData a => NFData (DList a) Source # |
Instance details Defined in Data.DList Methods rnf :: DList a -> () Source #
type Item (DList a) Source # |
Instance details Defined in Data.DList type Item (DList a) = a

# Construction

fromList :: [a] -> DList a Source #

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

empty :: DList a Source #

Create a dlist containing no elements

singleton :: a -> DList a Source #

Create dlist with a single element

cons :: a -> DList a -> DList a infixr 9 Source #

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

snoc :: DList a -> a -> DList a infixl 9 Source #

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

append :: DList a -> DList a -> DList a Source #

O(1). Append dlists

concat :: [DList a] -> DList a Source #

O(spine). Concatenate dlists

replicate :: Int -> a -> DList a Source #

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

list :: b -> (a -> DList a -> b) -> DList a -> b Source #

O(n). List elimination for dlists

head :: DList a -> a Source #

O(n). Return the head of the dlist

tail :: DList a -> DList a Source #

O(n). Return the tail of the dlist

unfoldr :: (b -> Maybe (a, b)) -> b -> DList a Source #

O(n). Unfoldr for dlists

foldr :: (a -> b -> b) -> b -> DList a -> b Source #

O(n). Foldr over difference lists

map :: (a -> b) -> DList a -> DList b Source #

O(n). Map over difference lists.