Data.RRBVector

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 \(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.

Documentation

data Vector a

A vector.

The instances are based on those of Seqs, which are in turn based on those of lists.

Instances

MonadFail Vector

Defined in Data.RRBVector.Internal

Methods

fail :: String -> Vector a

MonadFix Vector

Defined in Data.RRBVector.Internal

Methods

mfix :: (a -> Vector a) -> Vector a

MonadZip Vector

Defined in Data.RRBVector.Internal

Methods

mzip :: Vector a -> Vector b -> Vector (a, b)

mzipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c

munzip :: Vector (a, b) -> (Vector a, Vector b)

Foldable Vector

Defined in Data.RRBVector.Internal

Methods

fold :: Monoid m => Vector m -> m

foldMap :: Monoid m => (a -> m) -> Vector a -> m

foldMap' :: Monoid m => (a -> m) -> Vector a -> m

foldr :: (a -> b -> b) -> b -> Vector a -> b

foldr' :: (a -> b -> b) -> b -> Vector a -> b

foldl :: (b -> a -> b) -> b -> Vector a -> b

foldl' :: (b -> a -> b) -> b -> Vector a -> b

foldr1 :: (a -> a -> a) -> Vector a -> a

foldl1 :: (a -> a -> a) -> Vector a -> a

toList :: Vector a -> [a]

null :: Vector a -> Bool

length :: Vector a -> Int

elem :: Eq a => a -> Vector a -> Bool

maximum :: Ord a => Vector a -> a

minimum :: Ord a => Vector a -> a

sum :: Num a => Vector a -> a

product :: Num a => Vector a -> a

Eq1 Vector

Defined in Data.RRBVector.Internal

Methods

liftEq :: (a -> b -> Bool) -> Vector a -> Vector b -> Bool

Ord1 Vector

Defined in Data.RRBVector.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> Vector a -> Vector b -> Ordering

Read1 Vector

Defined in Data.RRBVector.Internal

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Vector a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Vector a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Vector a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Vector a]

Show1 Vector

Defined in Data.RRBVector.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Vector a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Vector a] -> ShowS

Traversable Vector

Defined in Data.RRBVector.Internal

Methods

traverse :: Applicative f => (a -> f b) -> Vector a -> f (Vector b)

sequenceA :: Applicative f => Vector (f a) -> f (Vector a)

mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)

sequence :: Monad m => Vector (m a) -> m (Vector a)

Alternative Vector

Defined in Data.RRBVector.Internal

Methods

empty :: Vector a

(<|>) :: Vector a -> Vector a -> Vector a

some :: Vector a -> Vector [a]

many :: Vector a -> Vector [a]

Applicative Vector

Defined in Data.RRBVector.Internal

Methods

pure :: a -> Vector a

(<*>) :: Vector (a -> b) -> Vector a -> Vector b

liftA2 :: (a -> b -> c) -> Vector a -> Vector b -> Vector c

(*>) :: Vector a -> Vector b -> Vector b

(<*) :: Vector a -> Vector b -> Vector a

Functor Vector

Defined in Data.RRBVector.Internal

Methods

fmap :: (a -> b) -> Vector a -> Vector b

(<$) :: a -> Vector b -> Vector a

Monad Vector

Defined in Data.RRBVector.Internal

Methods

(>>=) :: Vector a -> (a -> Vector b) -> Vector b

(>>) :: Vector a -> Vector b -> Vector b

return :: a -> Vector a

MonadPlus Vector

Defined in Data.RRBVector.Internal

Methods

mzero :: Vector a

mplus :: Vector a -> Vector a -> Vector a

NFData1 Vector

Defined in Data.RRBVector.Internal

Methods

liftRnf :: (a -> ()) -> Vector a -> ()

FoldableWithIndex Int Vector

Defined in Data.RRBVector.Internal

Methods

ifoldMap :: Monoid m => (Int -> a -> m) -> Vector a -> m

ifoldMap' :: Monoid m => (Int -> a -> m) -> Vector a -> m

ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b

ifoldl :: (Int -> b -> a -> b) -> b -> Vector a -> b

ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b

ifoldl' :: (Int -> b -> a -> b) -> b -> Vector a -> b

FunctorWithIndex Int Vector

Defined in Data.RRBVector.Internal

Methods

imap :: (Int -> a -> b) -> Vector a -> Vector b

TraversableWithIndex Int Vector

Defined in Data.RRBVector.Internal

Methods

itraverse :: Applicative f => (Int -> a -> f b) -> Vector a -> f (Vector b)

a ~ Char => IsString (Vector a)

Defined in Data.RRBVector.Internal

Methods

fromString :: String -> Vector a

Monoid (Vector a)

Defined in Data.RRBVector.Internal

Methods

mempty :: Vector a

mappend :: Vector a -> Vector a -> Vector a

mconcat :: [Vector a] -> Vector a

Semigroup (Vector a)

Defined in Data.RRBVector.Internal

Methods

(<>) :: Vector a -> Vector a -> Vector a

sconcat :: NonEmpty (Vector a) -> Vector a

stimes :: Integral b => b -> Vector a -> Vector a

IsList (Vector a)

Defined in Data.RRBVector.Internal

Associated Types

type Item (Vector a)

Methods

fromList :: [Item (Vector a)] -> Vector a

fromListN :: Int -> [Item (Vector a)] -> Vector a

