ralist-0.1.0.0: Random access list with a list compatible interface.

Data.RAList

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

# Documentation

data RAList a Source

Instances

 Monad RAList Functor RAList Eq a => Eq (RAList a) Ord a => Ord (RAList a) Read a => Read (RAList a) Show a => Show (RAList a) Monoid (RAList a)

# Basic functions

cons :: a -> RAList a -> RAList aSource

Complexity O(1).

head :: RAList a -> aSource

Complexity O(1).

last :: RAList a -> aSource

Complexity O(log n).

tail :: RAList a -> RAList aSource

Complexity O(1).

length :: RAList a -> IntSource

Complexity O(1).

# List transformations

map :: (a -> b) -> RAList a -> RAList bSource

foldl :: (a -> b -> a) -> a -> RAList b -> aSource

foldl' :: (a -> b -> a) -> a -> RAList b -> aSource

foldl1 :: (a -> a -> a) -> RAList a -> aSource

foldl1' :: (a -> a -> a) -> RAList a -> aSource

foldr :: (a -> b -> b) -> b -> RAList a -> bSource

foldr1 :: (a -> a -> a) -> RAList a -> aSource

## Special folds

concatMap :: (a -> RAList b) -> RAList a -> RAList bSource

any :: (a -> Bool) -> RAList a -> BoolSource

all :: (a -> Bool) -> RAList a -> BoolSource

sum :: Num a => RAList a -> aSource

product :: Num a => RAList a -> aSource

maximum :: Ord a => RAList a -> aSource

minimum :: Ord a => RAList a -> aSource

# Sublists

## Extracting sublists

drop :: Int -> RAList a -> RAList aSource

Complexity O(log n).

# Searching lists

## Searching by equality

elem :: Eq a => a -> RAList a -> BoolSource

notElem :: Eq a => a -> RAList a -> BoolSource

lookup :: Eq a => a -> RAList (a, b) -> Maybe bSource

filter :: (a -> Bool) -> RAList a -> RAList aSource

partition :: (a -> Bool) -> RAList a -> (RAList a, RAList a)Source

# Indexing lists

These functions treat a list `xs` as a indexed collection, with indices ranging from 0 to `length xs - 1`.

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

Complexity O(log n).

# Zipping and unzipping lists

zip :: RAList a -> RAList b -> RAList (a, b)Source

zipWith :: (a -> b -> c) -> RAList a -> RAList b -> RAList cSource

unzip :: RAList (a, b) -> (RAList a, RAList b)Source

# 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).

# List conversion

toList :: RAList a -> [a]Source

Complexity O(n).

fromList :: [a] -> RAList aSource

Complexity O(n).