Safe Haskell	Safe-Inferred
Language	Haskell2010

Queue.Ephemeral

Contents

Ephemeral queue
- Initialization
Basic interface
- Extended interface
Queries
Transformations
Conversions

Description

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.

Synopsis

data EphemeralQueue a where
- pattern Empty :: EphemeralQueue a
- pattern Full :: a -> EphemeralQueue a -> EphemeralQueue a
empty :: EphemeralQueue a
singleton :: a -> EphemeralQueue a
fromList :: [a] -> EphemeralQueue a
enqueue :: a -> EphemeralQueue a -> EphemeralQueue a
dequeue :: EphemeralQueue a -> Maybe (a, EphemeralQueue a)
enqueueFront :: a -> EphemeralQueue a -> EphemeralQueue a
isEmpty :: EphemeralQueue a -> Bool
map :: (a -> b) -> EphemeralQueue a -> EphemeralQueue b
traverse :: Applicative f => (a -> f b) -> EphemeralQueue a -> f (EphemeralQueue b)
toList :: EphemeralQueue a -> [a]

Ephemeral queue

data EphemeralQueue a where Source #

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

Instances details

Foldable EphemeralQueue Source #
Instance details 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 Source #
Instance details 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 Source #
Instance details Defined in Queue.Ephemeral Methods fmap :: (a -> b) -> EphemeralQueue a -> EphemeralQueue b # (<$) :: a -> EphemeralQueue b -> EphemeralQueue a #
Monoid (EphemeralQueue a) Source #
Instance details Defined in Queue.Ephemeral Methods mempty :: EphemeralQueue a # mappend :: EphemeralQueue a -> EphemeralQueue a -> EphemeralQueue a # mconcat :: [EphemeralQueue a] -> EphemeralQueue a #
Semigroup (EphemeralQueue a) Source #	$\mathcal{O}(n)$, where $n$ is the size of the second argument.
Instance details 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) Source #
Instance details Defined in Queue.Ephemeral Methods showsPrec :: Int -> EphemeralQueue a -> ShowS # show :: EphemeralQueue a -> String # showList :: [EphemeralQueue a] -> ShowS #
Eq a => Eq (EphemeralQueue a) Source #
Instance details Defined in Queue.Ephemeral Methods (==) :: EphemeralQueue a -> EphemeralQueue a -> Bool # (/=) :: EphemeralQueue a -> EphemeralQueue a -> Bool #

Initialization

empty :: EphemeralQueue a Source #

An empty queue.

singleton :: a -> EphemeralQueue a Source #

A singleton queue.

fromList :: [a] -> EphemeralQueue a Source #

$\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 Source #

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

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

$\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 Source #

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

Queries

isEmpty :: EphemeralQueue a -> Bool Source #

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

Transformations

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

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

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

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

Conversions

toList :: EphemeralQueue a -> [a] Source #

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