EdisonCore-1.3.2.1: 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 # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

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 # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

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

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

Applicative Seq Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

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 # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

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

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

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

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

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

lhead :: Seq a -> a Source #

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

ltail :: Seq a -> Seq a Source #

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

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

rhead :: Seq a -> a Source #

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

rtail :: Seq a -> Seq a Source #

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

null :: Seq a -> Bool Source #

size :: Seq a -> Int Source #

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

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

reverse :: Seq a -> Seq a Source #

reverseOnto :: Seq a -> Seq a -> Seq a 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 #

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 #

inBounds :: Int -> Seq a -> Bool 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 #

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 #

structuralInvariant :: Seq a -> Bool Source #

instanceName :: Seq a -> String Source #

Alternative Seq Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

empty :: Seq a

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

some :: Seq a -> Seq [a]

many :: Seq a -> Seq [a]

MonadPlus Seq Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

mzero :: Seq a

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

Eq a => Eq (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

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

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

Ord a => Ord (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

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 # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

readsPrec :: Int -> ReadS (Seq a)

readList :: ReadS [Seq a]

readPrec :: ReadPrec (Seq a)

readListPrec :: ReadPrec [Seq a]

Show a => Show (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

showsPrec :: Int -> Seq a -> ShowS

show :: Seq a -> String

showList :: [Seq a] -> ShowS

Semigroup (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

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 # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

mempty :: Seq a

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

mconcat :: [Seq a] -> Seq a

Arbitrary a => Arbitrary (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

Methods

arbitrary :: Gen (Seq a)

shrink :: Seq a -> [Seq a]

CoArbitrary a => CoArbitrary (Seq a) Source # 
Instance details

Defined in Data.Edison.Seq.SimpleQueue

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 #

inBounds :: Int -> Seq a -> Bool 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

moduleName :: String Source #