EdisonCore-1.3: 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.RandList

Contents

Description

Random-Access Lists. All operations are as listed in Data.Edison.Seq except the following:

  • rhead*, size O( log n )
  • copy, inBounds O( log i )
  • lookup*, update, adjust, drop O( min( i, log n ) )
  • subseq O( min( i, log n ) + len )

References:

  • Chris Okasaki. Purely Functional Data Structures. 1998. Section 9.3.1.
  • Chris Okasaki. "Purely Functional Random Access Lists". FPCA'95, pages 86-95.

Synopsis

Sequence Type

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

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