Data.Edison.Seq.BinaryRandList
 Portability GHC, Hugs (MPTC and FD) Stability stable Maintainer robdockins AT fastmail DOT fm
 Contents Sequence Type Sequence Operations Unit testing Documentation
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
 data Seq a empty :: Seq a singleton :: a -> Seq a lcons :: a -> Seq a -> Seq a rcons :: a -> Seq a -> Seq a append :: Seq a -> Seq a -> Seq a lview :: Monad m => Seq a -> m (a, Seq a) lhead :: Seq a -> a ltail :: Seq a -> Seq a rview :: Monad m => Seq a -> m (a, Seq a) rhead :: Seq a -> a rtail :: Seq a -> Seq a lheadM :: Monad m => Seq a -> m a ltailM :: Monad m => Seq a -> m (Seq a) rheadM :: Monad m => Seq a -> m a rtailM :: Monad m => Seq a -> m (Seq a) null :: Seq a -> Bool size :: Seq a -> Int concat :: Seq (Seq a) -> Seq a reverse :: Seq a -> Seq a reverseOnto :: Seq a -> Seq a -> Seq a fromList :: [a] -> Seq a toList :: Seq a -> [a] map :: (a -> b) -> Seq a -> Seq b concatMap :: (a -> Seq b) -> Seq a -> Seq b 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 copy :: Int -> 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 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) 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 moduleName :: String
Sequence Type
data Seq a
Instances
 Functor Seq Monad Seq MonadPlus Seq Sequence Seq Arbitrary a => Arbitrary (Seq a) (Eq a, ??? a) => Eq (Seq a) Monoid (Seq a) Ord a => Ord (Seq a) Read a => Read (Seq a) Show a => Show (Seq a)
Sequence Operations
empty :: Seq a
singleton :: a -> Seq a
lcons :: a -> Seq a -> Seq a
rcons :: a -> Seq a -> Seq a
append :: Seq a -> Seq a -> Seq a
lview :: Monad m => Seq a -> m (a, Seq a)
lhead :: Seq a -> a
ltail :: Seq a -> Seq a
rview :: Monad m => Seq a -> m (a, Seq a)
rhead :: Seq a -> a
rtail :: Seq a -> Seq a
lheadM :: Monad m => Seq a -> m a
ltailM :: Monad m => Seq a -> m (Seq a)
rheadM :: Monad m => Seq a -> m a
rtailM :: Monad m => Seq a -> m (Seq a)
null :: Seq a -> Bool
size :: Seq a -> Int
concat :: Seq (Seq a) -> Seq a
reverse :: Seq a -> Seq a
reverseOnto :: Seq a -> Seq a -> Seq a
fromList :: [a] -> Seq a
toList :: Seq a -> [a]
map :: (a -> b) -> Seq a -> Seq b
concatMap :: (a -> Seq b) -> Seq a -> Seq b
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
copy :: Int -> 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
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)
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
Unit testing
structuralInvariant :: Seq a -> Bool
Documentation
moduleName :: String
Produced by Haddock version 0.8