Copyright	(c) Atze van der Ploeg 2014 (c) David Feuer 2021
License	BSD-style
Maintainer	atzeus@gmail.org
Stability	provisional
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Sequence.FastQueue.Internal

Description

A queue (actually an output-restricted deque), with worst case constant time: |>, <|, and viewl. It has worst case linear time viewr. >< is linear in the length of its second argument.

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

Synopsis

data FastQueue a = RQ ![a] !(SL a) ![Any]
data SL a
- = SNil
- | (SL a) :> a
appendSL :: [a] -> SL a -> [a]
queue :: [a] -> SL a -> [Any] -> FastQueue a

Documentation

data FastQueue a Source #

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

Constructors

RQ ![a] !(SL a) ![Any]

Instances

Instances details

Functor FastQueue Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods fmap :: (a -> b) -> FastQueue a -> FastQueue b # (<$) :: a -> FastQueue b -> FastQueue a #
Foldable FastQueue Source #
Instance details 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 Source #
Instance details 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 Source #
Instance details 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 Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods empty :: FastQueue c Source # singleton :: c -> FastQueue c Source # (><) :: FastQueue c -> FastQueue c -> FastQueue c Source # viewl :: FastQueue c -> ViewL FastQueue c Source # viewr :: FastQueue c -> ViewR FastQueue c Source # (\|>) :: FastQueue c -> c -> FastQueue c Source # (<\|) :: c -> FastQueue c -> FastQueue c Source # fromList :: [c] -> FastQueue c Source #
Eq a => Eq (FastQueue a) Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods (==) :: FastQueue a -> FastQueue a -> Bool # (/=) :: FastQueue a -> FastQueue a -> Bool #
Ord a => Ord (FastQueue a) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods showsPrec :: Int -> FastQueue a -> ShowS # show :: FastQueue a -> String # showList :: [FastQueue a] -> ShowS #
Semigroup (FastQueue a) Source #
Instance details 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) Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods mempty :: FastQueue a # mappend :: FastQueue a -> FastQueue a -> FastQueue a # mconcat :: [FastQueue a] -> FastQueue a #

data SL a Source #

A lazy-spined snoc-list. Why lazy-spined? Only because that's better for fmap. In theory, strict-spined should be a bit better for everything else, but in practice it makes no measurable difference.

Constructors

SNil
(SL a) :> a infixl 5

Instances

Instances details

Functor SL Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods fmap :: (a -> b) -> SL a -> SL b # (<$) :: a -> SL b -> SL a #

appendSL :: [a] -> SL a -> [a] Source #

Append a snoc list to a list.

queue :: [a] -> SL a -> [Any] -> FastQueue a Source #