Safe Haskell | Safe-Infered |
---|

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, '(!!)'.

- data RAList a
- empty :: RAList a
- cons :: a -> RAList a -> RAList a
- (++) :: RAList a -> RAList a -> RAList a
- head :: RAList a -> a
- last :: RAList a -> a
- tail :: RAList a -> RAList a
- init :: RAList a -> RAList a
- null :: RAList a -> Bool
- length :: RAList a -> Int
- 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 :: Int -> a -> RAList a
- take :: Int -> RAList a -> RAList a
- drop :: Int -> RAList a -> RAList a
- splitAt :: Int -> RAList a -> (RAList a, RAList a)
- elem :: Eq a => a -> RAList a -> Bool
- notElem :: Eq a => a -> RAList a -> Bool
- lookup :: Eq a => a -> RAList (a, b) -> Maybe b
- filter :: (a -> Bool) -> RAList a -> RAList a
- partition :: (a -> Bool) -> RAList a -> (RAList a, RAList a)
- (!!) :: RAList a -> Int -> 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 :: Int -> a -> RAList a -> RAList a
- adjust :: (a -> a) -> Int -> RAList a -> RAList a
- toList :: RAList a -> [a]
- fromList :: [a] -> RAList a

# Documentation

# Basic functions

# List transformations

## Special folds

# Building lists

## Repetition

# Sublists

## Extracting sublists

# Searching lists

## Searching by equality

# Indexing lists

These functions treat a list `xs`

as a indexed collection,
with indices ranging from 0 to

.
`length`

xs - 1

# Zipping and unzipping lists

# Update

update :: Int -> a -> RAList a -> RAList aSource

Change element at the given index.
Complexity *O(log n)*.

adjust :: (a -> a) -> Int -> RAList a -> RAList aSource

Apply a function to the value at the given index.
Complexity *O(log n)*.