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

A stack.

Bundled Patterns

pattern Empty :: Stack a

A bidirectional pattern synonym for the empty stack.

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

A bidirectional pattern synonym for working with the front of a stack.

Instances

Functor Stack

Defined in Data.CompactSequence.Stack.Simple.Internal

Methods

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

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

Foldable Stack

Defined in Data.CompactSequence.Stack.Simple.Internal

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.Internal

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.Internal

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.Internal

Methods

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

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

Ord a => Ord (Stack a)

Defined in Data.CompactSequence.Stack.Simple.Internal

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.Internal

Methods

showsPrec :: Int -> Stack a -> ShowS

show :: Stack a -> String

showList :: [Stack a] -> ShowS

Semigroup (Stack a)

Defined in Data.CompactSequence.Stack.Simple.Internal

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.Internal

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.Internal

type Item (Stack a) = a

empty :: Stack a

The empty stack.

cons :: a -> Stack a -> Stack a infixr 5

Push an element onto the front of a stack.

\( O(\log n) \)

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

An infix synonym for cons.

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

Pop an element off the front of a stack.

Accessing the first element is \( O(1) \). Accessing the rest is \( O(\log n) \).

compareLength :: Int -> Stack a -> Ordering

\( O(\min(m, n)) \). Compare an Int to the length of a Stack.

compareLength n xs = compare n (length xs)

take :: Int -> Stack a -> Stack a

Take up to the given number of elements from the front of a stack to form a new stack. \( O(\min (k, n)) \), where \( k \) is the integer argument and \( n \) is the size of the stack.

fromList :: [a] -> Stack a

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

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.