rio-0.1.22.0: A standard library for Haskell

Safe Haskell | Safe-Inferred
Language | Haskell2010

RIO.Vector.Boxed.Partial

Contents

- Accessors
  - Indexing
  - Monadic indexing
  - Extracting subvectors
- Modifying vectors
  - Bulk updates
  - Accumulations
  - Permutations
- Folding
  - Specialised folds
  - Monadic folds
- Prefix sums (scans)

Description

Boxed `Vector` partial functions. Import as:

    import qualified RIO.Vector.Boxed.Partial as VB'

Synopsis

- (!) :: Vector a -> Int -> a
- head :: Vector a -> a
- last :: Vector a -> a
- indexM :: Monad m => Vector a -> Int -> m a
- headM :: Monad m => Vector a -> m a
- lastM :: Monad m => Vector a -> m a
- init :: Vector a -> Vector a
- tail :: Vector a -> Vector a
- (//) :: Vector a -> [(Int, a)] -> Vector a
- update :: Vector a -> Vector (Int, a) -> Vector a
- update_ :: Vector a -> Vector Int -> Vector a -> Vector a
- accum :: (a -> b -> a) -> Vector a -> [(Int, b)] -> Vector a
- accumulate :: (a -> b -> a) -> Vector a -> Vector (Int, b) -> Vector a
- accumulate_ :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
- backpermute :: Vector a -> Vector Int -> Vector a
- foldl1 :: (a -> a -> a) -> Vector a -> a
- foldl1' :: (a -> a -> a) -> Vector a -> a
- foldr1 :: (a -> a -> a) -> Vector a -> a
- foldr1' :: (a -> a -> a) -> Vector a -> a
- maximum :: Ord a => Vector a -> a
- maximumBy :: (a -> a -> Ordering) -> Vector a -> a
- minimum :: Ord a => Vector a -> a
- minimumBy :: (a -> a -> Ordering) -> Vector a -> a
- minIndex :: Ord a => Vector a -> Int
- minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
- maxIndex :: Ord a => Vector a -> Int
- maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
- fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a
- fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
- fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
- fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
- scanl1 :: (a -> a -> a) -> Vector a -> Vector a
- scanl1' :: (a -> a -> a) -> Vector a -> Vector a
- scanr1 :: (a -> a -> a) -> Vector a -> Vector a
- scanr1' :: (a -> a -> a) -> Vector a -> Vector a

# Accessors

## Indexing

(!) :: Vector a -> Int -> a Source #

O(1) Indexing.

head :: Vector a -> a Source #

O(1) First element.

last :: Vector a -> a Source #

O(1) Last element.

## Monadic indexing

indexM :: Monad m => Vector a -> Int -> m a Source #

O(1) Indexing in a monad.

The monad allows operations to be strict in the vector when necessary. Suppose vector copying is implemented like this:

    copy mv v = ... write mv i (v ! i) ...

For lazy vectors, `v ! i` would not be evaluated which means that `mv` would unnecessarily retain a reference to `v` in each element written.

With `indexM`, copying can be implemented like this instead:

    copy mv v = ... do
                      x <- indexM v i
                      write mv i x

Here, no references to `v` are retained because indexing (but not the element) is evaluated eagerly.

headM :: Monad m => Vector a -> m a Source #

O(1) First element of a vector in a monad. See `indexM` for an explanation of why this is useful.

lastM :: Monad m => Vector a -> m a Source #

O(1) Last element of a vector in a monad. See `indexM` for an explanation of why this is useful.

## Extracting subvectors

init :: Vector a -> Vector a Source #

O(1) Yield all but the last element without copying. The vector may not be empty.

tail :: Vector a -> Vector a Source #

O(1) Yield all but the first element without copying. The vector may not be empty.

# Modifying vectors

## Bulk updates

(//) Source #

Arguments

:: Vector a | initial vector (of length `m`)
-> [(Int, a)] | list of index/value pairs (of length `n`)
-> Vector a |

O(m+n) For each pair `(i,a)` from the list of index/value pairs, replace the vector element at position `i` by `a`.

    <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>

update Source #

Arguments

:: Vector a | initial vector (of length `m`)
-> Vector (Int, a) | vector of index/value pairs (of length `n`)
-> Vector a |

O(m+n) For each pair `(i,a)` from the vector of index/value pairs, replace the vector element at position `i` by `a`.

    update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>

update_ Source #

Arguments

:: Vector a | initial vector (of length `m`)
-> Vector Int | index vector (of length `n1`)
-> Vector a | value vector (of length `n2`)
-> Vector a |

O(m+min(n1,n2)) For each index `i` from the index vector and the corresponding value `a` from the value vector, replace the element of the initial vector at position `i` by `a`.

    update_ <5,9,2,7>  <2,0,2> <1,3,8> = <3,9,8,7>

The function `update` provides the same functionality and is usually more convenient.

    update_ xs is ys = update xs (zip is ys)

## Accumulations

accum Source #

Arguments

:: (a -> b -> a) | accumulating function `f`
-> Vector a | initial vector (of length `m`)
-> [(Int, b)] | list of index/value pairs (of length `n`)
-> Vector a |

O(m+n) For each pair `(i,b)` from the list, replace the vector element `a` at position `i` by `f a b`.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.accum (+) (V.fromList [1000,2000,3000]) [(2,4),(1,6),(0,3),(1,10)]
    [1003,2016,3004]

accumulate Source #

Arguments

:: (a -> b -> a) | accumulating function `f`
-> Vector a | initial vector (of length `m`)
-> Vector (Int, b) | vector of index/value pairs (of length `n`)
-> Vector a |

O(m+n) For each pair `(i,b)` from the vector of pairs, replace the vector element `a` at position `i` by `f a b`.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.accumulate (+) (V.fromList [1000,2000,3000]) (V.fromList [(2,4),(1,6),(0,3),(1,10)])
    [1003,2016,3004]

accumulate_ Source #

Arguments

:: (a -> b -> a) | accumulating function `f`
-> Vector a | initial vector (of length `m`)
-> Vector Int | index vector (of length `n1`)
-> Vector b | value vector (of length `n2`)
-> Vector a |

O(m+min(n1,n2)) For each index `i` from the index vector and the corresponding value `b` from the the value vector, replace the element of the initial vector at position `i` by `f a b`.

    accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>

The function `accumulate` provides the same functionality and is usually more convenient.

    accumulate_ f as is bs = accumulate f as (zip is bs)

## Permutations

backpermute :: Vector a -> Vector Int -> Vector a Source #

O(n) Yield the vector obtained by replacing each element `i` of the index vector by `xs`!`i`. This is equivalent to ``map` (xs`!`) is`, but is often much more efficient.

    backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>

# Folding

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

O(n) Left fold on non-empty vectors.

foldl1' :: (a -> a -> a) -> Vector a -> a Source #

O(n) Left fold on non-empty vectors with strict accumulator.

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

O(n) Right fold on non-empty vectors.

foldr1' :: (a -> a -> a) -> Vector a -> a Source #

O(n) Right fold on non-empty vectors with strict accumulator.

## Specialised folds

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

O(n) Yield the maximum element of the vector. The vector may not be empty. In case of a tie, the first occurrence wins.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.maximum $ V.fromList [2, 1]
    2
    >>> import Data.Semigroup
    >>> V.maximum $ V.fromList [Arg 1 'a', Arg 2 'b']
    Arg 2 'b'
    >>> V.maximum $ V.fromList [Arg 1 'a', Arg 1 'b']
    Arg 1 'a'

maximumBy :: (a -> a -> Ordering) -> Vector a -> a Source #

O(n) Yield the maximum element of the vector according to the given comparison function. The vector may not be empty. In case of a tie, the first occurrence wins. This behavior is different from `maximumBy` which returns the last tie.

#### Examples

Expand

    >>> import Data.Ord
    >>> import qualified Data.Vector as V
    >>> V.maximumBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')]
    (2,'a')
    >>> V.maximumBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]
    (1,'a')

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

O(n) Yield the minimum element of the vector. The vector may not be empty. In case of a tie, the first occurrence wins.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.minimum $ V.fromList [2, 1]
    1
    >>> import Data.Semigroup
    >>> V.minimum $ V.fromList [Arg 2 'a', Arg 1 'b']
    Arg 1 'b'
    >>> V.minimum $ V.fromList [Arg 1 'a', Arg 1 'b']
    Arg 1 'a'

minimumBy :: (a -> a -> Ordering) -> Vector a -> a Source #

O(n) Yield the minimum element of the vector according to the given comparison function. The vector may not be empty. In case of a tie, the first occurrence wins.

#### Examples

Expand

    >>> import Data.Ord
    >>> import qualified Data.Vector as V
    >>> V.minimumBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')]
    (1,'b')
    >>> V.minimumBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]
    (1,'a')

