Safe Haskell | None |
---|---|

Language | Haskell2010 |

Generic `Vector`

interface partial functions. Import as:

import qualified RIO.Vector.Partial as V'

## Synopsis

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

# Accessors

## Indexing

## Monadic indexing

indexM :: (Vector v a, Monad m) => v a -> Int -> m a #

*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
elements) is evaluated eagerly.

headM :: (Vector v a, Monad m) => v a -> m a #

*O(1)* First element of a vector in a monad. See `indexM`

for an
explanation of why this is useful.

lastM :: (Vector v a, Monad m) => v a -> m a #

*O(1)* Last element of a vector in a monad. See `indexM`

for an
explanation of why this is useful.

## Extracting subvectors

init :: Vector v a => v a -> v a #

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

tail :: Vector v a => v a -> v a #

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

# Modifying vectors

## Bulk updates

:: Vector v a | |

=> v a | initial vector (of length |

-> [(Int, a)] | list of index/value pairs (of length |

-> v a |

*O(m+n)* For each pair `(i,a)`

from the list, replace the vector
element at position `i`

by `a`

.

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

:: (Vector v a, Vector v (Int, a)) | |

=> v a | initial vector (of length |

-> v (Int, a) | vector of index/value pairs (of length |

-> v 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>

:: (Vector v a, Vector v Int) | |

=> v a | initial vector (of length |

-> v Int | index vector (of length |

-> v a | value vector (of length |

-> v 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>

This function is useful for instances of `Vector`

that cannot store pairs.
Otherwise, `update`

is probably more convenient.

update_ xs is ys =`update`

xs (`zip`

is ys)

## Accumulations

:: Vector v a | |

=> (a -> b -> a) | accumulating function |

-> v a | initial vector (of length |

-> [(Int, b)] | list of index/value pairs (of length |

-> v a |

*O(m+n)* For each pair `(i,b)`

from the list, replace the vector element
`a`

at position `i`

by `f a b`

.

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

:: (Vector v a, Vector v (Int, b)) | |

=> (a -> b -> a) | accumulating function |

-> v a | initial vector (of length |

-> v (Int, b) | vector of index/value pairs (of length |

-> v 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`

.

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

:: (Vector v a, Vector v Int, Vector v b) | |

=> (a -> b -> a) | accumulating function |

-> v a | initial vector (of length |

-> v Int | index vector (of length |

-> v b | value vector (of length |

-> v 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>

This function is useful for instances of `Vector`

that cannot store pairs.
Otherwise, `accumulate`

is probably more convenient:

accumulate_ f as is bs =`accumulate`

f as (`zip`

is bs)

## Permutations

# Folding

foldl1' :: Vector v a => (a -> a -> a) -> v a -> a #

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

foldr1' :: Vector v a => (a -> a -> a) -> v a -> a #

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

## Specialised folds

maximum :: (Vector v a, Ord a) => v a -> a #

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

maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a #

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

minimum :: (Vector v a, Ord a) => v a -> a #

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

minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a #

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

minIndex :: (Vector v a, Ord a) => v a -> Int #

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

minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int #

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

maxIndex :: (Vector v a, Ord a) => v a -> Int #

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

maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int #

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

## Monadic folds

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

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

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

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

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

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

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

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

# Prefix sums (scans)

scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a #

*O(n)* Scan over a non-empty vector

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

scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a #

*O(n)* Scan over a non-empty vector with a strict accumulator