-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Efficient RRB-Vectors -- -- An RRB-Vector is an efficient sequence data structure. It supports -- fast indexing, iteration, concatenation and splitting. -- --

Comparison with Data.Sequence

-- -- Seq a is a container with a very similar API. RRB-Vectors are -- generally faster for indexing and iteration, while sequences are -- faster for access to the front/back (amortized <math>). @package rrb-vector @version 0.2.2.1 -- | This module contains some debug utilities. It should only be used for -- debugging/testing purposes. module Data.RRBVector.Internal.Debug -- | <math>. Show the underlying tree of a vector. showTree :: Show a => Vector a -> String -- | <math>. Create a new unbalanced vector from a list. -- -- Note that it is not possbible to create an invalid Vector with -- this function. fromListUnbalanced :: [a] -> Vector a pattern Empty :: Vector a pattern Root :: Int -> Shift -> Tree a -> Vector a data Tree a type Shift = Int pattern Balanced :: Array (Tree a) -> Tree a pattern Unbalanced :: Array (Tree a) -> PrimArray Int -> Tree a pattern Leaf :: Array a -> Tree a -- | Structural invariants a vector is expected to hold. data Invariant -- | Check tree invariants. Returns Left on finding a violated -- invariant. valid :: Vector a -> Either Invariant () instance GHC.Show.Show Data.RRBVector.Internal.Debug.Invariant -- | The Vector a type is an RRB-Vector of elements of type -- a. -- -- This module should be imported qualified, to avoid name clashes with -- the Prelude. -- --

Performance

-- -- The worst case running time complexities are given, with <math> -- referring to the number of elements in the vector (or <math>, -- <math>, etc. for multiple vectors). Note that all logarithms are -- base 16, so the constant factor for <math> operations is quite -- small. -- --

Implementation

