Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

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

Monad RAList Source # | |

Functor RAList Source # | |

Applicative RAList Source # | |

Foldable RAList Source # | |

Traversable RAList Source # | |

Eq a => Eq (RAList a) Source # | |

Data a => Data (RAList a) Source # | |

Ord a => Ord (RAList a) Source # | |

Read a => Read (RAList a) Source # | |

Show a => Show (RAList a) Source # | |

Semigroup (RAList a) Source # | |

Monoid (RAList a) Source # | |

# Basic functions

# Indexing lists

These functions treat a list `xs`

as a indexed collection,
with indices ranging from 0 to

.`length`

xs - 1

lookupWithDefault :: forall t. t -> Word64 -> Top t -> t Source #

# List transformations

## Special folds

# Building lists

## Repetition

# Sublists

## Extracting sublists

drop :: Word64 -> RAList a -> RAList a Source #

drop i l

where l has length n has worst case complexity Complexity `drop`

i l*O(log n)*, Average case
complexity should be *O(min(log i, log n))*.

# Searching lists

## Searching by equality

# Zipping and unzipping lists

# Update

update :: Word64 -> a -> RAList a -> RAList a Source #

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

adjust :: (a -> a) -> Word64 -> RAList a -> RAList a Source #

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