Data.RAList

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

Documentation

data RAList a

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

empty :: RAList a

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

Complexity O(1).

(++) :: RAList a -> RAList a -> RAList a

head :: RAList a -> a

Complexity O(1).

last :: RAList a -> a

Complexity O(log n).

tail :: RAList a -> RAList a

Complexity O(1).

init :: RAList a -> RAList a

null :: RAList a -> Bool

length :: RAList a -> Int

Complexity O(1).

List transformations

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

Special folds

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

Building lists

Repetition

replicate :: Int -> a -> RAList a

Sublists

Extracting sublists

take :: Int -> RAList a -> RAList a

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

Complexity O(log n).

splitAt :: Int -> RAList a -> (RAList a, RAList a)

Searching lists

Searching by equality

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)

Indexing lists

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

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

Complexity O(log n).

Zipping and unzipping lists

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

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

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

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

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

List conversion

toList :: RAList a -> [a]

Complexity O(n).

fromList :: [a] -> RAList a

Complexity O(n).