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.SimpleQueue

Contents

Description

Simple Queues. All operations have running times as listed in Data.Edison.Seq except for the following:

  • rcons, fromList O( 1 )
  • lview, ltail* O( 1 ) if single threaded, O( n ) otherwise
  • inBounds, lookup, update, drop, splitAt O( n )

References:

  • Chris Okasaki. Purely Functional Data Structures. 1998. Section 5.2.
  • F. Warren Burton. "An efficient functional implementation of FIFO queues". Information Processing Letters, 14(5):205-206, July 1982.

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 #

foldlWithIndex :: (b -> Int -> a -> 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 #

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