EdisonCore-1.3.2.1: A library of efficient, purely-functional data structures (Core Implementations)

Copyright Copyright (c) 1998-1999 2008 Chris Okasaki MIT; see COPYRIGHT file for terms and conditions robdockins AT fastmail DOT fm stable GHC, Hugs (MPTC and FD) None Haskell2010

Data.Edison.Seq.BraunSeq

Description

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 ), where n is the length of the input sequence m is the length of the output sequence and t is the running time of f

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.

Synopsis

# Sequence Type

data Seq a Source #

Instances

# 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 #

null :: Seq a -> Bool 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 #