Copyright	(c) 2006-2009 Don Stewart 2013-2019 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

Instances details

Monad DList Source #
Instance details Defined in Data.DList Methods (>>=) :: DList a -> (a -> DList b) -> DList b (>>) :: DList a -> DList b -> DList b return :: a -> DList a
Functor DList Source #
Instance details Defined in Data.DList Methods fmap :: (a -> b) -> DList a -> DList b (<$) :: a -> DList b -> DList a
MonadFail DList Source #
Instance details Defined in Data.DList Methods fail :: String -> DList a
Applicative DList Source #
Instance details Defined in Data.DList Methods pure :: a -> DList a (<>) :: DList (a -> b) -> DList a -> DList b liftA2 :: (a -> b -> c) -> DList a -> DList b -> DList c (>) :: DList a -> DList b -> DList b (<*) :: DList a -> DList b -> DList a
Foldable DList Source #
Instance details Defined in Data.DList Methods fold :: Monoid m => DList m -> m foldMap :: Monoid m => (a -> m) -> DList a -> m foldMap' :: Monoid m => (a -> m) -> DList a -> m foldr :: (a -> b -> b) -> b -> DList a -> b foldr' :: (a -> b -> b) -> b -> DList a -> b foldl :: (b -> a -> b) -> b -> DList a -> b foldl' :: (b -> a -> b) -> b -> DList a -> b foldr1 :: (a -> a -> a) -> DList a -> a foldl1 :: (a -> a -> a) -> DList a -> a toList :: DList a -> [a] null :: DList a -> Bool length :: DList a -> Int elem :: Eq a => a -> DList a -> Bool maximum :: Ord a => DList a -> a minimum :: Ord a => DList a -> a sum :: Num a => DList a -> a product :: Num a => DList a -> a
MonadPlus DList Source #
Instance details Defined in Data.DList Methods mzero :: DList a mplus :: DList a -> DList a -> DList a
Alternative DList Source #
Instance details Defined in Data.DList Methods empty :: DList a (<\|>) :: DList a -> DList a -> DList a some :: DList a -> DList [a] many :: DList a -> DList [a]
IsList (DList a) Source #
Instance details Defined in Data.DList Associated Types type Item (DList a) Methods fromList :: [Item (DList a)] -> DList a fromListN :: Int -> [Item (DList a)] -> DList a toList :: DList a -> [Item (DList a)]
Eq a => Eq (DList a) Source #
Instance details Defined in Data.DList Methods (==) :: DList a -> DList a -> Bool (/=) :: DList a -> DList a -> Bool
Ord a => Ord (DList a) Source #
Instance details Defined in Data.DList Methods compare :: DList a -> DList a -> Ordering (<) :: DList a -> DList a -> Bool (<=) :: DList a -> DList a -> Bool (>) :: DList a -> DList a -> Bool (>=) :: DList a -> DList a -> Bool max :: DList a -> DList a -> DList a min :: DList a -> DList a -> DList a
Read a => Read (DList a) Source #
Instance details Defined in Data.DList Methods readsPrec :: Int -> ReadS (DList a) readList :: ReadS [DList a] readPrec :: ReadPrec (DList a) readListPrec :: ReadPrec [DList a]
Show a => Show (DList a) Source #
Instance details Defined in Data.DList Methods showsPrec :: Int -> DList a -> ShowS show :: DList a -> String showList :: [DList a] -> ShowS
a ~ Char => IsString (DList a) Source #
Instance details Defined in Data.DList Methods fromString :: String -> DList a
Semigroup (DList a) Source #
Instance details Defined in Data.DList Methods (<>) :: DList a -> DList a -> DList a sconcat :: NonEmpty (DList a) -> DList a stimes :: Integral b => b -> DList a -> DList a
Monoid (DList a) Source #
Instance details Defined in Data.DList Methods mempty :: DList a mappend :: DList a -> DList a -> DList a mconcat :: [DList a] -> DList a
NFData a => NFData (DList a) Source #
Instance details Defined in Data.DList Methods rnf :: DList a -> ()
type Item (DList a) Source #
Instance details Defined in Data.DList type Item (DList a) = a