A randomaccess list implementation based on Chris Okasaki's approach on his book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 9.3.
It provides randomaccess (lookup
, update
, etc.) in O(log n) while
the list functionality head
, tail
and cons
still works in O(1).
A RandomAccessList
uses Int
s for effective indexing. The valid index
range of a RandomAccessList
of size n
is [0 .. n1]
. 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.
 data RandomAccessList a
 (.!.) :: RandomAccessList a > Int > a
 (.:.) :: a > RandomAccessList a > RandomAccessList a
 (.+.) :: RandomAccessList a > RandomAccessList a > RandomAccessList a
 empty :: RandomAccessList a
 singleton :: a > RandomAccessList a
 replicate :: Int > a > RandomAccessList a
 null :: RandomAccessList a > Bool
 isEmpty :: RandomAccessList a > Bool
 size :: RandomAccessList a > Int
 member :: Eq a => a > RandomAccessList a > Bool
 index :: (Eq a, Monad m) => a > RandomAccessList a > m Int
 head :: RandomAccessList a > a
 tail :: RandomAccessList a > RandomAccessList a
 extractHead :: RandomAccessList a > (a, RandomAccessList a)
 cons :: a > RandomAccessList a > RandomAccessList a
 append :: RandomAccessList a > RandomAccessList a > RandomAccessList a
 zip :: RandomAccessList a > RandomAccessList b > RandomAccessList (a, b)
 zipWith :: (a > b > c) > RandomAccessList a > RandomAccessList b > RandomAccessList c
 lookup :: Int > RandomAccessList a > a
 update :: Int > a > RandomAccessList a > RandomAccessList a
 adjust :: (a > a) > Int > RandomAccessList a > RandomAccessList a
 adjustLookup :: (a > a) > Int > RandomAccessList a > (a, RandomAccessList a)
 fromList :: [a] > RandomAccessList a
 toList :: RandomAccessList a > [a]
 toIndexedList :: RandomAccessList a > [(Int, a)]
 toMap :: RandomAccessList a > Map Int a
 toIntMap :: RandomAccessList a > IntMap a
 fromArray :: (IArray a e, Ix i) => a i e > RandomAccessList e
 toArray :: IArray a e => RandomAccessList e > a Int e
The RandomAccessList type
data RandomAccessList a Source
Randomaccess lists allowing O(1) list operations and O(log n) indexed access.
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 > aSource
(.:.) :: a > RandomAccessList a > RandomAccessList aSource
O(1). Prepend an element to the RandomAccessList
, see cons
.
(.+.) :: RandomAccessList a > RandomAccessList a > RandomAccessList aSource
O(n) where n is the size of the first list. Appends two
RandomAccessList
s, see append
.
Construction
empty :: RandomAccessList aSource
O(1). Builds an empty RandomAccessList
.
singleton :: a > RandomAccessList aSource
O(1). Builds a singleton RandomAccessList
.
replicate :: Int > a > RandomAccessList aSource
O(n).
constructs a replicate
n xRandomAccessList
that
contains the same element x
n
times.
Query
null :: RandomAccessList a > BoolSource
O(1). Is the RandomAccessList
empty?
isEmpty :: RandomAccessList a > BoolSource
O(1). Is the RandomAccessList
empty?
size :: RandomAccessList a > IntSource
O(1). The number of elements contained in a RandomAccessList
.
member :: Eq a => a > RandomAccessList a > BoolSource
O(n). Is the given element a member of the RandomAccessList
?
index :: (Eq a, Monad m) => a > RandomAccessList a > m IntSource
O(n). Find the index of a given element. If the element is not
a member of the RandomAccessList
, this function will fail
or
otherwise.
return
index
List specific operations
head :: RandomAccessList a > aSource
O(1). Returns the head of a RandomAccessList
.
tail :: RandomAccessList a > RandomAccessList aSource
O(1). Retrieve the tail of a RandomAccessList
.
extractHead :: RandomAccessList a > (a, RandomAccessList a)Source
O(1). Retrieve both, head
and tail
of a RandomAccessList
.
cons :: a > RandomAccessList a > RandomAccessList aSource
O(1). Prepend an element to the RandomAccessList
.
append :: RandomAccessList a > RandomAccessList a > RandomAccessList aSource
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)Source
O(max(n, m)). Listlike zip
. This function is faster
when called with two RandomAccessList
s of equal size.
zipWith :: (a > b > c) > RandomAccessList a > RandomAccessList b > RandomAccessList cSource
O(max(n, m)). Listlike zipWith
. This function is faster
when called with two RandomAccessList
s of equal size.
Randomaccess specific operations
lookup :: Int > RandomAccessList a > aSource
O(log n). Retrieve the ith element of the list. Unless
0 <= i < n, an error
is raised.
update :: Int > a > RandomAccessList a > RandomAccessList aSource
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 aSource
O(log n). Adjust ith element of the list according to the
given function. Unless 0 <= i < n, an error
is raised.
:: (a > a)  Modifying element function. 
> Int  Index of the affected element. 
> RandomAccessList a 

> (a, RandomAccessList a)  Original element and modified 
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 aSource
O(n). Build a RandomAccessList
from a list.
toList :: RandomAccessList a > [a]Source
O(n). Convert a RandomAccessList
to a list.
toIndexedList :: RandomAccessList a > [(Int, a)]Source
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 aSource
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 aSource
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 eSource
O(n). Given an IArray
, generate a RandomAccessList
. The elements'
order will be preserved.
toArray :: IArray a e => RandomAccessList e > a Int eSource
O(n). Build an IArray
from the RandomAccessList
. It will have
an index range from [0 .. n1]
, where n
is the RandomAccessList
s
size
.