Queue.Ephemeral

A queue data structure with \(\mathcal{O}(1)^*\) (amortized under ephemeral usage only) operations, as described in

• Okasaki, Chris. "Simple and efficient purely functional queues and deques." Journal of functional programming 5.4 (1995): 583-592.
• Okasaki, Chris. Purely Functional Data Structures. Diss. Princeton University, 1996.

Ephemeral queue

data EphemeralQueue a where

A queue data structure with \(\mathcal{O}(1)^*\) (amortized under ephemeral usage only) operations.

Bundled Patterns

pattern Empty :: EphemeralQueue a

An empty queue.

pattern Full :: a -> EphemeralQueue a -> EphemeralQueue a

The front of a queue, and the rest of it.

Instances

Foldable EphemeralQueue

Defined in Queue.Ephemeral

Methods

fold :: Monoid m => EphemeralQueue m -> m

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

foldMap' :: Monoid m => (a -> m) -> EphemeralQueue a -> m

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

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

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

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

foldr1 :: (a -> a -> a) -> EphemeralQueue a -> a

foldl1 :: (a -> a -> a) -> EphemeralQueue a -> a

toList :: EphemeralQueue a -> [a]

null :: EphemeralQueue a -> Bool

length :: EphemeralQueue a -> Int

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

maximum :: Ord a => EphemeralQueue a -> a

minimum :: Ord a => EphemeralQueue a -> a

sum :: Num a => EphemeralQueue a -> a

product :: Num a => EphemeralQueue a -> a

Traversable EphemeralQueue

Defined in Queue.Ephemeral

Methods

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

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

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

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

Functor EphemeralQueue

Defined in Queue.Ephemeral

Methods

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

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

Monoid (EphemeralQueue a)

Defined in Queue.Ephemeral

Methods

mempty :: EphemeralQueue a

mappend :: EphemeralQueue a -> EphemeralQueue a -> EphemeralQueue a

mconcat :: [EphemeralQueue a] -> EphemeralQueue a

Semigroup (EphemeralQueue a)

\(\mathcal{O}(n)\), where \(n\) is the size of the second argument.

Defined in Queue.Ephemeral

Methods

(<>) :: EphemeralQueue a -> EphemeralQueue a -> EphemeralQueue a

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

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

Show a => Show (EphemeralQueue a)

Defined in Queue.Ephemeral

Methods

showsPrec :: Int -> EphemeralQueue a -> ShowS

show :: EphemeralQueue a -> String

showList :: [EphemeralQueue a] -> ShowS

Eq a => Eq (EphemeralQueue a)

Defined in Queue.Ephemeral

Methods

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

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

Initialization

empty :: EphemeralQueue a

An empty queue.

singleton :: a -> EphemeralQueue a

A singleton queue.

fromList :: [a] -> EphemeralQueue a

\(\mathcal{O}(1)\). Construct a queue from a list. The head of the list corresponds to the front of the queue.

Basic interface

enqueue :: a -> EphemeralQueue a -> EphemeralQueue a

\(\mathcal{O}(1)\). Enqueue an element at the back of a queue, to be dequeued last.

dequeue :: EphemeralQueue a -> Maybe (a, EphemeralQueue a)

\(\mathcal{O}(1)^*\) front, \(\mathcal{O}(1)^*\) rest. Dequeue an element from the front of a queue.

Extended interface

enqueueFront :: a -> EphemeralQueue a -> EphemeralQueue a

\(\mathcal{O}(1)\). Enqueue an element at the front of a queue, to be dequeued next.

Queries

isEmpty :: EphemeralQueue a -> Bool

\(\mathcal{O}(1)\). Is a queue empty?

Transformations

map :: (a -> b) -> EphemeralQueue a -> EphemeralQueue b

\(\mathcal{O}(n)\). Apply a function to every element in a queue.

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

\(\mathcal{O}(n)\). Apply a function to every element in a queue.

Conversions

toList :: EphemeralQueue a -> [a]

\(\mathcal{O}(n)\). Construct a list from a queue. The head of the list corresponds to the front of the queue.