ralist-0.2.1.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

# Basic functions

cons :: a -> RAList a -> RAList a infixr 5 Source #

Complexity O(1).

uncons :: RAList a -> Maybe (a, RAList a) Source #

(++) :: RAList a -> RAList a -> RAList a infixr 5 Source #

head :: RAList a -> Maybe a Source #

Complexity O(1).

last :: RAList a -> a Source #

Complexity O(log n).

tail :: RAList a -> Maybe (RAList a) Source #

Complexity O(1).

Complexity O(1).

# Indexing lists

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

(!!) :: RAList a -> Word64 -> a infixl 9 Source #

Complexity O(log n).

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

lookupM :: forall m a. Monad m => Word64 -> Top a -> m a Source #

lookup :: forall a. Word64 -> Top a -> a Source #

lookupL :: Eq a => a -> RAList (a, b) -> Maybe b Source #

# List transformations

map :: (a -> b) -> RAList a -> RAList b Source #

foldl :: (a -> b -> a) -> a -> RAList b -> a Source #

foldl' :: (a -> b -> a) -> a -> RAList b -> a Source #

foldl1 :: (a -> a -> a) -> RAList a -> a Source #

foldl1' :: (a -> a -> a) -> RAList a -> a Source #

foldr :: (a -> b -> b) -> b -> RAList a -> b Source #

foldr1 :: (a -> a -> a) -> RAList a -> a Source #

## Special folds

concatMap :: (a -> RAList b) -> RAList a -> RAList b Source #

any :: (a -> Bool) -> RAList a -> Bool Source #

all :: (a -> Bool) -> RAList a -> Bool Source #

sum :: Num a => RAList a -> a Source #

product :: Num a => RAList a -> a Source #

maximum :: Ord a => RAList a -> a Source #

minimum :: Ord a => RAList a -> a Source #

# Sublists

## Extracting sublists

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

drop i l drop i l where l has length n has worst case complexity Complexity O(log n), Average case complexity should be O(min(log i, log n)).

# Searching lists

## Searching by equality

elem :: Eq a => a -> RAList a -> Bool Source #

notElem :: Eq a => a -> RAList a -> Bool Source #

filter :: (a -> Bool) -> RAList a -> RAList a Source #

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

# Zipping and unzipping lists

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

zipWith :: (a -> b -> c) -> RAList a -> RAList b -> RAList c Source #

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

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

# List conversion

toList :: RAList a -> [a] Source #

Complexity O(n).

fromList :: [a] -> RAList a Source #

Complexity O(n).