A randomaccess list implementation based on Chris Okasaki's approach on his book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 9.3.
RandomAccessList
s are finite lists providing 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.
 data RandomAccessList a
 data View a
 = Empty
  Cons a (RandomAccessList a)
 empty :: RandomAccessList a
 singleton :: a > RandomAccessList a
 replicate :: Int > a > RandomAccessList a
 null :: RandomAccessList a > Bool
 isEmpty :: RandomAccessList a > Bool
 length :: RandomAccessList a > Int
 size :: RandomAccessList a > Int
 member :: Eq a => a > RandomAccessList a > Bool
 index :: Eq a => a > RandomAccessList a > Maybe Int
 head :: RandomAccessList a > a
 tail :: RandomAccessList a > RandomAccessList a
 uncons :: RandomAccessList a > (a, RandomAccessList a)
 view :: RandomAccessList a > View a
 cons :: a > RandomAccessList a > RandomAccessList a
 append :: RandomAccessList a > RandomAccessList a > RandomAccessList a
 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)
 filter :: (a > Bool) > RandomAccessList a > RandomAccessList a
 partition :: (a > Bool) > RandomAccessList a > (RandomAccessList a, RandomAccessList a)
 zip :: RandomAccessList a > RandomAccessList b > RandomAccessList (a, b)
 zipWith :: (a > b > c) > RandomAccessList a > RandomAccessList b > RandomAccessList c
 unzip :: RandomAccessList (a, b) > (RandomAccessList a, RandomAccessList b)
 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) 
View the end of a RandomAccessList
which is either empty or has
been constructed by head
and tail
.
Empty  An empty 
Cons a (RandomAccessList a) 

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?
length :: RandomAccessList a > IntSource
O(1). The number of elements contained in a RandomAccessList
.
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
?
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
.
uncons :: RandomAccessList a > (a, RandomAccessList a)Source
O(1). Retrieve both, head
and tail
of a RandomAccessList
.
view :: RandomAccessList a > View aSource
O(1). Examine a RandomAccessList
: Either it is Empty
or it has
a head
and a tail
(packed in Cons
).
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 length
of the first list. Appends the second
list to the first list.
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.
Miscellaneous
filter :: (a > Bool) > RandomAccessList a > RandomAccessList aSource
O(n). Remove all elements from a RandomAccessList
not fulfilling a
predicate.
partition :: (a > Bool) > RandomAccessList a > (RandomAccessList a, RandomAccessList a)Source
O(n). Split a RandomAccessList
into two: The elements in the first
fulfill the given prefix, the others don't.
zip :: RandomAccessList a > RandomAccessList b > RandomAccessList (a, b)Source
O(min(n, m)). Listlike zip
. This function is slightly faster
when called with two RandomAccessList
s of equal length
.
zipWith :: (a > b > c) > RandomAccessList a > RandomAccessList b > RandomAccessList cSource
O(min(n, m)). Listlike zipWith
. This function is slightly faster
when called with two RandomAccessList
s of equal length
.
unzip :: RandomAccessList (a, b) > (RandomAccessList a, RandomAccessList b)Source
O(n). Listlike Prelude.unzip
for RandomAccessList
s.
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
length
.