| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.RRBVector
Description
The Vector aa.
This module should be imported qualified, to avoid name clashes with the Prelude.
Performance
The worst case running time complexities are given, with \(n\) referring to the number of elements in the vector (or \(n_1\), \(n_2\), etc. for multiple vectors). Note that all logarithms are base 16, so the constant factor for \(O(\log n)\) operations is quite small.
Implementation
The implementation uses Relaxed-Radix-Balanced trees, as described by
- Nicolas Stucki, "Turning Relaxed Radix Balanced Vector from Theory into Practice for Scala Collections", January 2015.
Currently, a branching factor of 16 is used. The tree is strict in its spine, but lazy in its elements.
Synopsis
- data Vector a
- empty :: Vector a
- singleton :: a -> Vector a
- fromList :: [a] -> Vector a
- (<|) :: a -> Vector a -> Vector a
- (|>) :: Vector a -> a -> Vector a
- (><) :: Vector a -> Vector a -> Vector a
- viewl :: Vector a -> Maybe (a, Vector a)
- viewr :: Vector a -> Maybe (Vector a, a)
- lookup :: Int -> Vector a -> Maybe a
- index :: HasCallStack => Int -> Vector a -> a
- (!?) :: Vector a -> Int -> Maybe a
- (!) :: HasCallStack => Vector a -> Int -> a
- update :: Int -> a -> Vector a -> Vector a
- adjust :: Int -> (a -> a) -> Vector a -> Vector a
- adjust' :: Int -> (a -> a) -> Vector a -> Vector a
- take :: Int -> Vector a -> Vector a
- drop :: Int -> Vector a -> Vector a
- splitAt :: Int -> Vector a -> (Vector a, Vector a)
- insertAt :: Int -> a -> Vector a -> Vector a
- deleteAt :: Int -> Vector a -> Vector a
- module Data.Foldable.WithIndex
- module Data.Functor.WithIndex
- module Data.Traversable.WithIndex
- map :: (a -> b) -> Vector a -> Vector b
- reverse :: Vector a -> Vector a
- zip :: Vector a -> Vector b -> Vector (a, b)
- zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
- unzip :: Vector (a, b) -> (Vector a, Vector b)
Documentation
A vector.
The instances are based on those of Seqs, which are in turn based on those of lists.
Instances
Construction
singleton :: a -> Vector a Source #
\(O(1)\). A vector with a single element.
singleton x = fromList [x]
Concatenation
(<|) :: a -> Vector a -> Vector a infixr 5 Source #
\(O(\log n)\). Add an element to the left end of the vector.
>>>1 <| fromList [2, 3, 4]fromList [1,2,3,4]
(|>) :: Vector a -> a -> Vector a infixl 5 Source #
\(O(\log n)\). Add an element to the right end of the vector.
>>>fromList [1, 2, 3] |> 4fromList [1,2,3,4]
(><) :: Vector a -> Vector a -> Vector a infixr 5 Source #
\(O(\log \max(n_1, n_2))\). Concatenates two vectors.
>>>fromList [1, 2, 3] >< fromList [4, 5]fromList [1,2,3,4,5]
Deconstruction
viewl :: Vector a -> Maybe (a, Vector a) Source #
\(O(\log n)\). 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])
viewr :: Vector a -> Maybe (Vector a, a) Source #
\(O(\log n)\). 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)
Indexing
lookup :: Int -> Vector a -> Maybe a Source #
\(O(\log n)\). The element at the index or Nothing if the index is out of range.
index :: HasCallStack => Int -> Vector a -> a Source #
\(O(\log n)\). The element at the index. Calls error if the index is out of range.
update :: Int -> a -> Vector a -> Vector a Source #
\(O(\log n)\). Update the element at the index with a new element. If the index is out of range, the original vector is returned.
adjust :: Int -> (a -> a) -> Vector a -> Vector a Source #
\(O(\log n)\). 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 Source #
\(O(\log n)\). Like adjust, but the result of the function is forced.
take :: Int -> Vector a -> Vector a Source #
\(O(\log n)\). 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.
drop :: Int -> Vector a -> Vector a Source #
\(O(\log n)\). 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.
splitAt :: Int -> Vector a -> (Vector a, Vector a) Source #
\(O(\log n)\). Split the vector at the given index.
splitAt n v = (take n v, drop n v)
insertAt :: Int -> a -> Vector a -> Vector a Source #
\(O(\log n)\). Insert an element at the given index.
deleteAt :: Int -> Vector a -> Vector a Source #
\(O(\log n)\). Delete the element at the given index.
With Index
Reexported from indexed-traversable.
module Data.Foldable.WithIndex
module Data.Functor.WithIndex
module Data.Traversable.WithIndex
Transformations
map :: (a -> b) -> Vector a -> Vector b Source #
\(O(n)\). Apply the function to every element.
>>>map (+ 1) (fromList [1, 2, 3])fromList [2,3,4]
reverse :: Vector a -> Vector a Source #
\(O(n)\). Reverse the vector.
>>>reverse (fromList [1, 2, 3])fromList [3,2,1]
Zipping and unzipping
zip :: Vector a -> Vector b -> Vector (a, b) Source #
\(O(\min(n_1, n_2))\). Take two vectors and return a vector of corresponding pairs. If one input is longer, excess elements are discarded from the right end.
zip = zipWith (,)