Safe Haskell | None |
---|---|
Language | Haskell2010 |
Documentation
Data structure intended for accumulating a sequence of elements for later traversal or folding. Useful for implementing all kinds of builders on top.
Appending and prepending is always \(\mathcal{O}(1)\).
To produce a single element Acc
use pure
.
To produce a multielement Acc
use fromList
.
To combine use <|>
or <>
and other Alternative
and Monoid
-related utils.
To extract elements use Foldable
API.
The benchmarks show that for the described use-case this data-structure
is on average 2 times faster than DList
and Seq
,
is on par with list when you always prepend elements and
is exponentially faster than list when you append.
Internally it is implemented as a simple binary tree with all functions optimized to use tail recursion, ensuring that you don't get stack overflow.
Instances
Functor Acc Source # | |
Applicative Acc Source # | |
Foldable Acc Source # | |
Defined in Acc fold :: Monoid m => Acc m -> m # foldMap :: Monoid m => (a -> m) -> Acc a -> m # foldMap' :: Monoid m => (a -> m) -> Acc a -> m # foldr :: (a -> b -> b) -> b -> Acc a -> b # foldr' :: (a -> b -> b) -> b -> Acc a -> b # foldl :: (b -> a -> b) -> b -> Acc a -> b # foldl' :: (b -> a -> b) -> b -> Acc a -> b # foldr1 :: (a -> a -> a) -> Acc a -> a # foldl1 :: (a -> a -> a) -> Acc a -> a # elem :: Eq a => a -> Acc a -> Bool # maximum :: Ord a => Acc a -> a # | |
Traversable Acc Source # | |
Alternative Acc Source # | |
NFData1 Acc Source # | |
IsList (Acc a) Source # | |
Show a => Show (Acc a) Source # | |
Semigroup (Acc a) Source # | |
Monoid (Acc a) Source # | |
NFData a => NFData (Acc a) Source # | |
type Item (Acc a) Source # | |