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

Data.Edison.Seq.BinaryRandList

Contents

Sequence Type
Sequence Operations
Unit testing
Documentation

Description

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.

Synopsis

Sequence Type

data Seq a Source #

Instances

Monad Seq Source #
Methods (>>=) :: Seq a -> (a -> Seq b) -> Seq b # (>>) :: Seq a -> Seq b -> Seq b # return :: a -> Seq a # fail :: String -> Seq a #
Functor Seq Source #
Methods fmap :: (a -> b) -> Seq a -> Seq b # (<$) :: a -> Seq b -> Seq a #
Applicative Seq Source #
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 #
Sequence Seq Source #
Methods lcons :: a -> Seq a -> Seq a # rcons :: a -> Seq a -> Seq a # fromList :: [a] -> Seq a # copy :: Int -> a -> Seq a # lview :: Monad m => Seq a -> m (a, Seq a) # lhead :: Seq a -> a # lheadM :: Monad m => Seq a -> m a # ltail :: Seq a -> Seq a # ltailM :: Monad m => Seq a -> m (Seq a) # rview :: Monad m => Seq a -> m (a, Seq a) # rhead :: Seq a -> a # rheadM :: Monad m => Seq a -> m a # rtail :: Seq a -> Seq a # rtailM :: Monad 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 :: 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 # 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 Source #
Methods empty :: Seq a # (<\|>) :: Seq a -> Seq a -> Seq a # some :: Seq a -> Seq [a] # many :: Seq a -> Seq [a] #
MonadPlus Seq Source #
Methods mzero :: Seq a # mplus :: Seq a -> Seq a -> Seq a #
Eq a => Eq (Seq a) Source #
Methods (==) :: Seq a -> Seq a -> Bool # (/=) :: Seq a -> Seq a -> Bool #
Ord a => Ord (Seq a) Source #
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 #
Read a => Read (Seq a) Source #
Methods readsPrec :: Int -> ReadS (Seq a) # readList :: ReadS [Seq a] # readPrec :: ReadPrec (Seq a) # readListPrec :: ReadPrec [Seq a] #
Show a => Show (Seq a) Source #
Methods showsPrec :: Int -> Seq a -> ShowS # show :: Seq a -> String # showList :: [Seq a] -> ShowS #
Semigroup (Seq a) Source #
Methods (<>) :: Seq a -> Seq a -> Seq a # sconcat :: NonEmpty (Seq a) -> Seq a # stimes :: Integral b => b -> Seq a -> Seq a #
Monoid (Seq a) Source #
Methods mempty :: Seq a # mappend :: Seq a -> Seq a -> Seq a # mconcat :: [Seq a] -> Seq a #
Arbitrary a => Arbitrary (Seq a) Source #
Methods arbitrary :: Gen (Seq a) # shrink :: Seq a -> [Seq a] #
CoArbitrary a => CoArbitrary (Seq a) Source #
Methods coarbitrary :: Seq a -> Gen b -> Gen b #