Safe Haskell	Safe
Language	Haskell2010

Data.RAList

Contents

Basic functions
Indexing lists
List transformations
- Special folds
Building lists
- Repetition
Sublists
- Extracting sublists
Searching lists
- Searching by equality
Zipping and unzipping lists
Update
List conversion

Description

A random-access list implementation based on Chris Okasaki's approach on his book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 9.3.

RAList is a replacement for ordinary finite lists. RAList provides the same complexity as ordinary for most the list operations. Some operations take O(log n) for RAList where the list operation is O(n), notably indexing, '(!!)'.

Synopsis

data RAList a
empty :: RAList a
cons :: a -> RAList a -> RAList a
uncons :: RAList a -> Maybe (a, RAList a)
(++) :: RAList a -> RAList a -> RAList a
head :: RAList a -> Maybe a
last :: RAList a -> a
tail :: RAList a -> Maybe (RAList a)
init :: RAList a -> RAList a
null :: RAList a -> Bool
length :: RAList a -> Word64
(!!) :: RAList a -> Word64 -> a
lookupWithDefault :: forall t. t -> Word64 -> Top t -> t
lookupM :: forall (m :: * -> *) a. Monad m => Word64 -> Top a -> m a
lookup :: forall a. Word64 -> Top a -> a
lookupL :: Eq a => a -> RAList (a, b) -> Maybe b
map :: (a -> b) -> RAList a -> RAList b
reverse :: RAList a -> RAList a
foldl :: (a -> b -> a) -> a -> RAList b -> a
foldl' :: (a -> b -> a) -> a -> RAList b -> a
foldl1 :: (a -> a -> a) -> RAList a -> a
foldl1' :: (a -> a -> a) -> RAList a -> a
foldr :: (a -> b -> b) -> b -> RAList a -> b
foldr1 :: (a -> a -> a) -> RAList a -> a
concat :: RAList (RAList a) -> RAList a
concatMap :: (a -> RAList b) -> RAList a -> RAList b
and :: RAList Bool -> Bool
or :: RAList Bool -> Bool
any :: (a -> Bool) -> RAList a -> Bool
all :: (a -> Bool) -> RAList a -> Bool
sum :: Num a => RAList a -> a
product :: Num a => RAList a -> a
maximum :: Ord a => RAList a -> a
minimum :: Ord a => RAList a -> a
replicate :: Word64 -> a -> RAList a
take :: Word64 -> RAList a -> RAList a
drop :: Word64 -> RAList a -> RAList a
simpleDrop :: Word64 -> RAList a -> RAList a
splitAt :: Word64 -> RAList a -> (RAList a, RAList a)
elem :: Eq a => a -> RAList a -> Bool
notElem :: Eq a => a -> RAList a -> Bool
filter :: (a -> Bool) -> RAList a -> RAList a
partition :: (a -> Bool) -> RAList a -> (RAList a, RAList a)
zip :: RAList a -> RAList b -> RAList (a, b)
zipWith :: (a -> b -> c) -> RAList a -> RAList b -> RAList c
unzip :: RAList (a, b) -> (RAList a, RAList b)
update :: Word64 -> a -> RAList a -> RAList a
adjust :: (a -> a) -> Word64 -> RAList a -> RAList a
toList :: RAList a -> [a]
fromList :: [a] -> RAList a

Documentation

data RAList a Source #

Instances

Monad RAList Source #
Instance details Defined in Data.RAList Methods (>>=) :: RAList a -> (a -> RAList b) -> RAList b # (>>) :: RAList a -> RAList b -> RAList b # return :: a -> RAList a # fail :: String -> RAList a #
Functor RAList Source #
Instance details Defined in Data.RAList Methods fmap :: (a -> b) -> RAList a -> RAList b # (<$) :: a -> RAList b -> RAList a #
Applicative RAList Source #
Instance details Defined in Data.RAList Methods pure :: a -> RAList a # (<>) :: RAList (a -> b) -> RAList a -> RAList b # liftA2 :: (a -> b -> c) -> RAList a -> RAList b -> RAList c # (>) :: RAList a -> RAList b -> RAList b # (<*) :: RAList a -> RAList b -> RAList a #
Foldable RAList Source #
Instance details Defined in Data.RAList Methods fold :: Monoid m => RAList m -> m # foldMap :: Monoid m => (a -> m) -> RAList a -> m # foldr :: (a -> b -> b) -> b -> RAList a -> b # foldr' :: (a -> b -> b) -> b -> RAList a -> b # foldl :: (b -> a -> b) -> b -> RAList a -> b # foldl' :: (b -> a -> b) -> b -> RAList a -> b # foldr1 :: (a -> a -> a) -> RAList a -> a # foldl1 :: (a -> a -> a) -> RAList a -> a # toList :: RAList a -> [a] # null :: RAList a -> Bool # length :: RAList a -> Int # elem :: Eq a => a -> RAList a -> Bool # maximum :: Ord a => RAList a -> a # minimum :: Ord a => RAList a -> a # sum :: Num a => RAList a -> a # product :: Num a => RAList a -> a #
Traversable RAList Source #
Instance details Defined in Data.RAList Methods traverse :: Applicative f => (a -> f b) -> RAList a -> f (RAList b) # sequenceA :: Applicative f => RAList (f a) -> f (RAList a) # mapM :: Monad m => (a -> m b) -> RAList a -> m (RAList b) # sequence :: Monad m => RAList (m a) -> m (RAList a) #
Eq a => Eq (RAList a) Source #
Instance details Defined in Data.RAList Methods (==) :: RAList a -> RAList a -> Bool # (/=) :: RAList a -> RAList a -> Bool #
Data a => Data (RAList a) Source #
Instance details Defined in Data.RAList Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> RAList a -> c (RAList a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (RAList a) # toConstr :: RAList a -> Constr # dataTypeOf :: RAList a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (RAList a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (RAList a)) # gmapT :: (forall b. Data b => b -> b) -> RAList a -> RAList a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> RAList a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> RAList a -> r # gmapQ :: (forall d. Data d => d -> u) -> RAList a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> RAList a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> RAList a -> m (RAList a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> RAList a -> m (RAList a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> RAList a -> m (RAList a) #
Ord a => Ord (RAList a) Source #
Instance details Defined in Data.RAList Methods compare :: RAList a -> RAList a -> Ordering # (<) :: RAList a -> RAList a -> Bool # (<=) :: RAList a -> RAList a -> Bool # (>) :: RAList a -> RAList a -> Bool # (>=) :: RAList a -> RAList a -> Bool # max :: RAList a -> RAList a -> RAList a # min :: RAList a -> RAList a -> RAList a #
Read a => Read (RAList a) Source #
Instance details Defined in Data.RAList Methods readsPrec :: Int -> ReadS (RAList a) # readList :: ReadS [RAList a] # readPrec :: ReadPrec (RAList a) # readListPrec :: ReadPrec [RAList a] #
Show a => Show (RAList a) Source #
Instance details Defined in Data.RAList Methods showsPrec :: Int -> RAList a -> ShowS # show :: RAList a -> String # showList :: [RAList a] -> ShowS #
Semigroup (RAList a) Source #
Instance details Defined in Data.RAList Methods (<>) :: RAList a -> RAList a -> RAList a # sconcat :: NonEmpty (RAList a) -> RAList a # stimes :: Integral b => b -> RAList a -> RAList a #
Monoid (RAList a) Source #
Instance details Defined in Data.RAList Methods mempty :: RAList a # mappend :: RAList a -> RAList a -> RAList a # mconcat :: [RAList a] -> RAList a #