 | EdisonCore-1.2.1.1: A library of efficent, purely-functional data structures (Core Implementations) | Source code | Contents | Index |
|
| Data.Edison.Seq.BinaryRandList | | Portability | GHC, Hugs (MPTC and FD) | | Stability | stable | | Maintainer | robdockins AT fastmail DOT fm |
|
|
|
|
|
| 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
|
|
|
 Instances | |
|
|
| Sequence Operations
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| fold :: (a -> b -> b) -> b -> Seq a -> b | Source |
|
|
| fold' :: (a -> b -> b) -> b -> Seq a -> b | 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 |
|
|
|
|
|
|
|
|
|
|
| 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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Unit testing
|
|
|
|
| Documentation
|
|
|
|
| Produced by Haddock version 2.3.0 |