Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Vector

Contents

Sort functions
Index compression
Vector Utilities
- Monadic scanl
Queries

Description

Miscellaneous vector functions. These functions are not the fastest implementations, but fills in some lacking features.

Since: 1.2.2.0

Synopsis

argsort :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int
compress :: Vector Int -> (Vector Int, Vector Int)
iconcatMap :: (HasCallStack, Vector v a, Vector v b) => (Int -> a -> v b) -> v a -> v b
concatMapM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> m (v b)) -> v a -> m (v b)
iconcatMapM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (Int -> a -> m (v b)) -> v a -> m (v b)
mapAccumL :: forall v s a b. (HasCallStack, Vector v a, Vector v b) => (s -> a -> (s, b)) -> s -> v a -> (s, v b)
chunks :: Vector v a => Int -> v a -> Vector (v a)
prescanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
prescanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
postscanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
postscanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
scanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
scanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
scanl1M :: (HasCallStack, Monad m, Vector v a) => (a -> a -> m a) -> v a -> m (v a)
scanl1M' :: (HasCallStack, Monad m, Vector v a) => (a -> a -> m a) -> v a -> m (v a)
maxRangeSum :: (Vector v a, Ord a, Num a) => v a -> a
minRangeSum :: (Vector v a, Ord a, Num a) => v a -> a
slideMinIndices :: HasCallStack => Int -> Vector Int -> Vector Int
slideMaxIndices :: HasCallStack => Int -> Vector Int -> Vector Int

Sort functions

argsort :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int Source #

\(O(n \log n)\) Returns indices of the vector elements, stably sorted by their value.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.argsort $ VU.fromList @Int [0, 1, 0, 1, 0]
[0,2,4,1,3]

Since: 1.2.3.0

Index compression

compress :: Vector Int -> (Vector Int, Vector Int) Source #

\(O(n \log n)\) One dimensional index compression: xs -> (nubSortXs, xs')

Example

>>> import AtCoder.Extra.Bisect (lowerBound)
>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> let xs = VU.fromList [0, 20, 40, 10, 30]
>>> let (dict, xs') = EV.compress xs
>>> xs'
[0,2,4,1,3]
>>> lowerBound dict 10
1

Since: 1.5.1.0

Vector Utilities

iconcatMap :: (HasCallStack, Vector v a, Vector v b) => (Int -> a -> v b) -> v a -> v b Source #

Maps each element to a vector and concatenate the results.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.iconcatMap (\i x -> VU.fromList [i + x, i + x]) $ VU.replicate @Int 3 0
[0,0,1,1,2,2]

Since: 1.5.1.0

concatMapM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> m (v b)) -> v a -> m (v b) Source #

Maps each element to a vector and concatenate the results.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.iconcatMap (\x -> pure (VU.fromList [x, x])) $ VU.generate @Int 3 id
[0,0,1,1,2,2]

Since: 1.5.1.0

iconcatMapM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (Int -> a -> m (v b)) -> v a -> m (v b) Source #

Maps each element to a vector and concatenate the results.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.iconcatMapM (\i x -> pure (VU.fromList [i + x, i + x])) $ VU.replicate @Int 3 0
[0,0,1,1,2,2]

Since: 1.5.1.0

mapAccumL :: forall v s a b. (HasCallStack, Vector v a, Vector v b) => (s -> a -> (s, b)) -> s -> v a -> (s, v b) Source #

\(O(n)\) Maps a vector with an accumulator.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.mapAccumL (\s x -> (s + 1, s * x)) (0 :: Int) $ VU.generate @Int 4 id
(4,[0,1,4,9])

Since: 1.5.1.0

chunks :: Vector v a => Int -> v a -> Vector (v a) Source #

\(O(n)\) Converts a vector into chunks of vectors with lenth \(k\). The last vector may have smaller length than \(k\).

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.chunks 3 $ VU.fromList ([1, 2, 3, 4, 5, 6, 7] :: [Int])
[[1,2,3],[4,5,6],[7]]

Since: 1.5.1.0

Monadic scanl

prescanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

prescanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

postscanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

postscanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

scanlM :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

scanlM' :: (HasCallStack, Monad m, Vector v a, Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a) Source #

Since: 1.5.1.0

scanl1M :: (HasCallStack, Monad m, Vector v a) => (a -> a -> m a) -> v a -> m (v a) Source #

Since: 1.5.1.0

scanl1M' :: (HasCallStack, Monad m, Vector v a) => (a -> a -> m a) -> v a -> m (v a) Source #

Since: 1.5.1.0

Queries

maxRangeSum :: (Vector v a, Ord a, Num a) => v a -> a Source #

\(O(n)\) Returns maximum range sum.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.maxRangeSum $ VU.fromList @Int [-3, 1, 6, -2, 7, -5]
12

Since: 1.5.1.0

minRangeSum :: (Vector v a, Ord a, Num a) => v a -> a Source #

\(O(n)\) Returns minimum range sum.

Example

>>> import AtCoder.Extra.Vector qualified as EV
>>> import Data.Vector.Unboxed qualified as VU
>>> EV.minRangeSum $ VU.fromList @Int[-3, 1, 6, -20, 7, -9]
-22

Since: 1.5.1.0

slideMinIndices :: HasCallStack => Int -> Vector Int -> Vector Int Source #

\(O(N)\) Returns indices of minimum values in the windows with the specified length.

Constraints

\(k \gt 0\)

Example

>>> slideMinIndices 3 (VU.fromList [0 .. 5])
[0,1,2,3]
>>> slideMinIndices 3 (VU.fromList [5, 4 .. 0])
[2,3,4,5]

Since: 1.5.1.0

slideMaxIndices :: HasCallStack => Int -> Vector Int -> Vector Int Source #

\(O(N)\) Returns indices of maximum values in the windows with the specified length.

Constraints

\(k \gt 0\)

Example

indices: 0 1 2 3 4 5
values:  0 1 2 3 4 5   max value indices:
         [---]         2
           [---]       3
             [---]     4
               [---]   5

>>> slideMaxIndices 3 (VU.fromList [0 .. 5])
[2,3,4,5]
>>> slideMaxIndices 3 (VU.fromList [5, 4 .. 0])
[0,1,2,3]

Since: 1.5.1.0