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:

• 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) Monoid (Seq a) Arbitrary a => Arbitrary (Seq a)
Sequence Operations
 empty :: Seq a Source
 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
 ltailM :: Monad m => Seq a -> m (Seq 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
 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
 structuralInvariant :: Seq a -> Bool Source
Documentation
 moduleName :: String Source