toList :: Vector a -> [Item (Vector a)]

Read a => Read (Vector a)

Defined in Data.RRBVector.Internal

Methods

readsPrec :: Int -> ReadS (Vector a)

readList :: ReadS [Vector a]

readPrec :: ReadPrec (Vector a)

readListPrec :: ReadPrec [Vector a]

Show a => Show (Vector a)

Defined in Data.RRBVector.Internal

Methods

showsPrec :: Int -> Vector a -> ShowS

show :: Vector a -> String

showList :: [Vector a] -> ShowS

NFData a => NFData (Vector a)

Defined in Data.RRBVector.Internal

Methods

rnf :: Vector a -> ()

Eq a => Eq (Vector a)

Defined in Data.RRBVector.Internal

Methods

(==) :: Vector a -> Vector a -> Bool

(/=) :: Vector a -> Vector a -> Bool

Ord a => Ord (Vector a)

Defined in Data.RRBVector.Internal

Methods

compare :: Vector a -> Vector a -> Ordering

(<) :: Vector a -> Vector a -> Bool

(<=) :: Vector a -> Vector a -> Bool

(>) :: Vector a -> Vector a -> Bool

(>=) :: Vector a -> Vector a -> Bool

max :: Vector a -> Vector a -> Vector a

min :: Vector a -> Vector a -> Vector a

type Item (Vector a)

Defined in Data.RRBVector.Internal

type Item (Vector a) = a

Construction

empty :: Vector a

\(O(1)\). The empty vector.

empty = fromList []

singleton :: a -> Vector a

\(O(1)\). A vector with a single element.

singleton x = fromList [x]

fromList :: [a] -> Vector a

\(O(n)\). Create a new vector from a list.

replicate :: Int -> a -> Vector a

\(O(\log n)\). replicate n x creates a vector of length n with every element set to x.

>>> replicate 5 42
fromList [42,42,42,42,42]

Since: 0.1.1.0

Concatenation

(<|) :: a -> Vector a -> Vector a infixr 5

\(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

\(O(\log n)\). Add an element to the right end of the vector.

>>> fromList [1, 2, 3] |> 4
fromList [1,2,3,4]

(><) :: Vector a -> Vector a -> Vector a infixr 5

\(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)

\(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)

\(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

\(O(\log n)\). The element at the index or Nothing if the index is out of range.

index :: HasCallStack => Int -> Vector a -> a

\(O(\log n)\). The element at the index. Calls error if the index is out of range.

(!?) :: Vector a -> Int -> Maybe a

\(O(\log n)\). A flipped version of lookup.

(!) :: HasCallStack => Vector a -> Int -> a

\(O(\log n)\). A flipped version of index.

update :: Int -> a -> Vector a -> Vector a

\(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

\(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

\(O(\log n)\). Like adjust, but the result of the function is forced.

take :: Int -> Vector a -> Vector a

\(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

\(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)

\(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

\(O(\log n)\). 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.

deleteAt :: Int -> Vector a -> Vector a

\(O(\log n)\). Delete the element at the given index. If the index is out of range, return the original vector.

findIndexL :: (a -> Bool) -> Vector a -> Maybe Int

\(O(n)\). Find the first index from the left that satisfies the predicate.

Since: 0.2.1.0

findIndexR :: (a -> Bool) -> Vector a -> Maybe Int

\(O(n)\). Find the first index from the right that satisfies the predicate.

Since: 0.2.1.0

findIndicesL :: (a -> Bool) -> Vector a -> [Int]

\(O(n)\). Find the indices that satisfy the predicate, starting from the left.

Since: 0.2.1.0

findIndicesR :: (a -> Bool) -> Vector a -> [Int]

\(O(n)\). Find the indices that satisfy the predicate, starting from the right.

Since: 0.2.1.0

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

\(O(n)\). Apply the function to every element.

>>> map (+ 1) (fromList [1, 2, 3])
fromList [2,3,4]

map' :: (a -> b) -> Vector a -> Vector b

\(O(n)\). Like map, but the results of the function are forced.

Since: 0.2.0.0

reverse :: Vector a -> Vector a

\(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)

\(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.

zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c

\(O(\min(n_1, n_2))\). zipWith generalizes zip by zipping with the function.

unzip :: Vector (a, b) -> (Vector a, Vector b)

\(O(n)\). Unzip a vector of pairs.

>>> unzip (fromList [(1, "a"), (2, "b"), (3, "c")])
(fromList [1,2,3],fromList ["a","b","c"])

unzipWith :: (a -> (b, c)) -> Vector a -> (Vector b, Vector c)

\(O(n)\). Unzip a vector with a function.

unzipWith f = unzip . map f

Since: 0.2.0.0

Sorting

Currently implemented using samsort.

sort :: Ord a => Vector a -> Vector a

\(O(n \log n)\). Sort the vector in ascending order. The sort is stable, meaning the order of equal elements is preserved.

Since: 0.2.2.0

sortBy :: (a -> a -> Ordering) -> Vector a -> Vector a

\(O(n \log n)\). Sort the vector in ascending order according to the specified comparison function. The sort is stable, meaning the order of equal elements is preserved.

Since: 0.2.2.0

sortOn :: Ord b => (a -> b) -> Vector a -> Vector a

\(O(n \log n)\). 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.

Since: 0.2.2.0