 | EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations) | Contents | Index |
|
| Data.Edison.Seq.SimpleQueue | | Portability | GHC, Hugs (MPTC and FD) | | Stability | stable | | Maintainer | robdockins AT fastmail DOT fm |
|
|
|
|
|
| Description |
Simple Queues. All operations have running times as listed in
Data.Edison.Seq except for the following:
- rcons, fromList O( 1 )
- lview, ltail* O( 1 ) if single threaded, O( n ) otherwise
- inBounds, lookup, update, drop, splitAt O( n )
References:
- Chris Okasaki. Purely Functional Data Structures. 1998.
Section 5.2.
- F. Warren Burton. "An efficient functional implementation of FIFO queues".
Information Processing Letters, 14(5):205-206, July 1982.
|
|
| 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 | | | foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b | | | foldrWithIndex' :: (Int -> a -> b -> 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 | |
|
|
| 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 |
|
| foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b |
|
| foldrWithIndex' :: (Int -> a -> b -> 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 |