Safe Haskell	Safe-Inferred
Language	Haskell2010

Queue

Contents

Queue
- Initialization
Basic interface
- Extended interface
Queries
Transformations
Conversions

Description

A queue data structure with $\mathcal{O}(1)$ (worst-case) 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 Queue a where
- pattern Empty :: Queue a
- pattern Full :: a -> Queue a -> Queue a
empty :: Queue a
singleton :: a -> Queue a
fromList :: [a] -> Queue a
enqueue :: a -> Queue a -> Queue a
dequeue :: Queue a -> Maybe (a, Queue a)
enqueueFront :: a -> Queue a -> Queue a
isEmpty :: Queue a -> Bool
map :: (a -> b) -> Queue a -> Queue b
traverse :: Applicative f => (a -> f b) -> Queue a -> f (Queue b)
toList :: Queue a -> [a]

Queue

data Queue a where Source #

A queue data structure with $\mathcal{O}(1)$ (worst-case) operations.

Bundled Patterns

pattern Empty :: Queue a	An empty queue.
pattern Full :: a -> Queue a -> Queue a	The front of a queue, and the rest of it.

Instances

Instances details

Foldable Queue Source #
Instance details Defined in Queue Methods fold :: Monoid m => Queue m -> m # foldMap :: Monoid m => (a -> m) -> Queue a -> m # foldMap' :: Monoid m => (a -> m) -> Queue a -> m # foldr :: (a -> b -> b) -> b -> Queue a -> b # foldr' :: (a -> b -> b) -> b -> Queue a -> b # foldl :: (b -> a -> b) -> b -> Queue a -> b # foldl' :: (b -> a -> b) -> b -> Queue a -> b # foldr1 :: (a -> a -> a) -> Queue a -> a # foldl1 :: (a -> a -> a) -> Queue a -> a # toList :: Queue a -> [a] # null :: Queue a -> Bool # length :: Queue a -> Int # elem :: Eq a => a -> Queue a -> Bool # maximum :: Ord a => Queue a -> a # minimum :: Ord a => Queue a -> a # sum :: Num a => Queue a -> a # product :: Num a => Queue a -> a #
Traversable Queue Source #
Instance details Defined in Queue Methods traverse :: Applicative f => (a -> f b) -> Queue a -> f (Queue b) # sequenceA :: Applicative f => Queue (f a) -> f (Queue a) # mapM :: Monad m => (a -> m b) -> Queue a -> m (Queue b) # sequence :: Monad m => Queue (m a) -> m (Queue a) #
Functor Queue Source #
Instance details Defined in Queue Methods fmap :: (a -> b) -> Queue a -> Queue b # (<$) :: a -> Queue b -> Queue a #
Monoid (Queue a) Source #
Instance details Defined in Queue Methods mempty :: Queue a # mappend :: Queue a -> Queue a -> Queue a # mconcat :: [Queue a] -> Queue a #
Semigroup (Queue a) Source #	$\mathcal{O}(n)$, where $n$ is the size of the second argument.
Instance details Defined in Queue Methods (<>) :: Queue a -> Queue a -> Queue a # sconcat :: NonEmpty (Queue a) -> Queue a # stimes :: Integral b => b -> Queue a -> Queue a #
Show a => Show (Queue a) Source #
Instance details Defined in Queue Methods showsPrec :: Int -> Queue a -> ShowS # show :: Queue a -> String # showList :: [Queue a] -> ShowS #
Eq a => Eq (Queue a) Source #
Instance details Defined in Queue Methods (==) :: Queue a -> Queue a -> Bool # (/=) :: Queue a -> Queue a -> Bool #

Initialization

empty :: Queue a Source #

An empty queue.

singleton :: a -> Queue a Source #

A singleton queue.

fromList :: [a] -> Queue 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 -> Queue a -> Queue a Source #

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

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

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

Extended interface

enqueueFront :: a -> Queue a -> Queue a Source #

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

Queries

isEmpty :: Queue a -> Bool Source #

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

Transformations

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

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

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

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

Conversions

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

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