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.

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

Defined in Acc

Methods

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

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]

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

Functor Acc

Defined in Acc

Methods

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

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

NFData1 Acc

Defined in Acc

Methods

liftRnf :: (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

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

IsList (Acc a)

Defined in Acc

Associated Types

type Item (Acc a)

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

NFData a => NFData (Acc a)

Defined in Acc

Methods

rnf :: Acc a -> ()

type Item (Acc a)

Defined in Acc

type Item (Acc a) = a

fromReverseList :: [a] -> Acc a

Construct from list in reverse order.

This is more efficient than fromList, which is actually defined as fromReverseList . reverse.

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)\).

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.

toNeAcc :: Acc a -> Maybe (NeAcc a)

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

enumFromTo :: (Enum a, Ord a) => a -> a -> Acc a

Enumerate in range, inclusively.