-- 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.0 -- | This is an internal module. -- -- It provides a thin wrapper over Data.Primitive.SmallArray with -- <math> slicing. -- -- Warning: No bound checks are performed! module Data.RRBVector.Internal.Array data Array a data MutableArray s a ifoldrStep :: Int -> (a -> Int) -> (Int -> a -> b -> b) -> b -> Array a -> b ifoldlStep :: Int -> (a -> Int) -> (Int -> b -> a -> b) -> b -> Array a -> b ifoldrStep' :: Int -> (a -> Int) -> (Int -> a -> b -> b) -> b -> Array a -> b ifoldlStep' :: Int -> (a -> Int) -> (Int -> b -> a -> b) -> b -> Array a -> b empty :: Array a singleton :: a -> Array a from2 :: a -> a -> Array a wrap :: SmallArray a -> Array a replicate :: Int -> a -> Array a replicateSnoc :: Int -> a -> a -> Array a index :: Array a -> Int -> a head :: Array a -> a last :: Array a -> a update :: Array a -> Int -> a -> Array a adjust :: Array a -> Int -> (a -> a) -> Array a adjust' :: Array a -> Int -> (a -> a) -> Array a take :: Array a -> Int -> Array a drop :: Array a -> Int -> Array a splitAt :: Array a -> Int -> (Array a, Array a) snoc :: Array a -> a -> Array a cons :: Array a -> a -> Array a (++) :: Array a -> Array a -> Array a map :: (a -> b) -> Array a -> Array b map' :: (a -> b) -> Array a -> Array b imapStep :: Int -> (a -> Int) -> (Int -> a -> b) -> Array a -> Array b imapStep' :: Int -> (a -> Int) -> (Int -> a -> b) -> Array a -> Array b unzipWith :: (a -> (b, c)) -> Array a -> (Array b, Array c) traverse :: Applicative f => (a -> f b) -> Array a -> f (Array b) traverse' :: Applicative f => (a -> f b) -> Array a -> f (Array b) itraverseStep :: Applicative f => Int -> (a -> Int) -> (Int -> a -> f b) -> Array a -> f (Array b) itraverseStep' :: Applicative f => Int -> (a -> Int) -> (Int -> a -> f b) -> Array a -> f (Array b) new :: Int -> ST s (MutableArray s a) read :: MutableArray s a -> Int -> ST s a write :: MutableArray s a -> Int -> a -> ST s () freeze :: MutableArray s a -> Int -> Int -> ST s (Array a) thaw :: Array a -> Int -> Int -> ST s (MutableArray s a) instance Data.Foldable.Foldable Data.RRBVector.Internal.Array.Array instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RRBVector.Internal.Array.Array a) -- | This is an internal module. -- -- A Buffer is an array with a fixed capacity, used to build up -- Arrays. It is used in the implementation of fromList and -- ><. module Data.RRBVector.Internal.Buffer -- | A mutable array buffer with a fixed capacity. data Buffer s a -- | <math>. Create a new empty buffer with the given capacity. new :: Int -> ST s (Buffer s a) -- | <math>. Push a new element onto the buffer. The size of the -- buffer must not exceed the capacity, but this is not checked. push :: Buffer s a -> a -> ST s () -- | <math>. Freeze the content of the buffer and return it. This -- resets the buffer so that it is empty. get :: Buffer s a -> ST s (Array a) -- | <math>. Return the current size of the buffer. size :: Buffer s a -> ST s Int module Data.RRBVector.Internal -- | A vector. -- -- The instances are based on those of Seqs, which are in turn -- based on those of lists. data Vector a Empty :: Vector a Root :: !Int -> !Shift -> !Tree a -> Vector a data Tree a Balanced :: {-# UNPACK #-} !Array (Tree a) -> Tree a Unbalanced :: {-# UNPACK #-} !Array (Tree a) -> !PrimArray Int -> Tree a Leaf :: {-# UNPACK #-} !Array a -> Tree a type Shift = Int blockShift :: Shift blockSize :: Int treeSize :: Shift -> Tree a -> Int computeSizes :: Shift -> Array (Tree a) -> Tree a up :: Shift -> Shift down :: Shift -> Shift -- | <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>. Slice the vector between the two indices (inclusive). slice :: (Int, 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) instance Data.Functor.Classes.Show1 Data.RRBVector.Internal.Vector instance GHC.Show.Show a => GHC.Show.Show (Data.RRBVector.Internal.Vector a) instance Data.Functor.Classes.Read1 Data.RRBVector.Internal.Vector instance GHC.Read.Read a => GHC.Read.Read (Data.RRBVector.Internal.Vector a) instance Data.Functor.Classes.Eq1 Data.RRBVector.Internal.Vector instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.RRBVector.Internal.Vector a) instance Data.Functor.Classes.Ord1 Data.RRBVector.Internal.Vector instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.RRBVector.Internal.Vector a) instance GHC.Base.Semigroup (Data.RRBVector.Internal.Vector a) instance GHC.Base.Monoid (Data.RRBVector.Internal.Vector a) instance Data.Foldable.Foldable Data.RRBVector.Internal.Vector instance WithIndex.FoldableWithIndex GHC.Types.Int Data.RRBVector.Internal.Vector instance GHC.Base.Functor Data.RRBVector.Internal.Vector instance WithIndex.FunctorWithIndex GHC.Types.Int Data.RRBVector.Internal.Vector instance Data.Traversable.Traversable Data.RRBVector.Internal.Vector instance WithIndex.TraversableWithIndex GHC.Types.Int Data.RRBVector.Internal.Vector instance GHC.Base.Applicative Data.RRBVector.Internal.Vector instance GHC.Base.Monad Data.RRBVector.Internal.Vector instance GHC.Base.Alternative Data.RRBVector.Internal.Vector instance GHC.Base.MonadPlus Data.RRBVector.Internal.Vector instance Control.Monad.Fail.MonadFail Data.RRBVector.Internal.Vector instance Control.Monad.Fix.MonadFix Data.RRBVector.Internal.Vector instance Control.Monad.Zip.MonadZip Data.RRBVector.Internal.Vector instance GHC.IsList.IsList (Data.RRBVector.Internal.Vector a) instance (a GHC.Types.~ GHC.Types.Char) => Data.String.IsString (Data.RRBVector.Internal.Vector a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RRBVector.Internal.Vector a) instance Control.DeepSeq.NFData1 Data.RRBVector.Internal.Vector -- | 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>. Slice the vector between the two indices (inclusive). slice :: (Int, 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