Portability | GHC, Hugs (MPTC and FD) |
---|---|
Stability | stable |
Maintainer | robdockins AT fastmail DOT fm |
One-sided Braun sequences. All running times are as listed in Data.Edison.Seq except the following:
- lview, lcons, ltail*
O( log n )
- rcons, rview, rhead*, rtail*, size
O( log^2 n )
- copy, inBounds, lookup*, update, adjust
O( log i )
- append
O( n1 log n2 )
- concat
O( n + m log m )
- drop, splitAt
O( i log n )
- subseq
O( i log n + len )
- reverseOnto
O( n1 log n2 )
- concatMap, (>>=)
O( n * t + m log m )
, wheren
is the length of the input sequencem
is the length of the output sequence andt
is the running time off
By keeping track of the size, we could get rcons, rview, rhead*, and rtail*
down to O(log n)
as well; furthermore, size would be O( 1 )
.
References:
- Rob Hoogerwoord. "A symmetric set of efficient list operations". Journal of Functional Programming, 2(4):505--513, 1992.
- Rob Hoogerwoord. "A Logarithmic Implementation of Flexible Arrays". Mathematics of Program Construction (MPC'92), pages 191-207.
- Chris Okasaki. "Three algorithms on Braun Trees". Journal of Function Programming 7(6):661-666. Novemebr 1997.
- 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
Sequence Operations
reverseOnto :: Seq a -> Seq a -> Seq aSource
lookupWithDefault :: a -> Int -> Seq a -> aSource
mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq bSource
foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> bSource
foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Seq a -> bSource
foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> bSource
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Seq a -> bSource
strictWith :: (a -> b) -> Seq a -> Seq aSource
Unit testing
structuralInvariant :: Seq a -> BoolSource