-- -- The implementation uses Relaxed-Radix-Balanced trees, as described by -- -- -- -- Currently, a branching factor of 16 is used. The tree is strict in its -- spine, but lazy in its elements. module Data.RRBVector -- | A vector. -- -- The instances are based on those of Seqs, which are in turn -- based on those of lists. data Vector a -- | <math>. The empty vector. -- -- 
--   empty = fromList []
--
empty :: Vector a -- | <math>. A vector with a single element. -- -- 
--   singleton x = fromList [x]
--
singleton :: a -> Vector a -- | <math>. Create a new vector from a list. fromList :: [a] -> Vector a -- | <math>. replicate n x creates a vector of length -- n with every element set to x. -- -- 
--   >>> replicate 5 42
--   fromList [42,42,42,42,42]
--
replicate :: Int -> a -> Vector a -- | <math>. Add an element to the left end of the vector. -- -- 
--   >>> 1 <| fromList [2, 3, 4]
--   fromList [1,2,3,4]
--
(<|) :: a -> Vector a -> Vector a infixr 5 <| -- | <math>. Add an element to the right end of the vector. -- -- 
--   >>> fromList [1, 2, 3] |> 4
--   fromList [1,2,3,4]
--
(|>) :: Vector a -> a -> Vector a infixl 5 |> -- | <math>. Concatenates two vectors. -- -- 
--   >>> fromList [1, 2, 3] >< fromList [4, 5]
--   fromList [1,2,3,4,5]
--
(><) :: Vector a -> Vector a -> Vector a infixr 5 >< -- | <math>. The first element and the vector without the first -- element, or Nothing if the vector is empty. -- -- 
--   >>> viewl (fromList [1, 2, 3])
--   Just (1,fromList [2,3])
--
viewl :: Vector a -> Maybe (a, Vector a) -- | <math>. The vector without the last element and the last -- element, or Nothing if the vector is empty. -- -- 
--   >>> viewr (fromList [1, 2, 3])
--   Just (fromList [1,2],3)
--
viewr :: Vector a -> Maybe (Vector a, a) -- | <math>. The element at the index or Nothing if the index -- is out of range. lookup :: Int -> Vector a -> Maybe a -- | <math>. The element at the index. Calls error if the -- index is out of range. index :: HasCallStack => Int -> Vector a -> a -- | <math>. A flipped version of lookup. (!?) :: Vector a -> Int -> Maybe a -- | <math>. A flipped version of index. (!) :: HasCallStack => Vector a -> Int -> a -- | <math>. Update the element at the index with a new element. If -- the index is out of range, the original vector is returned. update :: Int -> a -> Vector a -> Vector a -- | <math>. Adjust the element at the index by applying the function -- to it. If the index is out of range, the original vector is returned. adjust :: Int -> (a -> a) -> Vector a -> Vector a -- | <math>. Like adjust, but the result of the function is -- forced. adjust' :: Int -> (a -> a) -> Vector a -> Vector a -- | <math>. The first i elements of the vector. If -- i is negative, the empty vector is returned. If the vector -- contains less than i elements, the whole vector is returned. take :: Int -> Vector a -> Vector a -- | <math>. The vector without the first i elements. If -- i is negative, the whole vector is returned. If the vector -- contains less than i elements, the empty vector is returned. drop :: Int -> Vector a -> Vector a -- | <math>. Split the vector at the given index. -- -- 
--   splitAt n v = (take n v, drop n v)
--
splitAt :: Int -> Vector a -> (Vector a, Vector a) -- | <math>. Insert an element at the given index, shifting the rest -- of the vector over. If the index is negative, add the element to the -- left end of the vector. If the index is bigger than or equal to the -- length of the vector, add the element to the right end of the vector. insertAt :: Int -> a -> Vector a -> Vector a -- | <math>. Delete the element at the given index. If the index is -- out of range, return the original vector. deleteAt :: Int -> Vector a -> Vector a -- | <math>. Find the first index from the left that satisfies the -- predicate. findIndexL :: (a -> Bool) -> Vector a -> Maybe Int -- | <math>. Find the first index from the right that satisfies the -- predicate. findIndexR :: (a -> Bool) -> Vector a -> Maybe Int -- | <math>. Find the indices that satisfy the predicate, starting -- from the left. findIndicesL :: (a -> Bool) -> Vector a -> [Int] -- | <math>. Find the indices that satisfy the predicate, starting -- from the right. findIndicesR :: (a -> Bool) -> Vector a -> [Int] -- | <math>. Apply the function to every element. -- -- 
--   >>> map (+ 1) (fromList [1, 2, 3])
--   fromList [2,3,4]
--
map :: (a -> b) -> Vector a -> Vector b -- | <math>. Like map, but the results of the function are -- forced. map' :: (a -> b) -> Vector a -> Vector b -- | <math>. Reverse the vector. -- -- 
--   >>> reverse (fromList [1, 2, 3])
--   fromList [3,2,1]
--
reverse :: Vector a -> Vector a -- | <math>. Take two vectors and return a vector of corresponding -- pairs. If one input is longer, excess elements are discarded from the -- right end. zip :: Vector a -> Vector b -> Vector (a, b) -- | <math>. zipWith generalizes zip by zipping with -- the function. zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c -- | <math>. Unzip a vector of pairs. -- -- 
--   >>> unzip (fromList [(1, "a"), (2, "b"), (3, "c")])
--   (fromList [1,2,3],fromList ["a","b","c"])
--
unzip :: Vector (a, b) -> (Vector a, Vector b) -- | <math>. Unzip a vector with a function. -- -- 
--   unzipWith f = unzip . map f
--
unzipWith :: (a -> (b, c)) -> Vector a -> (Vector b, Vector c) -- | <math>. Sort the vector in ascending order. The sort is stable, -- meaning the order of equal elements is preserved. sort :: Ord a => Vector a -> Vector a -- | <math>. Sort the vector in ascending order according to the -- specified comparison function. The sort is stable, meaning the order -- of equal elements is preserved. sortBy :: (a -> a -> Ordering) -> Vector a -> Vector a -- | <math>. Sort the vector in ascending order by comparing the -- results of applying the key function to each element. The sort is -- stable, meaning the order of equal elements is preserved. -- sortOn f is equivalent to sortBy -- (comparing f), but only evaluates f once for each -- element. sortOn :: Ord b => (a -> b) -> Vector a -> Vector a