EdisonCore-1.3.2: A library of efficient, purely-functional data structures (Core Implementations)

CopyrightCopyright (c) 1998-1999 2008 Chris Okasaki
LicenseMIT; see COPYRIGHT file for terms and conditions
Maintainerrobdockins AT fastmail DOT fm
Stabilitystable
PortabilityGHC, Hugs (MPTC and FD)
Safe HaskellNone
LanguageHaskell2010

Data.Edison.Seq.BankersQueue

Contents

Description

This module implements Banker's Queues. It has the standard running times from Data.Edison.Seq except for the following:

  • rcons, size, inBounds O( 1 )

References:

  • Chris Okasaki, Purely Functional Data Structures, 1998, sections 6.3.2 and 8.4.1.
  • Chris Okasaki, "Simple and efficient purely functional queues and deques", Journal of Function Programming 5(4):583-592, October 1995.

Synopsis

Sequence Type

data Seq a Source #

Instances

Monad Seq Source # 

Methods

(>>=) :: Seq a -> (a -> Seq b) -> Seq b #

(>>) :: Seq a -> Seq b -> Seq b #

return :: a -> Seq a #

fail :: String -> Seq a #

Functor Seq Source # 

Methods

fmap :: (a -> b) -> Seq a -> Seq b #

(<$) :: a -> Seq b -> Seq a #

Applicative Seq Source # 

Methods

pure :: a -> Seq a #

(<*>) :: Seq (a -> b) -> Seq a -> Seq b #

liftA2 :: (a -> b -> c) -> Seq a -> Seq b -> Seq c #

(*>) :: Seq a -> Seq b -> Seq b #

(<*) :: Seq a -> Seq b -> Seq a #

Sequence Seq Source # 

Methods

lcons :: a -> Seq a -> Seq a #

rcons :: a -> Seq a -> Seq a #

fromList :: [a] -> Seq a #

copy :: Int -> a -> Seq a #

lview :: Monad m => Seq a -> m (a, Seq a) #

lhead :: Seq a -> a #

lheadM :: Monad m => Seq a -> m a #

ltail :: Seq a -> Seq a #

ltailM :: Monad m => Seq a -> m (Seq a) #

rview :: Monad m => Seq a -> m (a, Seq a) #

rhead :: Seq a -> a #

rheadM :: Monad m => Seq a -> m a #

rtail :: Seq a -> Seq a #

rtailM :: Monad m => Seq a -> m (Seq a) #

null :: Seq a -> Bool #

size :: Seq a -> Int #

toList :: Seq a -> [a] #

concat :: Seq (Seq a) -> Seq a #

reverse :: Seq a -> Seq a #

reverseOnto :: Seq a -> Seq a -> Seq a #

fold :: (a -> b -> b) -> b -> Seq a -> b #

fold' :: (a -> b -> b) -> b -> Seq a -> b #

fold1 :: (a -> a -> a) -> Seq a -> a #

fold1' :: (a -> a -> a) -> Seq a -> a #

foldr :: (a -> b -> b) -> b -> Seq a -> b #

foldr' :: (a -> b -> b) -> b -> Seq a -> b #

foldl :: (b -> a -> b) -> b -> Seq a -> b #

foldl' :: (b -> a -> b) -> b -> Seq a -> b #

foldr1 :: (a -> a -> a) -> Seq a -> a #

foldr1' :: (a -> a -> a) -> Seq a -> a #

foldl1 :: (a -> a -> a) -> Seq a -> a #

foldl1' :: (a -> a -> a) -> Seq a -> a #

reducer :: (a -> a -> a) -> a -> Seq a -> a #

reducer' :: (a -> a -> a) -> a -> Seq a -> a #

reducel :: (a -> a -> a) -> a -> Seq a -> a #

reducel' :: (a -> a -> a) -> a -> Seq a -> a #

reduce1 :: (a -> a -> a) -> Seq a -> a #

reduce1' :: (a -> a -> a) -> Seq a -> a #

take :: Int -> Seq a -> Seq a #

drop :: Int -> Seq a -> Seq a #

splitAt :: Int -> Seq a -> (Seq a, Seq a) #

subseq :: Int -> Int -> Seq a -> Seq a #

filter :: (a -> Bool) -> Seq a -> Seq a #

partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a) #

takeWhile :: (a -> Bool) -> Seq a -> Seq a #

dropWhile :: (a -> Bool) -> Seq a -> Seq a #

splitWhile :: (a -> Bool) -> Seq a -> (Seq a, Seq a) #

inBounds :: Int -> Seq a -> Bool #

lookup :: Int -> Seq a -> a #

lookupM :: Monad m => Int -> Seq a -> m a #

lookupWithDefault :: a -> Int -> Seq a -> a #

update :: Int -> a -> Seq a -> Seq a #

adjust :: (a -> a) -> Int -> Seq a -> Seq a #

mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b #

foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b #

foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> b #

foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b #

foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> b #

zip :: Seq a -> Seq b -> Seq (a, b) #

zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c) #

zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c #

zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d #

unzip :: Seq (a, b) -> (Seq a, Seq b) #

unzip3 :: Seq (a, b, c) -> (Seq a, Seq b, Seq c) #

unzipWith :: (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c) #

unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d) #

strict :: Seq a -> Seq a #

strictWith :: (a -> b) -> Seq a -> Seq a #

structuralInvariant :: Seq a -> Bool #

instanceName :: Seq a -> String #

Alternative Seq Source # 

Methods

empty :: Seq a #

(<|>) :: Seq a -> Seq a -> Seq a #

some :: Seq a -> Seq [a] #

many :: Seq a -> Seq [a] #

MonadPlus Seq Source # 

Methods

mzero :: Seq a #

