Data.Stack.Circular

Creation date: Thu Jun 18 10:00:28 2020.

Construction of mutable circular stacks is done with replicate and subsequent pushes, or with fromVector. Use the data constructors for MStack and Stack only if you know what you are doing.

When denoting the asymptotic runtime of functions, n refers to the circular stack size.

Circular stacks

data MStack v s a

Mutable circular stacks with fixed size are just mutable vectors with a pointer to the last element.

Constructors

MStack

Fields

• mStack :: Mutable v s a
• mIndex :: !Int

data Stack v a

Immutable circular stack; useful, for example, to save, or restore a mutable circular stack.

Constructors

Stack

Fields

• iStack :: v a
• iIndex :: !Int

Instances

Eq (v a) => Eq (Stack v a)

Defined in Data.Stack.Circular

Methods

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

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

Read (v a) => Read (Stack v a)

Defined in Data.Stack.Circular

Methods

readsPrec :: Int -> ReadS (Stack v a)

readList :: ReadS [Stack v a]

readPrec :: ReadPrec (Stack v a)

readListPrec :: ReadPrec [Stack v a]

Show (v a) => Show (Stack v a)

Defined in Data.Stack.Circular

Methods

showsPrec :: Int -> Stack v a -> ShowS

show :: Stack v a -> String

showList :: [Stack v a] -> ShowS

ToJSON (v a) => ToJSON (Stack v a)

Defined in Data.Stack.Circular

Methods

toJSON :: Stack v a -> Value

toEncoding :: Stack v a -> Encoding

toJSONList :: [Stack v a] -> Value

toEncodingList :: [Stack v a] -> Encoding

FromJSON (v a) => FromJSON (Stack v a)

Defined in Data.Stack.Circular

Methods

parseJSON :: Value -> Parser (Stack v a)

parseJSONList :: Value -> Parser [Stack v a]

Construction

replicate :: (Vector v a, PrimMonad m) => Int -> a -> m (MStack v (PrimState m) a)

A circular stack of given size with the same element replicated.

Call error if the maximum size is zero or negative.

O(n).

Conversion

fromVector :: (Vector v a, PrimMonad m) => v a -> m (MStack v (PrimState m) a)

Convert a vector to a circular stack with size being equal to the length of the vector. The first element of the vector is the deepest (oldest) element of the stack, the last element of the vector is the current (newest) element of the stack.

The vector must be non-empty.

O(n).

toVector :: Vector v a => Stack v a -> v a

Convert a circular stack to a vector. The first element of the returned vector is the deepest (oldest) element of the stack, the last element of the returned vector is the current (newest) element of the stack.

O(n).

take :: (Vector v a, PrimMonad m) => Int -> MStack v (PrimState m) a -> m (v a)

Convert the last k elements of a circular stack to a vector. The first element of the returned vector is the deepest (oldest) element of the stack, the last element of the returned vector is the current (newest) element of the stack.

The size of the stack must be larger than k.

O(k).

thaw :: (Vector v a, PrimMonad m) => Stack v a -> m (MStack v (PrimState m) a)

Conversion from immutable to mutable circular stack.

O(n).

freeze :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (Stack v a)

Conversion from mutable to immutable circular stack.

O(n).

Accessors

get :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a

Get the last element without changing the stack.

O(1).

pop :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (a, MStack v (PrimState m) a)

Pop the current element from the stack and put the focus on the previous element.

Be careful: pop always succeeds, even if there are actually no more elements on the stack (similar to walking in a circle).

O(1).

push :: (Vector v a, PrimMonad m) => a -> MStack v (PrimState m) a -> m (MStack v (PrimState m) a)

Push an element on the stack.

O(1).

Folds

Commutativity of the combining function is assumed for fold-like functions provided in this module, that is, the order of elements of the stack must not matter!

foldl :: (Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a

Left fold.

O(n).

sum :: (Num a, Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a

Compute the sum of the elements on the stack.

O(n).

product :: (Num a, Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a

Compute the product of the elements on the stack.

O(n).