Data.CompactSequence.Stack.Simple

Space-efficient stacks with amortized \( O(\log n) \) operations. These directly use an underlying array-based implementation, without doing any special optimization for the very top of the stack.

Documentation

data Stack a where

Bundled Patterns

pattern Empty :: Stack a

pattern (:<) :: a -> Stack a -> Stack a infixr 4

Instances

Functor Stack

Defined in Data.CompactSequence.Stack.Simple

Methods

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

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

Foldable Stack

Defined in Data.CompactSequence.Stack.Simple

Methods

fold :: Monoid m => Stack m -> m

foldMap :: Monoid m => (a -> m) -> Stack a -> m

foldr :: (a -> b -> b) -> b -> Stack a -> b

foldr' :: (a -> b -> b) -> b -> Stack a -> b

foldl :: (b -> a -> b) -> b -> Stack a -> b

foldl' :: (b -> a -> b) -> b -> Stack a -> b

foldr1 :: (a -> a -> a) -> Stack a -> a

foldl1 :: (a -> a -> a) -> Stack a -> a

toList :: Stack a -> [a]

null :: Stack a -> Bool

length :: Stack a -> Int

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

maximum :: Ord a => Stack a -> a

minimum :: Ord a => Stack a -> a

sum :: Num a => Stack a -> a

product :: Num a => Stack a -> a

Traversable Stack

Defined in Data.CompactSequence.Stack.Simple

Methods

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

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

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

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

IsList (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Associated Types

type Item (Stack a) :: Type

Methods

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

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

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

Eq a => Eq (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Methods

(==) :: Stack a -> Stack a -> Bool

(/=) :: Stack a -> Stack a -> Bool

Ord a => Ord (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Methods

compare :: Stack a -> Stack a -> Ordering

(<) :: Stack a -> Stack a -> Bool

(<=) :: Stack a -> Stack a -> Bool

(>) :: Stack a -> Stack a -> Bool

(>=) :: Stack a -> Stack a -> Bool

max :: Stack a -> Stack a -> Stack a

min :: Stack a -> Stack a -> Stack a

Show a => Show (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Methods

showsPrec :: Int -> Stack a -> ShowS

show :: Stack a -> String

showList :: [Stack a] -> ShowS

Semigroup (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Methods

(<>) :: Stack a -> Stack a -> Stack a

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

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

Monoid (Stack a)

Defined in Data.CompactSequence.Stack.Simple

Methods

mempty :: Stack a

mappend :: Stack a -> Stack a -> Stack a

mconcat :: [Stack a] -> Stack a

type Item (Stack a)

Defined in Data.CompactSequence.Stack.Simple

type Item (Stack a) = a

empty :: Stack a

cons :: a -> Stack a -> Stack a infixr 4

(<|) :: a -> Stack a -> Stack a infixr 4

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

fromListN :: Int -> [a] -> Stack a

\( O(n) \). Convert a list of known length to a stack, with the first element of the list as the top of the stack.