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 |
Difference lists: a data structure for O(1) append on lists.
Synopsis
- data DList a where
- 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
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
pattern Nil :: DList a | A unidirectional pattern synonym using |
pattern Cons :: a -> [a] -> DList a | A unidirectional pattern synonym using |
Instances
Monad DList # | |
Functor DList # | |
Applicative DList # | |
Foldable DList # | |
Defined in Data.DList fold :: Monoid m => DList m -> 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 # elem :: Eq a => a -> DList a -> Bool # maximum :: Ord a => DList a -> a # minimum :: Ord a => DList a -> a # | |
Alternative DList # | |
MonadPlus DList # | |
IsList (DList a) # | |
Eq a => Eq (DList a) # | |
Ord a => Ord (DList a) # | |
Read a => Read (DList a) # | |
Show a => Show (DList a) # | |
a ~ Char => IsString (DList a) # | |
Defined in Data.DList fromString :: String -> DList a # | |
Semigroup (DList a) # | |
Monoid (DList a) # | |
NFData a => NFData (DList a) # | |
Defined in Data.DList | |
type Item (DList a) # | |
Defined in Data.DList |
Construction
apply :: DList a -> [a] -> [a] #
Apply a dlist to a list to get the underlying list with an extension
apply (fromList xs) ys = xs ++ ys