minIndex :: Ord a => Vector a -> Int Source #

O(n) Yield the index of the minimum element of the vector. The vector may not be empty.

minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int Source #

O(n) Yield the index of the minimum element of the vector according to the given comparison function. The vector may not be empty.

#### Examples

Expand

    >>> import Data.Ord
    >>> import qualified Data.Vector as V
    >>> V.minIndexBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')]
    1
    >>> V.minIndexBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]
    0

maxIndex :: Ord a => Vector a -> Int Source #

O(n) Yield the index of the maximum element of the vector. The vector may not be empty.

maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int Source #

O(n) Yield the index of the maximum element of the vector according to the given comparison function. The vector may not be empty. In case of a tie, the first occurrence wins.

#### Examples

Expand

    >>> import Data.Ord
    >>> import qualified Data.Vector as V
    >>> V.maxIndexBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')]
    0
    >>> V.maxIndexBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]
    0

## Monadic folds

fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a Source #

O(n) Monadic fold over non-empty vectors.

fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a Source #

O(n) Monadic fold over non-empty vectors with strict accumulator.

fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m () Source #

O(n) Monadic fold over non-empty vectors that discards the result.

fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m () Source #

O(n) Monadic fold over non-empty vectors with strict accumulator that discards the result.

# Prefix sums (scans)

