-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Random-access lists in Haskell
--
-- A purely functional random-access list implementation using skew
-- binary number representation. These lists offer indexed random-access
-- in logarithmic time while still providing typical list functionality
-- (head, tail, cons) in constant time. See "Purely Functional Data
-- Structures" by Chris Okasaki.
@package random-access-list
@version 0.2
-- | 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.
--
-- RandomAccessLists are finite lists providing 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.
module Data.RandomAccessList
-- | Random-access lists allowing O(1) list operations and O(log
-- n) indexed access.
data RandomAccessList a
-- | View the end of a RandomAccessList which is either empty or has
-- been constructed by head and tail.
data View a
-- | An empty RandomAccessList.
Empty :: View a
-- | head and tail of a non-empty RandomAccessList.
Cons :: a -> (RandomAccessList a) -> View a
-- | O(1). Builds an empty RandomAccessList.
empty :: RandomAccessList a
-- | O(1). Builds a singleton RandomAccessList.
singleton :: a -> RandomAccessList a
-- | O(n). replicate n x constructs a
-- RandomAccessList that contains the same element x
-- n times.
replicate :: Int -> a -> RandomAccessList a
-- | O(1). Is the RandomAccessList empty?
null :: RandomAccessList a -> Bool
-- | O(1). Is the RandomAccessList empty?
isEmpty :: RandomAccessList a -> Bool
-- | O(1). The number of elements contained in a
-- RandomAccessList.
length :: RandomAccessList a -> Int
-- | O(1). The number of elements contained in a
-- RandomAccessList.
size :: RandomAccessList a -> Int
-- | O(n). Is the given element a member of the
-- RandomAccessList?
member :: Eq a => a -> RandomAccessList a -> Bool
-- | O(n). Find the index of a given element.
index :: Eq a => a -> RandomAccessList a -> Maybe Int
-- | O(1). Returns the head of a RandomAccessList.
head :: RandomAccessList a -> a
-- | O(1). Retrieve the tail of a RandomAccessList.
tail :: RandomAccessList a -> RandomAccessList a
-- | O(1). Retrieve both, head and tail of a
-- RandomAccessList.
uncons :: RandomAccessList a -> (a, RandomAccessList a)
-- | O(1). Examine a RandomAccessList: Either it is
-- Empty or it has a head and a tail (packed in
-- Cons).
view :: RandomAccessList a -> View a
-- | O(1). Prepend an element to the RandomAccessList.
cons :: a -> RandomAccessList a -> RandomAccessList a
-- | O(n) where n is the length of the first list.
-- Appends the second list to the first list.
append :: RandomAccessList a -> RandomAccessList a -> RandomAccessList a
-- | O(log n). Retrieve the ith element of the list. Unless
-- 0 <= i < n, an error is raised.
lookup :: Int -> RandomAccessList a -> a
-- | O(log n). Set the ith element of the list. Unless 0
-- <= i < n, an error is raised.
update :: Int -> a -> 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.
adjust :: (a -> a) -> Int -> RandomAccessList a -> RandomAccessList a
-- | 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.
adjustLookup :: (a -> a) -> Int -> RandomAccessList a -> (a, RandomAccessList a)
-- | O(n). Remove all elements from a RandomAccessList not
-- fulfilling a predicate.
filter :: (a -> Bool) -> RandomAccessList a -> RandomAccessList a
-- | O(n). Split a RandomAccessList into two: The elements in
-- the first fulfill the given prefix, the others don't.
partition :: (a -> Bool) -> RandomAccessList a -> (RandomAccessList a, RandomAccessList a)
-- | O(min(n, m)). List-like zip. This function is slightly
-- faster when called with two RandomAccessLists of equal
-- length.
zip :: RandomAccessList a -> RandomAccessList b -> RandomAccessList (a, b)
-- | O(min(n, m)). List-like zipWith. This function is
-- slightly faster when called with two RandomAccessLists of equal
-- length.
zipWith :: (a -> b -> c) -> RandomAccessList a -> RandomAccessList b -> RandomAccessList c
-- | O(n). List-like Prelude.unzip for
-- RandomAccessLists.
unzip :: RandomAccessList (a, b) -> (RandomAccessList a, RandomAccessList b)
-- | O(n). Build a RandomAccessList from a list.
fromList :: [a] -> RandomAccessList a
-- | O(n). Convert a RandomAccessList to a list.
toList :: RandomAccessList a -> [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.
toIndexedList :: RandomAccessList a -> [(Int, a)]
-- | O(n). Build a Map from a RandomAccessList. The
-- keys in the Map are the indices of the elements in the
-- RandomAccessList.
toMap :: RandomAccessList a -> Map Int a
-- | O(n). Build an IntMap from a RandomAccessList.
-- The keys in the IntMap are the indices of the elements in the
-- RandomAccessList.
toIntMap :: RandomAccessList a -> IntMap a
-- | O(n). Given an IArray, generate a
-- RandomAccessList. The elements' order will be preserved.
fromArray :: (IArray a e, Ix i) => a i e -> RandomAccessList e
-- | O(n). Build an IArray from the RandomAccessList.
-- It will have an index range from [0 .. n-1], where n
-- is the RandomAccessLists length.
toArray :: IArray a e => RandomAccessList e -> a Int e
instance Show a => Show (View a)
instance Read a => Read (View a)
instance Eq a => Eq (View a)
instance Ord a => Ord (View a)
instance Eq a => Eq (CBTree a)
instance Foldable View
instance Functor View
instance Functor CBTree
instance Foldable RandomAccessList
instance Functor RandomAccessList
instance Monoid (RandomAccessList a)
instance Ord a => Ord (RandomAccessList a)
instance Eq a => Eq (RandomAccessList a)
instance Read a => Read (RandomAccessList a)
instance Show a => Show (RandomAccessList a)