Data.Edison.Seq.BinaryRandList

Binary Random-Access lists. All functions have the standard running times from Data.Edison.Seq except the following:

• lcons, lhead, ltail*, lview*, rhead*, size, lookup*, update, adjust, drop O( log n )
• copy, inBounds O( i )
• append, reverseOnto O( n1 + log n2 )
• take, splitAt O( i + log n )
• subseq O( log n + len )
• zip O( min( n1, n2 ) + log max( n1, n2 ) )

References:

• Chris Okasaki. Purely Functional Data Structures. 1998. Section 10.1.2.

Sequence Type

data Seq a

Instances

Sequence Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

lcons :: a -> Seq a -> Seq a

rcons :: a -> Seq a -> Seq a

fromList :: [a] -> Seq a

copy :: Int -> a -> Seq a

lview :: MonadFail m => Seq a -> m (a, Seq a)

lhead :: Seq a -> a

lheadM :: MonadFail m => Seq a -> m a

ltail :: Seq a -> Seq a

ltailM :: MonadFail m => Seq a -> m (Seq a)

rview :: MonadFail m => Seq a -> m (a, Seq a)

rhead :: Seq a -> a

rheadM :: MonadFail m => Seq a -> m a

rtail :: Seq a -> Seq a

rtailM :: MonadFail m => Seq a -> m (Seq a)

null :: Seq a -> Bool

size :: Seq a -> Int

toList :: Seq a -> [a]

concat :: Seq (Seq a) -> Seq a

reverse :: Seq a -> Seq a

reverseOnto :: Seq a -> Seq a -> Seq a

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

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)

inBounds :: Int -> Seq a -> Bool

lookup :: Int -> Seq a -> a

lookupM :: MonadFail 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

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

instanceName :: Seq a -> String

Alternative Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

empty :: Seq a

(<|>) :: Seq a -> Seq a -> Seq a

some :: Seq a -> Seq [a]

many :: Seq a -> Seq [a]

Applicative Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

pure :: a -> Seq a

(<*>) :: Seq (a -> b) -> Seq a -> Seq b

liftA2 :: (a -> b -> c) -> Seq a -> Seq b -> Seq c

(*>) :: Seq a -> Seq b -> Seq b

(<*) :: Seq a -> Seq b -> Seq a

Functor Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

fmap :: (a -> b) -> Seq a -> Seq b

(<$) :: a -> Seq b -> Seq a

Monad Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

(>>=) :: Seq a -> (a -> Seq b) -> Seq b

(>>) :: Seq a -> Seq b -> Seq b

return :: a -> Seq a

MonadPlus Seq

Defined in Data.Edison.Seq.BinaryRandList

Methods

mzero :: Seq a

mplus :: Seq a -> Seq a -> Seq a

Arbitrary a => Arbitrary (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

arbitrary :: Gen (Seq a)

shrink :: Seq a -> [Seq a]

CoArbitrary a => CoArbitrary (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

coarbitrary :: Seq a -> Gen b -> Gen b

Monoid (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

mempty :: Seq a

mappend :: Seq a -> Seq a -> Seq a

mconcat :: [Seq a] -> Seq a

Semigroup (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

(<>) :: Seq a -> Seq a -> Seq a

sconcat :: NonEmpty (Seq a) -> Seq a

stimes :: Integral b => b -> Seq a -> Seq a

Read a => Read (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

readsPrec :: Int -> ReadS (Seq a)

readList :: ReadS [Seq a]

readPrec :: ReadPrec (Seq a)

readListPrec :: ReadPrec [Seq a]

Show a => Show (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

showsPrec :: Int -> Seq a -> ShowS

show :: Seq a -> String

showList :: [Seq a] -> ShowS

Eq a => Eq (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

(==) :: Seq a -> Seq a -> Bool

(/=) :: Seq a -> Seq a -> Bool

Ord a => Ord (Seq a)

Defined in Data.Edison.Seq.BinaryRandList

Methods

compare :: Seq a -> Seq a -> Ordering

(<) :: Seq a -> Seq a -> Bool

(<=) :: Seq a -> Seq a -> Bool

(>) :: Seq a -> Seq a -> Bool

(>=) :: Seq a -> Seq a -> Bool

max :: Seq a -> Seq a -> Seq a

min :: Seq a -> Seq a -> Seq a

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 :: MonadFail m => Seq a -> m (a, Seq a)

lhead :: Seq a -> a

ltail :: Seq a -> Seq a

rview :: MonadFail m => Seq a -> m (a, Seq a)

rhead :: Seq a -> a

rtail :: Seq a -> Seq a

lheadM :: MonadFail m => Seq a -> m a

ltailM :: MonadFail m => Seq a -> m (Seq a)

rheadM :: MonadFail m => Seq a -> m a

rtailM :: MonadFail 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 :: MonadFail 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

Unit testing

structuralInvariant :: Seq a -> Bool

Documentation

moduleName :: String