Data.Sequence.Queue.Internal

A sequence, a queue, with amortized constant time: |>, and viewl. It also supports |> and viewr in amortized logarithmic time.

A simplified version of Okasaki's implicit recursive slowdown queues. See purely functional data structures by Chris Okasaki section 8.4: Queues based on implicit recursive slowdown

Documentation

data Queue a where

A queue.

Constructors

Q0 :: Queue a

Q1 :: a -> Queue a

QN :: !(B a) -> Queue (P a) -> !(B a) -> Queue a

Instances

Functor Queue

Defined in Data.Sequence.Queue.Internal

Methods

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

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

Foldable Queue

Defined in Data.Sequence.Queue.Internal

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 Data.Sequence.Queue.Internal

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)

Show1 Queue

Defined in Data.Sequence.Queue.Internal

Methods

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

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

Sequence Queue

Defined in Data.Sequence.Queue.Internal

Methods

empty :: Queue c

singleton :: c -> Queue c

(><) :: Queue c -> Queue c -> Queue c

viewl :: Queue c -> ViewL Queue c

viewr :: Queue c -> ViewR Queue c

(|>) :: Queue c -> c -> Queue c

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

fromList :: [c] -> Queue c

Eq a => Eq (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

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

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

Ord a => Ord (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

compare :: Queue a -> Queue a -> Ordering

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

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

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

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

max :: Queue a -> Queue a -> Queue a

min :: Queue a -> Queue a -> Queue a

Read a => Read (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

readsPrec :: Int -> ReadS (Queue a)

readList :: ReadS [Queue a]

readPrec :: ReadPrec (Queue a)

readListPrec :: ReadPrec [Queue a]

Show a => Show (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

showsPrec :: Int -> Queue a -> ShowS

show :: Queue a -> String

showList :: [Queue a] -> ShowS

Semigroup (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

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

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

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

Monoid (Queue a)

Defined in Data.Sequence.Queue.Internal

Methods

mempty :: Queue a

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

mconcat :: [Queue a] -> Queue a

data P a

Constructors

a :* a

Instances

Functor P

Defined in Data.Sequence.Queue.Internal

Methods

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

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

Foldable P

Defined in Data.Sequence.Queue.Internal

Methods

fold :: Monoid m => P m -> m

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

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

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

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

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

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

foldr1 :: (a -> a -> a) -> P a -> a

foldl1 :: (a -> a -> a) -> P a -> a

toList :: P a -> [a]

null :: P a -> Bool

length :: P a -> Int

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

maximum :: Ord a => P a -> a

minimum :: Ord a => P a -> a

sum :: Num a => P a -> a

product :: Num a => P a -> a

Traversable P

Defined in Data.Sequence.Queue.Internal

Methods

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

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

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

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

data B a where

Constructors

B1 :: a -> B a

B2 :: !(P a) -> B a

Instances

Functor B

Defined in Data.Sequence.Queue.Internal

Methods

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

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

Foldable B

Defined in Data.Sequence.Queue.Internal

Methods

fold :: Monoid m => B m -> m

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

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

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

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

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

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

foldr1 :: (a -> a -> a) -> B a -> a

foldl1 :: (a -> a -> a) -> B a -> a

toList :: B a -> [a]

null :: B a -> Bool

length :: B a -> Int

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

maximum :: Ord a => B a -> a

minimum :: Ord a => B a -> a

sum :: Num a => B a -> a

product :: Num a => B a -> a

Traversable B

Defined in Data.Sequence.Queue.Internal

Methods

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

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

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

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