Queue

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.

Queue

data Queue a where

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

Foldable Queue

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

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

Defined in Queue

Methods

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

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

Monoid (Queue a)

Defined in Queue

Methods

mempty :: Queue a

mappend :: Queue a -> Queue a -> Queue a

mconcat :: [Queue a] -> Queue a

Semigroup (Queue a)

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

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)

Defined in Queue

Methods

showsPrec :: Int -> Queue a -> ShowS

show :: Queue a -> String

showList :: [Queue a] -> ShowS

Eq a => Eq (Queue a)

Defined in Queue

Methods

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

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

Initialization

empty :: Queue a

An empty queue.

singleton :: a -> Queue a

A singleton queue.

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

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

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

\(\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

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

Queries

isEmpty :: Queue a -> Bool

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

Transformations

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

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

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

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

Conversions

toList :: Queue a -> [a]

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