mplus :: Seq a -> Seq a -> Seq a #

Eq a => Eq (Seq a) Source # 

Methods

(==) :: Seq a -> Seq a -> Bool #

(/=) :: Seq a -> Seq a -> Bool #

Ord a => Ord (Seq a) Source # 

Methods

compare :: Seq a -> Seq a -> Ordering #

(<) :: Seq a -> Seq a -> Bool #

(<=) :: Seq a -> Seq a -> Bool #

(>) :: Seq a -> Seq a -> Bool #

(>=) :: Seq a -> Seq a -> Bool #

max :: Seq a -> Seq a -> Seq a #

min :: Seq a -> Seq a -> Seq a #

Read a => Read (Seq a) Source # 
Show a => Show (Seq a) Source # 

Methods

showsPrec :: Int -> Seq a -> ShowS #

show :: Seq a -> String #

showList :: [Seq a] -> ShowS #

Semigroup (Seq a) Source # 

Methods

(<>) :: Seq a -> Seq a -> Seq a #

sconcat :: NonEmpty (Seq a) -> Seq a #

stimes :: Integral b => b -> Seq a -> Seq a #

Monoid (Seq a) Source # 

Methods

mempty :: Seq a #

mappend :: Seq a -> Seq a -> Seq a #

mconcat :: [Seq a] -> Seq a #

Arbitrary a => Arbitrary (Seq a) Source # 

Methods

arbitrary :: Gen (Seq a) #

shrink :: Seq a -> [Seq a] #

CoArbitrary a => CoArbitrary (Seq a) Source # 

Methods

coarbitrary :: Seq a -> Gen b -> Gen b #

Sequence operations

singleton :: a -> Seq a Source #

lcons :: a -> Seq a -> Seq a Source #

rcons :: a -> Seq a -> Seq a Source #

append :: Seq a -> Seq a -> Seq a Source #

lview :: Monad m => Seq a -> m (a, Seq a) Source #

lhead :: Seq a -> a Source #

ltail :: Seq a -> Seq a Source #

rview :: Monad m => Seq a -> m (a, Seq a) Source #

rhead :: Seq a -> a Source #

rtail :: Seq a -> Seq a Source #

lheadM :: Monad m => Seq a -> m a Source #

ltailM :: Monad m => Seq a -> m (Seq a) Source #

rheadM :: Monad m => Seq a -> m a Source #

rtailM :: Monad m => Seq a -> m (Seq a) Source #

null :: Seq a -> Bool Source #

size :: Seq a -> Int Source #

concat :: Seq (Seq a) -> Seq a Source #

reverse :: Seq a -> Seq a Source #

reverseOnto :: Seq a -> Seq a -> Seq a Source #

fromList :: [a] -> Seq a Source #

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

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

concatMap :: (a -> Seq b) -> Seq a -> Seq b Source #

fold :: (a -> b -> b) -> b -> Seq a -> b Source #

fold' :: (a -> b -> b) -> b -> Seq a -> b Source #

fold1 :: (a -> a -> a) -> Seq a -> a Source #

fold1' :: (a -> a -> a) -> Seq a -> a Source #

foldr :: (a -> b -> b) -> b -> Seq a -> b Source #

foldr' :: (a -> b -> b) -> b -> Seq a -> b Source #

foldl :: (b -> a -> b) -> b -> Seq a -> b Source #

foldl' :: (b -> a -> b) -> b -> Seq a -> b Source #

foldr1 :: (a -> a -> a) -> Seq a -> a Source #

foldr1' :: (a -> a -> a) -> Seq a -> a Source #

foldl1 :: (a -> a -> a) -> Seq a -> a Source #

foldl1' :: (a -> a -> a) -> Seq a -> a Source #

reducer :: (a -> a -> a) -> a -> Seq a -> a Source #

reducer' :: (a -> a -> a) -> a -> Seq a -> a Source #

reducel :: (a -> a -> a) -> a -> Seq a -> a Source #

reducel' :: (a -> a -> a) -> a -> Seq a -> a Source #

reduce1 :: (a -> a -> a) -> Seq a -> a Source #

reduce1' :: (a -> a -> a) -> Seq a -> a Source #

copy :: Int -> a -> Seq a Source #

lookup :: Int -> Seq a -> a Source #

lookupM :: Monad m => Int -> Seq a -> m a Source #

lookupWithDefault :: a -> Int -> Seq a -> a Source #

update :: Int -> a -> Seq a -> Seq a Source #

adjust :: (a -> a) -> Int -> Seq a -> Seq a Source #

mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b Source #

foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b Source #

foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> b Source #

foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b Source #

foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> b Source #

take :: Int -> Seq a -> Seq a Source #

drop :: Int -> Seq a -> Seq a Source #

splitAt :: Int -> Seq a -> (Seq a, Seq a) Source #

subseq :: Int -> Int -> Seq a -> Seq a Source #

filter :: (a -> Bool) -> Seq a -> Seq a Source #

partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source #

takeWhile :: (a -> Bool) -> Seq a -> Seq a Source #

dropWhile :: (a -> Bool) -> Seq a -> Seq a Source #

splitWhile :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source #

zip :: Seq a -> Seq b -> Seq (a, b) Source #

zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c) Source #

zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c Source #

zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d Source #

unzip :: Seq (a, b) -> (Seq a, Seq b) Source #

unzip3 :: Seq (a, b, c) -> (Seq a, Seq b, Seq c) Source #

unzipWith :: (a -> b) -> (a -> c) -> Seq a -> (Seq b, Seq c) Source #

unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> Seq a -> (Seq b, Seq c, Seq d) Source #

strict :: Seq a -> Seq a Source #

strictWith :: (a -> b) -> Seq a -> Seq a Source #

Unit testing

Documentation