EdisonCore-1.2.1.3: A library of efficent, purely-functional data structures (Core Implementations)

PortabilityGHC, Hugs (MPTC and FD)
Stabilitystable
Maintainerrobdockins AT fastmail DOT fm

Data.Edison.Seq.BinaryRandList

Contents

Description

Binary Random-Access lists. All functions have the standard running times from Data.Edison.Seq except the following:

  • lcons, lhead, ltail*, lview*, rhead*, size, lookup*, update, adjust, drop O( log n )
  • copy, inBounds O( i )
  • append, reverseOnto O( n1 + log n2 )
  • take, splitAt O( i + log n )
  • subseq O( log n + len )
  • zip O( min( n1, n2 ) + log max( n1, n2 ) )

References:

  • Chris Okasaki. Purely Functional Data Structures. 1998. Section 10.1.2.

Synopsis

Sequence Type

data Seq a Source

Instances

Monad Seq 
Functor Seq 
MonadPlus Seq 
Sequence Seq 
Eq a => Eq (Seq a) 
Ord a => Ord (Seq a) 
Read a => Read (Seq a) 
Show a => Show (Seq a) 
Arbitrary a => Arbitrary (Seq a) 
Monoid (Seq a) 

Sequence Operations

lcons :: a -> Seq a -> Seq aSource

rcons :: a -> Seq a -> Seq aSource

append :: Seq a -> Seq a -> Seq aSource

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

lhead :: Seq a -> aSource

ltail :: Seq a -> Seq aSource

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

rhead :: Seq a -> aSource

rtail :: Seq a -> Seq aSource

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

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

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

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

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

reverseOnto :: Seq a -> Seq a -> Seq aSource

fromList :: [a] -> Seq aSource

toList :: Seq a -> [a]Source

map :: (a -> b) -> Seq a -> Seq bSource

concatMap :: (a -> Seq b) -> Seq a -> Seq bSource

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

copy :: Int -> a -> Seq aSource

lookup :: Int -> Seq a -> aSource

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

lookupWithDefault :: a -> Int -> Seq a -> aSource

update :: Int -> a -> Seq a -> Seq aSource

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

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

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

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

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

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

take :: Int -> Seq a -> Seq aSource

drop :: Int -> Seq a -> Seq aSource

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

subseq :: Int -> Int -> Seq a -> Seq aSource

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

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

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

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

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 cSource

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

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 aSource

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

Unit testing

Documentation