scanl1 :: (a -> a -> a) -> Vector a -> Vector a Source #

O(n) Initial-value free left-to-right scan over a vector.

    scanl f <x1,...,xn> = <y1,...,yn>
      where y1 = x1
            yi = f y(i-1) xi

Note: Since 0.13, application of this to an empty vector no longer results in an error; instead it produces an empty vector.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.scanl1 min $ V.fromListN 5 [4,2,4,1,3]
    [4,2,2,1,1]
    >>> V.scanl1 max $ V.fromListN 5 [1,3,2,5,4]
    [1,3,3,5,5]
    >>> V.scanl1 min (V.empty :: V.Vector Int)
    []

scanl1' :: (a -> a -> a) -> Vector a -> Vector a Source #

O(n) Initial-value free left-to-right scan over a vector with a strict accumulator.

Note: Since 0.13, application of this to an empty vector no longer results in an error; instead it produces an empty vector.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.scanl1' min $ V.fromListN 5 [4,2,4,1,3]
    [4,2,2,1,1]
    >>> V.scanl1' max $ V.fromListN 5 [1,3,2,5,4]
    [1,3,3,5,5]
    >>> V.scanl1' min (V.empty :: V.Vector Int)
    []

scanr1 :: (a -> a -> a) -> Vector a -> Vector a Source #

O(n) Right-to-left, initial-value free scan over a vector.

Note: Since 0.13, application of this to an empty vector no longer results in an error; instead it produces an empty vector.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.scanr1 min $ V.fromListN 5 [3,1,4,2,4]
    [1,1,2,2,4]
    >>> V.scanr1 max $ V.fromListN 5 [4,5,2,3,1]
    [5,5,3,3,1]
    >>> V.scanr1 min (V.empty :: V.Vector Int)
    []

scanr1' :: (a -> a -> a) -> Vector a -> Vector a Source #

O(n) Right-to-left, initial-value free scan over a vector with a strict accumulator.

Note: Since 0.13, application of this to an empty vector no longer results in an error; instead it produces an empty vector.

#### Examples

Expand

    >>> import qualified Data.Vector as V
    >>> V.scanr1' min $ V.fromListN 5 [3,1,4,2,4]
    [1,1,2,2,4]
    >>> V.scanr1' max $ V.fromListN 5 [4,5,2,3,1]
    [5,5,3,3,1]
    >>> V.scanr1' min (V.empty :: V.Vector Int)
    []