EdisonCore-1.3: A library of efficent, purely-functional data structures (Core Implementations)

CopyrightCopyright (c) 1998-1999, 2008 Chris Okasaki
LicenseMIT; see COPYRIGHT file for terms and conditions
Maintainerrobdockins AT fastmail DOT fm
Stabilitystable
PortabilityGHC, Hugs (MPTC and FD)
Safe HaskellNone
LanguageHaskell2010

Data.Edison.Seq.MyersStack

Contents

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

Sequence Type

Sequence Operations

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

lheadM :: Monad m => Seq a -> m a Source

ltailM :: Monad m => Seq a -> m (Seq a) Source

rheadM :: Monad m => Seq a -> m a Source

rtailM :: Monad m => Seq a -> m (Seq a) 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

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

Documentation