Data.Sequence.FastQueue

A queue (actually an output-restricted deque), with worst case constant time: |>, <|, and viewl. It has worst case linear time viewr and ><.

Based on: "Simple and Efficient Purely Functional Queues and Deques", Chris Okasaki, Journal of Functional Programming 1995

Documentation

module Data.SequenceClass

data FastQueue a

A scheduled Banker's FastQueue, as described by Okasaki.

Instances

Functor FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

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

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

Foldable FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

fold :: Monoid m => FastQueue m -> m

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

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

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

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

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

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

foldr1 :: (a -> a -> a) -> FastQueue a -> a

foldl1 :: (a -> a -> a) -> FastQueue a -> a

toList :: FastQueue a -> [a]

null :: FastQueue a -> Bool

length :: FastQueue a -> Int

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

maximum :: Ord a => FastQueue a -> a

minimum :: Ord a => FastQueue a -> a

sum :: Num a => FastQueue a -> a

product :: Num a => FastQueue a -> a

Traversable FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

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

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

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

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

Show1 FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> FastQueue a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [FastQueue a] -> ShowS

Sequence FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

empty :: FastQueue c

singleton :: c -> FastQueue c

(><) :: FastQueue c -> FastQueue c -> FastQueue c

viewl :: FastQueue c -> ViewL FastQueue c

viewr :: FastQueue c -> ViewR FastQueue c

(|>) :: FastQueue c -> c -> FastQueue c

(<|) :: c -> FastQueue c -> FastQueue c

fromList :: [c] -> FastQueue c

Eq a => Eq (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

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

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

Ord a => Ord (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

compare :: FastQueue a -> FastQueue a -> Ordering

(<) :: FastQueue a -> FastQueue a -> Bool

(<=) :: FastQueue a -> FastQueue a -> Bool

(>) :: FastQueue a -> FastQueue a -> Bool

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

max :: FastQueue a -> FastQueue a -> FastQueue a

min :: FastQueue a -> FastQueue a -> FastQueue a

Read a => Read (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

readsPrec :: Int -> ReadS (FastQueue a)

readList :: ReadS [FastQueue a]

readPrec :: ReadPrec (FastQueue a)

readListPrec :: ReadPrec [FastQueue a]

Show a => Show (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

showsPrec :: Int -> FastQueue a -> ShowS

show :: FastQueue a -> String

showList :: [FastQueue a] -> ShowS

Semigroup (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

(<>) :: FastQueue a -> FastQueue a -> FastQueue a

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

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

Monoid (FastQueue a)

Defined in Data.Sequence.FastQueue.Internal

Methods

mempty :: FastQueue a

mappend :: FastQueue a -> FastQueue a -> FastQueue a

mconcat :: [FastQueue a] -> FastQueue a