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

cons :: a -> Acc a -> Acc a

Prepend an element.

snoc :: a -> Acc a -> Acc a

Append an element.

uncons :: Acc a -> Maybe (a, Acc a)

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)\) and unsnoc will be \(\mathcal{O}(n)\).

unsnoc :: Acc a -> Maybe (a, Acc a)

Extract the last element.

The produced accumulator will lack the extracted element and will have the underlying tree rebalanced towards the end. This means that calling unsnoc on it will be \(\mathcal{O}(1)\) and uncons will be \(\mathcal{O}(n)\).

toNonEmpty :: Acc a -> Maybe (NonEmpty a)

Convert to non empty list if it's not empty.