EdisonCore-1.2.1.1: A library of efficent, purely-functional data structures (Core Implementations)Source codeContentsIndex
Data.Edison.Seq.MyersStack
PortabilityGHC, Hugs (MPTC and FD)
Stabilitystable
Maintainerrobdockins AT fastmail DOT fm
Contents
Sequence Type
Sequence Operations
Unit testing
Documentation
Description

Meyers Stacks. All operations are as listed in Data.Edison.Seq except the following:

  • lookup, inBounds, drop O( min(i, log n) )
  • rhead*, size O( log n )
  • subseq O( min (i, log n) + len )

References:

  • Eugene Myers. "An applicative random-access stack". /Information Processing Letters/, 17(5):241-248, December 1983.
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 Source
show/hide Instances
Sequence Operations
empty :: Seq aSource
singleton :: a -> Seq aSource
lcons :: a -> Seq a -> Seq aSource
rcons :: a -> Seq a -> Seq aSource
append :: Seq a -> Seq a -> Seq aSource
lview :: Monad m => Seq a -> m (a, Seq a)Source
lhead :: Seq a -> aSource
ltail :: Seq a -> Seq aSource
rview :: Monad m => Seq a -> m (a, Seq a)Source
rhead :: Seq a -> aSource
rtail :: Seq a -> Seq aSource
lheadM :: Monad m => Seq a -> m aSource
ltailM :: Monad m => Seq a -> m (Seq a)Source
rheadM :: Monad m => Seq a -> m aSource
rtailM :: Monad m => Seq a -> m (Seq a)Source
null :: Seq a -> BoolSource
size :: Seq a -> IntSource
concat :: Seq (Seq a) -> Seq aSource
reverse :: Seq a -> Seq aSource
reverseOnto :: Seq a -> Seq a -> Seq aSource
fromList :: [a] -> Seq aSource
toList :: Seq a -> [a]Source
map :: (a -> b) -> Seq a -> Seq bSource
concatMap :: (a -> Seq b) -> Seq a -> Seq bSource
fold :: (a -> b -> b) -> b -> Seq a -> bSource
fold' :: (a -> b -> b) -> b -> Seq a -> bSource
fold1 :: (a -> a -> a) -> Seq a -> aSource
fold1' :: (a -> a -> a) -> Seq a -> aSource
foldr :: (a -> b -> b) -> b -> Seq a -> bSource
foldr' :: (a -> b -> b) -> b -> Seq a -> bSource
foldl :: (b -> a -> b) -> b -> Seq a -> bSource
foldl' :: (b -> a -> b) -> b -> Seq a -> bSource
foldr1 :: (a -> a -> a) -> Seq a -> aSource
foldr1' :: (a -> a -> a) -> Seq a -> aSource
foldl1 :: (a -> a -> a) -> Seq a -> aSource
foldl1' :: (a -> a -> a) -> Seq a -> aSource
reducer :: (a -> a -> a) -> a -> Seq a -> aSource
reducer' :: (a -> a -> a) -> a -> Seq a -> aSource
reducel :: (a -> a -> a) -> a -> Seq a -> aSource
reducel' :: (a -> a -> a) -> a -> Seq a -> aSource
reduce1 :: (a -> a -> a) -> Seq a -> aSource
reduce1' :: (a -> a -> a) -> Seq a -> aSource
copy :: Int -> a -> Seq aSource
inBounds :: Int -> Seq a -> BoolSource
lookup :: Int -> Seq a -> aSource
lookupM :: Monad m => Int -> Seq a -> m aSource
lookupWithDefault :: a -> Int -> Seq a -> aSource
update :: Int -> a -> Seq a -> Seq aSource
adjust :: (a -> a) -> Int -> Seq a -> Seq 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
take :: Int -> Seq a -> Seq aSource
drop :: Int -> Seq a -> Seq aSource
splitAt :: Int -> Seq a -> (Seq a, Seq a)Source
subseq :: Int -> Int -> Seq a -> Seq aSource
filter :: (a -> Bool) -> Seq a -> Seq aSource
partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a)Source
takeWhile :: (a -> Bool) -> Seq a -> Seq aSource
dropWhile :: (a -> Bool) -> Seq a -> Seq aSource
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 cSource
zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq dSource
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 aSource
strictWith :: (a -> b) -> Seq a -> Seq aSource
Unit testing
structuralInvariant :: Seq a -> BoolSource
Documentation
moduleName :: StringSource
Produced by Haddock version 2.3.0