EdisonCore-1.3.1.1: A library of efficent, 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.JoinList

Contents

Description

Join lists. All running times are as listed in Data.Edison.Seq except for the following:

  • rcons, append O( 1 )
  • ltail*, lview O( 1 ) when used single-threaded, O( n ) otherwise
  • lhead* O( n )
  • inBounds, lookup O( n )
  • copy O( log i )
  • concat O( n1 )
  • concatMap, (>>=) O( n * t ), where n is the length of the input sequence and t is the running time of f

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 #

(*>) :: 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 #

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 #

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