Safe Haskell | Safe-Inferred |
---|---|
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)\).
Another way to think about this data-structure is as of a strict list with fast append and snoc.
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
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 # | |
Applicative Acc Source # | |
Functor Acc Source # | |
NFData1 Acc Source # | |
Monoid (Acc a) Source # | |
Semigroup (Acc a) Source # | |
IsList (Acc a) Source # | |
Show a => Show (Acc a) Source # | |
NFData a => NFData (Acc a) Source # | |
type Item (Acc a) Source # | |
fromReverseList :: [a] -> Acc a Source #
uncons :: Acc a -> Maybe (a, Acc a) Source #
Extract the first element.
The produced accumulator will lack the extracted element
and will have the underlying tree rebalanced towards the beginning.
This means that calling uncons
on it will be \(\mathcal{O}(1)\).