Acc

Documentation

data Acc a

Data structure intended for accumulating a sequence of elements for later traversal or folding. Useful for implementing all kinds of builders on top.

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

Defined in Acc

Methods

fmap :: (a -> b) -> Acc a -> Acc b

(<$) :: a -> Acc b -> Acc a

Applicative Acc

Defined in Acc

Methods

pure :: a -> Acc a

(<*>) :: Acc (a -> b) -> Acc a -> Acc b

liftA2 :: (a -> b -> c) -> Acc a -> Acc b -> Acc c

(*>) :: Acc a -> Acc b -> Acc b

(<*) :: Acc a -> Acc b -> Acc a

Foldable Acc

Defined in Acc

Methods

fold :: Monoid m => Acc m -> 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

toList :: Acc a -> [a]

null :: Acc a -> Bool

length :: Acc a -> Int

elem :: Eq a => a -> Acc a -> Bool

maximum :: Ord a => Acc a -> a

minimum :: Ord a => Acc a -> a

sum :: Num a => Acc a -> a

product :: Num a => Acc a -> a

Traversable Acc

Defined in Acc

Methods

traverse :: Applicative f => (a -> f b) -> Acc a -> f (Acc b)

sequenceA :: Applicative f => Acc (f a) -> f (Acc a)

mapM :: Monad m => (a -> m b) -> Acc a -> m (Acc b)

sequence :: Monad m => Acc (m a) -> m (Acc a)

Alternative Acc

Defined in Acc

Methods

empty :: Acc a

(<|>) :: Acc a -> Acc a -> Acc a

some :: Acc a -> Acc [a]

many :: Acc a -> Acc [a]

NFData1 Acc

Defined in Acc

Methods

liftRnf :: (a -> ()) -> Acc a -> ()

IsList (Acc a)

Defined in Acc

Associated Types

type Item (Acc a) :: Type

Methods

fromList :: [Item (Acc a)] -> Acc a

fromListN :: Int -> [Item (Acc a)] -> Acc a

toList :: Acc a -> [Item (Acc a)]

Show a => Show (Acc a)

Defined in Acc

Methods

showsPrec :: Int -> Acc a -> ShowS

show :: Acc a -> String

showList :: [Acc a] -> ShowS

Generic (Acc a)

Defined in Acc

Associated Types

type Rep (Acc a) :: Type -> Type

Methods

from :: Acc a -> Rep (Acc a) x

to :: Rep (Acc a) x -> Acc a

Semigroup (Acc a)

Defined in Acc

Methods

(<>) :: Acc a -> Acc a -> Acc a

sconcat :: NonEmpty (Acc a) -> Acc a

stimes :: Integral b => b -> Acc a -> Acc a

Monoid (Acc a)

Defined in Acc

Methods

mempty :: Acc a

mappend :: Acc a -> Acc a -> Acc a

mconcat :: [Acc a] -> Acc a

NFData a => NFData (Acc a)

Defined in Acc

Methods

rnf :: Acc a -> ()

Generic1 Acc

Defined in Acc

Associated Types

type Rep1 Acc :: k -> Type

Methods

from1 :: Acc a -> Rep1 Acc a

to1 :: Rep1 Acc a -> Acc a

type Rep (Acc a)

Defined in Acc

type Rep (Acc a)

type Item (Acc a)

Defined in Acc

type Item (Acc a) = a

type Rep1 Acc

Defined in Acc

type Rep1 Acc