Data.RandomAccessList

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.

It provides random-access (lookup, update, etc.) in O(log n) while the list functionality head, tail and cons still works in O(1).

A RandomAccessList uses Ints for effective indexing. The valid index range of a RandomAccessList of size n is [0 .. n-1]. If an index is out of range, an error is raised.

This module is best imported qualified in order to prevent name clashes with other modules.

The RandomAccessList type

data RandomAccessList a

Random-access lists allowing O(1) list operations and O(log n) indexed access.

Instances

Functor RandomAccessList

Foldable RandomAccessList

Eq a => Eq (RandomAccessList a)

Ord a => Ord (RandomAccessList a)

Read a => Read (RandomAccessList a)

Show a => Show (RandomAccessList a)

Monoid (RandomAccessList a)

Operators

(.!.) :: RandomAccessList a -> Int -> a

O(log n). Retrieve the ith element of the list. Unless 0 <= i < n, an error is raised, see lookup.

(.:.) :: a -> RandomAccessList a -> RandomAccessList a

O(1). Prepend an element to the RandomAccessList, see cons.

(.+.) :: RandomAccessList a -> RandomAccessList a -> RandomAccessList a

O(n) where n is the size of the first list. Appends two RandomAccessLists, see append.

Construction

empty :: RandomAccessList a

O(1). Builds an empty RandomAccessList.

singleton :: a -> RandomAccessList a

O(1). Builds a singleton RandomAccessList.

replicate :: Int -> a -> RandomAccessList a

O(n). replicate n x constructs a RandomAccessList that contains the same element x n times.

Query

null :: RandomAccessList a -> Bool

O(1). Is the RandomAccessList empty?

isEmpty :: RandomAccessList a -> Bool

O(1). Is the RandomAccessList empty?

size :: RandomAccessList a -> Int

O(1). The number of elements contained in a RandomAccessList.

member :: Eq a => a -> RandomAccessList a -> Bool

O(n). Is the given element a member of the RandomAccessList?

index :: (Eq a, Monad m) => a -> RandomAccessList a -> m Int

O(n). Find the index of a given element. If the element is not a member of the RandomAccessList, this function will fail or return index otherwise.

List specific operations

head :: RandomAccessList a -> a

O(1). Returns the head of a RandomAccessList.

tail :: RandomAccessList a -> RandomAccessList a

O(1). Retrieve the tail of a RandomAccessList.

extractHead :: RandomAccessList a -> (a, RandomAccessList a)

O(1). Retrieve both, head and tail of a RandomAccessList.

cons :: a -> RandomAccessList a -> RandomAccessList a

O(1). Prepend an element to the RandomAccessList.

append :: RandomAccessList a -> RandomAccessList a -> RandomAccessList a

O(n) where n is the size of the first list. Appends the second list to the first list.

zip :: RandomAccessList a -> RandomAccessList b -> RandomAccessList (a, b)

O(max(n, m)). List-like zip. This function is faster when called with two RandomAccessLists of equal size.

zipWith :: (a -> b -> c) -> RandomAccessList a -> RandomAccessList b -> RandomAccessList c

O(max(n, m)). List-like zipWith. This function is faster when called with two RandomAccessLists of equal size.

Random-access specific operations

lookup :: Int -> RandomAccessList a -> a

O(log n). Retrieve the ith element of the list. Unless 0 <= i < n, an error is raised.

update :: Int -> a -> RandomAccessList a -> RandomAccessList a

O(log n). Set the ith element of the list. Unless 0 <= i < n, an error is raised.

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

O(log n). Adjust ith element of the list according to the given function. Unless 0 <= i < n, an error is raised.

adjustLookup

Arguments

:: (a -> a)

Modifying element function.

-> Int

Index of the affected element.

-> RandomAccessList a

RandomAccessList to be modified.

-> (a, RandomAccessList a)

Original element and modified RandomAccessList.

O(log n). Find the ith element of the list and change it. This function returns the element that is at index i in the original RandomAccessList and a new RandomAccessList with the ith element replaced according to the given function:

    lookup   index list === fst (adjustLookup undefined index list)
    adjust f index list === snd (adjustLookup f         index list)

Unless 0 <= i < n, an error is raised.

Conversion

List

fromList :: [a] -> RandomAccessList a

O(n). Build a RandomAccessList from a list.

toList :: RandomAccessList a -> [a]

O(n). Convert a RandomAccessList to a list.

toIndexedList :: RandomAccessList a -> [(Int, a)]

O(n). Convert a RandomAccessList to a list of tuples each holding an element and its index. The list is ordered ascending regarding the indices.

Map

toMap :: RandomAccessList a -> Map Int a

O(n). Build a Map from a RandomAccessList. The keys in the Map are the indices of the elements in the RandomAccessList.

toIntMap :: RandomAccessList a -> IntMap a

O(n). Build an IntMap from a RandomAccessList. The keys in the IntMap are the indices of the elements in the RandomAccessList.

Array

fromArray :: (IArray a e, Ix i) => a i e -> RandomAccessList e

O(n). Given an IArray, generate a RandomAccessList. The elements' order will be preserved.

toArray :: IArray a e => RandomAccessList e -> a Int e

O(n). Build an IArray from the RandomAccessList. It will have an index range from [0 .. n-1], where n is the RandomAccessLists size.