vector 0.13.1.0 → 0.13.2.0
raw patch · 53 files changed
+5177/−672 lines, 53 filesdep −HUnitdep ~QuickCheckdep ~basedep ~doctest
Dependencies removed: HUnit
Dependency ranges changed: QuickCheck, base, doctest, random
Files
- README.md +65/−2
- benchlib/Bench/Vector/Algo/AwShCC.hs +38/−0
- benchlib/Bench/Vector/Algo/FindIndexR.hs +24/−0
- benchlib/Bench/Vector/Algo/HybCC.hs +42/−0
- benchlib/Bench/Vector/Algo/Leaffix.hs +16/−0
- benchlib/Bench/Vector/Algo/ListRank.hs +21/−0
- benchlib/Bench/Vector/Algo/MutableSet.hs +30/−0
- benchlib/Bench/Vector/Algo/NextPermutation.hs +122/−0
- benchlib/Bench/Vector/Algo/Quickhull.hs +32/−0
- benchlib/Bench/Vector/Algo/Rootfix.hs +15/−0
- benchlib/Bench/Vector/Algo/Spectral.hs +21/−0
- benchlib/Bench/Vector/Algo/Tridiag.hs +16/−0
- benchlib/Bench/Vector/Tasty.hs +27/−0
- benchlib/Bench/Vector/TestData/Graph.hs +41/−0
- benchlib/Bench/Vector/TestData/ParenTree.hs +20/−0
- benchmarks/Algo/AwShCC.hs +0/−38
- benchmarks/Algo/FindIndexR.hs +0/−24
- benchmarks/Algo/HybCC.hs +0/−42
- benchmarks/Algo/Leaffix.hs +0/−16
- benchmarks/Algo/ListRank.hs +0/−21
- benchmarks/Algo/MutableSet.hs +0/−30
- benchmarks/Algo/Quickhull.hs +0/−32
- benchmarks/Algo/Rootfix.hs +0/−15
- benchmarks/Algo/Spectral.hs +0/−21
- benchmarks/Algo/Tridiag.hs +0/−16
- benchmarks/Main.hs +24/−37
- benchmarks/TestData/Graph.hs +0/−41
- benchmarks/TestData/ParenTree.hs +0/−20
- changelog.md +23/−0
- src/Data/Vector.hs +59/−5
- src/Data/Vector/Generic.hs +122/−44
- src/Data/Vector/Generic/Base.hs +9/−1
- src/Data/Vector/Generic/Mutable.hs +109/−40
- src/Data/Vector/Mutable.hs +37/−2
- src/Data/Vector/Primitive.hs +59/−5
- src/Data/Vector/Primitive/Mutable.hs +38/−3
- src/Data/Vector/Storable.hs +59/−5
- src/Data/Vector/Storable/Mutable.hs +39/−4
- src/Data/Vector/Strict.hs +2611/−0
- src/Data/Vector/Strict/Mutable.hs +787/−0
- src/Data/Vector/Unboxed.hs +124/−32
- src/Data/Vector/Unboxed/Base.hs +265/−1
- src/Data/Vector/Unboxed/Mutable.hs +46/−3
- tests/Boilerplater.hs +2/−17
- tests/Main.hs +16/−6
- tests/Setup.hs +0/−3
- tests/Tests/Move.hs +33/−3
- tests/Tests/Vector.hs +0/−15
- tests/Tests/Vector/Property.hs +3/−0
- tests/Tests/Vector/Strict.hs +52/−0
- tests/Utilities.hs +20/−0
- tests/doctests.hs +3/−0
- vector.cabal +107/−128
README.md view
@@ -1,6 +1,69 @@ The `vector` package [](https://github.com/haskell/vector/actions?query=branch%3Amaster) ==================== -An efficient implementation of `Int`-indexed arrays (both mutable and immutable), with a powerful loop optimisation framework.+Vector is a collection of efficient `Int`-indexed array implementations: +[boxed, unboxed, storable, and primitive vectors](#vectors-available-in-the-package)+(all can be mutable or immutable). The package features a generic API,+polymorphic in vector type, and implements [*stream fusion*](#stream-fusion), +a powerful optimisation framework that can help eliminate intermediate data structures. -See [`vector` on Hackage](http://hackage.haskell.org/package/vector) for more information.+## Table of Contents++<!-- no toc -->+- [Tutorial](#tutorial)+- [Vector vs Array](#vector-vs-array)+- [Vectors Available in the Package](#vectors-available-in-the-package)+- [Stream Fusion](#stream-fusion)++## Tutorial++A beginner-friendly tutorial for vectors can be found on +[MMHaskell](https://mmhaskell.com/data-structures/vector).+++If you have already started your adventure with vectors, +the tutorial on [Haskell Wiki](https://wiki.haskell.org/Numeric_Haskell:_A_Vector_Tutorial) +covers more ground.++## Vector vs Array++Arrays are data structures that can store a multitude of elements +and allow immediate access to every one of them. However, they are +often seen as legacy constructs that are rarely used in modern Haskell.+Even though Haskell has a built-in [Data.Array module](https://hackage.haskell.org/package/array-0.5.7.0), +arrays might be a bit overwhelming to use due to their complex API. +Conversely, vectors incorporate the array’s *O(1)* access to elements +with a much friendlier API of lists. Since they allow for framework +optimisation via loop fusion, vectors emphasise efficiency and keep +a rich interface. Unless you’re confident with arrays, it’s +well-advised to use vectors when looking for a similar functionality.++## Vectors Available in the Package++**Lazy boxed vectors** (`Data.Vector`) store each of their elements as a +pointer to a heap-allocated value. Because of indirection, lazy boxed vectors+are slower in comparison to unboxed vectors.++**Strict boxed vectors** (`Data.Vector.Strict`) contain elements that are +[strictly evaluated](https://tech.fpcomplete.com/haskell/tutorial/all-about-strictness/).++**Unboxed vectors** (`Data.Vector.Unboxed`) determine an array's representation+from its elements' type. For example, vector of primitive types (e.g. `Int`) will be +backed by primitive array while vector of product types by structure of arrays.+They are quite efficient due to the unboxed representation they use.++**Storable vectors** (`Data.Vector.Storable`) are backed by pinned memory, i.e., +they cannot be moved by the garbage collector. Their primary use case is C FFI. ++**Primitive vectors** (`Data.Vector.Primitive`) are backed by simple byte array and +can store only data types that are represented in memory as a sequence of bytes without+a pointer, i.e., they belong to the `Prim` type class, e.g., `Int`, `Double`, etc.+It's advised to use unboxed vectors if you're looking for the performance of primitive vectors,+but more versality. + +## Stream Fusion++An optimisation framework used by vectors, stream fusion is a technique that merges +several functions into one and prevents creation of intermediate data structures. For example, +the expression `sum . filter g . map f` won't allocate temporary vectors if +compiled with optimisations.
+ benchlib/Bench/Vector/Algo/AwShCC.hs view
@@ -0,0 +1,38 @@+{-# OPTIONS -fno-spec-constr-count #-}+module Bench.Vector.Algo.AwShCC (awshcc) where++import Data.Vector.Unboxed as V++awshcc :: (Int, Vector Int, Vector Int) -> Vector Int+{-# NOINLINE awshcc #-}+awshcc (n, es1, es2) = concomp ds es1' es2'+ where+ ds = V.enumFromTo 0 (n-1) V.++ V.enumFromTo 0 (n-1)+ es1' = es1 V.++ es2+ es2' = es2 V.++ es1++ starCheck ds = V.backpermute st' gs+ where+ gs = V.backpermute ds ds+ st = V.zipWith (==) ds gs+ st' = V.update st . V.filter (not . snd)+ $ V.zip gs st++ concomp ds es1 es2+ | V.and (starCheck ds'') = ds''+ | otherwise = concomp (V.backpermute ds'' ds'') es1 es2+ where+ ds' = V.update ds+ . V.map (\(di, dj, gi) -> (di, dj))+ . V.filter (\(di, dj, gi) -> gi == di && di > dj)+ $ V.zip3 (V.backpermute ds es1)+ (V.backpermute ds es2)+ (V.backpermute ds (V.backpermute ds es1))++ ds'' = V.update ds'+ . V.map (\(di, dj, st) -> (di, dj))+ . V.filter (\(di, dj, st) -> st && di /= dj)+ $ V.zip3 (V.backpermute ds' es1)+ (V.backpermute ds' es2)+ (V.backpermute (starCheck ds') es1)+
+ benchlib/Bench/Vector/Algo/FindIndexR.hs view
@@ -0,0 +1,24 @@+module Bench.Vector.Algo.FindIndexR (findIndexR, findIndexR_naive, findIndexR_manual)+where++import Data.Vector.Unboxed (Vector)+import qualified Data.Vector.Generic as V++findIndexR :: (Double -> Bool, Vector Double) -> Maybe Int+{-# NOINLINE findIndexR #-}+findIndexR = uncurry V.findIndexR++findIndexR_naive :: (Double -> Bool, Vector Double) -> Maybe Int+{-# NOINLINE findIndexR_naive #-}+findIndexR_naive (pred, v) = fmap (V.length v - 1 -)+ $ V.foldl (\a x -> if pred x+ then Just 1+ else succ<$>a) Nothing v++findIndexR_manual :: (Double -> Bool, Vector Double) -> Maybe Int+{-# NOINLINE findIndexR_manual #-}+findIndexR_manual (pred, v) = go $ V.length v - 1+ where go i | i < 0 = Nothing+ | pred (V.unsafeIndex v i) = Just i+ | otherwise = go $ i-1+
+ benchlib/Bench/Vector/Algo/HybCC.hs view
@@ -0,0 +1,42 @@+module Bench.Vector.Algo.HybCC (hybcc) where++import Data.Vector.Unboxed as V++hybcc :: (Int, Vector Int, Vector Int) -> Vector Int+{-# NOINLINE hybcc #-}+hybcc (n, e1, e2) = concomp (V.zip e1 e2) n+ where+ concomp es n+ | V.null es = V.enumFromTo 0 (n-1)+ | otherwise = V.backpermute ins ins+ where+ p = shortcut_all+ $ V.update (V.enumFromTo 0 (n-1)) es++ (es',i) = compress p es+ r = concomp es' (V.length i)+ ins = V.update_ p i+ $ V.backpermute i r++ enumerate bs = V.prescanl' (+) 0 $ V.map (\b -> if b then 1 else 0) bs++ pack_index bs = V.map fst+ . V.filter snd+ $ V.zip (V.enumFromTo 0 (V.length bs - 1)) bs++ shortcut_all p | p == pp = pp+ | otherwise = shortcut_all pp+ where+ pp = V.backpermute p p++ compress p es = (new_es, pack_index roots)+ where+ (e1,e2) = V.unzip es+ es' = V.map (\(x,y) -> if x > y then (y,x) else (x,y))+ . V.filter (\(x,y) -> x /= y)+ $ V.zip (V.backpermute p e1) (V.backpermute p e2)++ roots = V.zipWith (==) p (V.enumFromTo 0 (V.length p - 1))+ labels = enumerate roots+ (e1',e2') = V.unzip es'+ new_es = V.zip (V.backpermute labels e1') (V.backpermute labels e2')
+ benchlib/Bench/Vector/Algo/Leaffix.hs view
@@ -0,0 +1,16 @@+module Bench.Vector.Algo.Leaffix where++import Data.Vector.Unboxed as V++leaffix :: (Vector Int, Vector Int) -> Vector Int+{-# NOINLINE leaffix #-}+leaffix (ls,rs)+ = leaffix (V.replicate (V.length ls) 1) ls rs+ where+ leaffix xs ls rs+ = let zs = V.replicate (V.length ls * 2) 0+ vs = V.update_ zs ls xs+ sums = V.prescanl' (+) 0 vs+ in+ V.zipWith (-) (V.backpermute sums ls) (V.backpermute sums rs)+
+ benchlib/Bench/Vector/Algo/ListRank.hs view
@@ -0,0 +1,21 @@+module Bench.Vector.Algo.ListRank+where++import Data.Vector.Unboxed as V++listRank :: Int -> Vector Int+{-# NOINLINE listRank #-}+listRank n = pointer_jump xs val+ where+ xs = 0 `V.cons` V.enumFromTo 0 (n-2)++ val = V.zipWith (\i j -> if i == j then 0 else 1)+ xs (V.enumFromTo 0 (n-1))++ pointer_jump pt val+ | npt == pt = val+ | otherwise = pointer_jump npt nval+ where+ npt = V.backpermute pt pt+ nval = V.zipWith (+) val (V.backpermute val pt)+
+ benchlib/Bench/Vector/Algo/MutableSet.hs view
@@ -0,0 +1,30 @@+{-# LANGUAGE BangPatterns #-}++module Bench.Vector.Algo.MutableSet+where++import Prelude hiding(length, read)++import Data.Vector.Mutable++mutableSet :: IOVector Int -> IO Int+{-# NOINLINE mutableSet #-}+mutableSet v = do+ let repetitions = 100 -- we repeat to reduce the standard deviation in measurements.+ l = length v++ -- This function is tail recursive.+ f :: Int -> Int -> IO Int+ f i !curSum =+ if i == 0+ then+ return curSum+ else do+ -- 'set' is what we want to benchmark.+ set v i+ -- In order to make it difficult for ghc to optimize the 'set' call+ -- away, we read the value of one element and add it to a running sum+ -- which is returned by the function.+ val <- read v (l-1)+ f (i-1) (curSum+val)+ f repetitions 0
+ benchlib/Bench/Vector/Algo/NextPermutation.hs view
@@ -0,0 +1,122 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+module Bench.Vector.Algo.NextPermutation (generatePermTests) where++import qualified Data.Vector.Unboxed as V+import qualified Data.Vector.Unboxed.Mutable as M+import qualified Data.Vector.Generic.Mutable as G+import System.Random.Stateful+ ( StatefulGen, UniformRange(uniformRM) )++-- | Generate a list of benchmarks for permutation algorithms.+-- The list contains pairs of benchmark names and corresponding actions.+-- The actions are to be executed by the benchmarking framework.+-- +-- The list contains the following benchmarks:+-- - @(next|prev)Permutation@ on a small vector repeated until the end of the permutation cycle+-- - Bijective versions of @(next|prev)Permutation@ on a vector of size @n@, repeated @n@ times+-- - ascending permutation+-- - descending permutation+-- - random permutation+-- - Baseline for bijective versions: just copying a vector of size @n@. Note that the tests for+-- bijective versions begins with copying a vector.+generatePermTests :: StatefulGen g IO => g -> Int -> IO [(String, IO ())]+generatePermTests gen useSize = do+ let !k = useSizeToPermLen useSize+ let !vasc = V.generate useSize id+ !vdesc = V.generate useSize (useSize-1-)+ !vrnd <- randomPermutationWith gen useSize+ return+ [ ("nextPermutation (small vector, until end)", loopPermutations k)+ , ("nextPermutationBijective (ascending perm of size n, n times)", repeatNextPermutation vasc useSize)+ , ("nextPermutationBijective (descending perm of size n, n times)", repeatNextPermutation vdesc useSize)+ , ("nextPermutationBijective (random perm of size n, n times)", repeatNextPermutation vrnd useSize)+ , ("prevPermutation (small vector, until end)", loopRevPermutations k)+ , ("prevPermutationBijective (ascending perm of size n, n times)", repeatPrevPermutation vasc useSize)+ , ("prevPermutationBijective (descending perm of size n, n times)", repeatPrevPermutation vdesc useSize)+ , ("prevPermutationBijective (random perm of size n, n times)", repeatPrevPermutation vrnd useSize)+ , ("baseline for *Bijective (just copying the vector of size n)", V.thaw vrnd >> return ())+ ]++-- | Given a PRNG and a length @n@, generate a random permutation of @[0..n-1]@.+randomPermutationWith :: (StatefulGen g IO) => g -> Int -> IO (V.Vector Int)+randomPermutationWith gen n = do+ v <- M.generate n id+ V.forM_ (V.generate (n-1) id) $ \ !i -> do+ j <- uniformRM (i,n-1) gen+ M.swap v i j+ V.unsafeFreeze v++-- | Given @useSize@ benchmark option, compute the largest @n <= 12@ such that @n! <= useSize@.+-- Repeat-nextPermutation-until-end benchmark will use @n@ as the length of the vector.+-- Note that 12 is the largest @n@ such that @n!@ can be represented as an 'Int32'.+useSizeToPermLen :: Int -> Int+useSizeToPermLen us = case V.findIndex (> max 0 us) $ V.scanl' (*) 1 $ V.generate 12 (+1) of+ Just i -> i-1+ Nothing -> 12++-- | A bijective version of @G.nextPermutation@ that reverses the vector+-- if it is already in descending order.+-- "Bijective" here means that the function forms a cycle over all permutations+-- of the vector's elements.+--+-- This has a nice property that should be benchmarked: +-- this function takes amortized constant time each call,+-- if successively called either Omega(n) times on a single vector having distinct elements,+-- or arbitrary times on a single vector initially in strictly ascending order.+nextPermutationBijective :: (G.MVector v a, Ord a) => v G.RealWorld a -> IO Bool+nextPermutationBijective v = do+ res <- G.nextPermutation v+ if res then return True else G.reverse v >> return False++-- | A bijective version of @G.prevPermutation@ that reverses the vector+-- if it is already in ascending order.+-- "Bijective" here means that the function forms a cycle over all permutations+-- of the vector's elements.+--+-- This has a nice property that should be benchmarked:+-- this function takes amortized constant time each call,+-- if successively called either Omega(n) times on a single vector having distinct elements,+-- or arbitrary times on a single vector initially in strictly descending order.+prevPermutationBijective :: (G.MVector v a, Ord a) => v G.RealWorld a -> IO Bool+prevPermutationBijective v = do+ res <- G.prevPermutation v+ if res then return True else G.reverse v >> return False++-- | Repeat @nextPermutation@ on @[0..n-1]@ until the end.+loopPermutations :: Int -> IO ()+loopPermutations n = do+ v <- M.generate n id+ let loop = do+ res <- M.nextPermutation v+ if res then loop else return ()+ loop++-- | Repeat @prevPermutation@ on @[n-1,n-2..0]@ until the end.+loopRevPermutations :: Int -> IO ()+loopRevPermutations n = do+ v <- M.generate n (n-1-)+ let loop = do+ res <- M.prevPermutation v+ if res then loop else return ()+ loop++-- | Repeat @nextPermutationBijective@ on a given vector given times.+repeatNextPermutation :: V.Vector Int -> Int -> IO ()+repeatNextPermutation !v !n = do+ !mv <- V.thaw v+ let loop !i | i <= 0 = return ()+ loop !i = do+ _ <- nextPermutationBijective mv+ loop (i-1)+ loop n++-- | Repeat @prevPermutationBijective@ on a given vector given times.+repeatPrevPermutation :: V.Vector Int -> Int -> IO ()+repeatPrevPermutation !v !n = do+ !mv <- V.thaw v+ let loop !i | i <= 0 = return ()+ loop !i = do+ _ <- prevPermutationBijective mv+ loop (i-1)+ loop n
+ benchlib/Bench/Vector/Algo/Quickhull.hs view
@@ -0,0 +1,32 @@+module Bench.Vector.Algo.Quickhull (quickhull) where++import Data.Vector.Unboxed as V++quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)+{-# NOINLINE quickhull #-}+quickhull (xs, ys) = xs' `seq` ys' `seq` (xs',ys')+ where+ (xs',ys') = V.unzip+ $ hsplit points pmin pmax V.++ hsplit points pmax pmin++ imin = V.minIndex xs+ imax = V.maxIndex xs++ points = V.zip xs ys+ pmin = points V.! imin+ pmax = points V.! imax+++ hsplit points p1 p2+ | V.length packed < 2 = p1 `V.cons` packed+ | otherwise = hsplit packed p1 pm V.++ hsplit packed pm p2+ where+ cs = V.map (\p -> cross p p1 p2) points+ packed = V.map fst+ $ V.filter (\t -> snd t > 0)+ $ V.zip points cs++ pm = points V.! V.maxIndex cs++ cross (x,y) (x1,y1) (x2,y2) = (x1-x)*(y2-y) - (y1-y)*(x2-x)+
+ benchlib/Bench/Vector/Algo/Rootfix.hs view
@@ -0,0 +1,15 @@+module Bench.Vector.Algo.Rootfix where++import Data.Vector.Unboxed as V++rootfix :: (V.Vector Int, V.Vector Int) -> V.Vector Int+{-# NOINLINE rootfix #-}+rootfix (ls, rs) = rootfix (V.replicate (V.length ls) 1) ls rs+ where+ rootfix xs ls rs+ = let zs = V.replicate (V.length ls * 2) 0+ vs = V.update_ (V.update_ zs ls xs) rs (V.map negate xs)+ sums = V.prescanl' (+) 0 vs+ in+ V.backpermute sums ls+
+ benchlib/Bench/Vector/Algo/Spectral.hs view
@@ -0,0 +1,21 @@+module Bench.Vector.Algo.Spectral ( spectral ) where++import Data.Vector.Unboxed as V++import Data.Bits++spectral :: Vector Double -> Vector Double+{-# NOINLINE spectral #-}+spectral us = us `seq` V.map row (V.enumFromTo 0 (n-1))+ where+ n = V.length us++ row i = i `seq` V.sum (V.imap (\j u -> eval_A i j * u) us)++ eval_A i j = 1 / fromIntegral r+ where+ r = u + (i+1)+ u = t `shiftR` 1+ t = n * (n+1)+ n = i+j+
+ benchlib/Bench/Vector/Algo/Tridiag.hs view
@@ -0,0 +1,16 @@+module Bench.Vector.Algo.Tridiag ( tridiag ) where++import Data.Vector.Unboxed as V++tridiag :: (Vector Double, Vector Double, Vector Double, Vector Double)+ -> Vector Double+{-# NOINLINE tridiag #-}+tridiag (as,bs,cs,ds) = V.prescanr' (\(c,d) x' -> d - c*x') 0+ $ V.prescanl' modify (0,0)+ $ V.zip (V.zip as bs) (V.zip cs ds)+ where+ modify (c',d') ((a,b),(c,d)) = + let id = 1 / (b - c'*a)+ in+ id `seq` (c*id, (d-d'*a)*id)+
+ benchlib/Bench/Vector/Tasty.hs view
@@ -0,0 +1,27 @@+-- |+-- Tasty integration for vector benchmarks.+module Bench.Vector.Tasty+ ( VectorSize(..)+ , RandomSeed(..)+ ) where++import Test.Tasty.Options+++-- | Size of vector used in benchmarks+newtype VectorSize = VectorSize Int++instance IsOption VectorSize where+ defaultValue = VectorSize 2000000+ parseValue = fmap VectorSize . safeRead+ optionName = pure "size"+ optionHelp = pure "Size of vectors used in benchmarks"++-- | Random seed used for generation of the test data+newtype RandomSeed = RandomSeed Int++instance IsOption RandomSeed where+ defaultValue = RandomSeed 42+ parseValue = fmap RandomSeed . safeRead+ optionName = pure "seed"+ optionHelp = pure "Random seed used for generation of the test data"
+ benchlib/Bench/Vector/TestData/Graph.hs view
@@ -0,0 +1,41 @@+module Bench.Vector.TestData.Graph+ ( randomGraph+ ) where++import System.Random.Stateful+import qualified Data.Vector as V+import qualified Data.Vector.Mutable as MV+import qualified Data.Vector.Unboxed as U++randomGraph+ :: (StatefulGen g m, MV.PrimMonad m)+ => g+ -> Int+ -> m (Int, U.Vector Int, U.Vector Int)+randomGraph g edges = do+ let vertices = edges `div` 10+ marr <- MV.replicate vertices []+ addRandomEdges g vertices marr edges+ arr <- V.unsafeFreeze marr+ let (as, bs) = unzip [ (i, j) | i <- [0 .. vertices - 1], j <- arr V.! i ]+ return (vertices, U.fromList as, U.fromList bs)++addRandomEdges+ :: (StatefulGen g m, MV.PrimMonad m)+ => g+ -> Int+ -> MV.MVector (MV.PrimState m) [Int]+ -> Int+ -> m ()+addRandomEdges g vertices arr = fill+ where+ fill 0 = return ()+ fill e = do+ m1 <- uniformRM (0, vertices - 1) g+ m2 <- uniformRM (0, vertices - 1) g+ let lo = min m1 m2+ hi = max m1 m2+ ns <- MV.read arr lo+ if lo == hi || hi `elem` ns+ then fill e+ else MV.write arr lo (hi : ns) >> fill (e - 1)
+ benchlib/Bench/Vector/TestData/ParenTree.hs view
@@ -0,0 +1,20 @@+module Bench.Vector.TestData.ParenTree where++import qualified Data.Vector.Unboxed as V++parenTree :: Int -> (V.Vector Int, V.Vector Int)+parenTree n = case go ([],[]) 0 (if even n then n else n+1) of+ (ls,rs) -> (V.fromListN (length ls) (reverse ls),+ V.fromListN (length rs) (reverse rs))+ where+ go (ls,rs) i j = case j-i of+ 0 -> (ls,rs)+ 2 -> (ls',rs')+ d -> let k = ((d-2) `div` 4) * 2+ in+ go (go (ls',rs') (i+1) (i+1+k)) (i+1+k) (j-1)+ where+ ls' = i:ls+ rs' = j-1:rs++
− benchmarks/Algo/AwShCC.hs
@@ -1,38 +0,0 @@-{-# OPTIONS -fno-spec-constr-count #-}-module Algo.AwShCC (awshcc) where--import Data.Vector.Unboxed as V--awshcc :: (Int, Vector Int, Vector Int) -> Vector Int-{-# NOINLINE awshcc #-}-awshcc (n, es1, es2) = concomp ds es1' es2'- where- ds = V.enumFromTo 0 (n-1) V.++ V.enumFromTo 0 (n-1)- es1' = es1 V.++ es2- es2' = es2 V.++ es1-- starCheck ds = V.backpermute st' gs- where- gs = V.backpermute ds ds- st = V.zipWith (==) ds gs- st' = V.update st . V.filter (not . snd)- $ V.zip gs st-- concomp ds es1 es2- | V.and (starCheck ds'') = ds''- | otherwise = concomp (V.backpermute ds'' ds'') es1 es2- where- ds' = V.update ds- . V.map (\(di, dj, gi) -> (di, dj))- . V.filter (\(di, dj, gi) -> gi == di && di > dj)- $ V.zip3 (V.backpermute ds es1)- (V.backpermute ds es2)- (V.backpermute ds (V.backpermute ds es1))-- ds'' = V.update ds'- . V.map (\(di, dj, st) -> (di, dj))- . V.filter (\(di, dj, st) -> st && di /= dj)- $ V.zip3 (V.backpermute ds' es1)- (V.backpermute ds' es2)- (V.backpermute (starCheck ds') es1)-
− benchmarks/Algo/FindIndexR.hs
@@ -1,24 +0,0 @@-module Algo.FindIndexR (findIndexR, findIndexR_naive, findIndexR_manual)-where--import Data.Vector.Unboxed (Vector)-import qualified Data.Vector.Generic as V--findIndexR :: (Double -> Bool, Vector Double) -> Maybe Int-{-# NOINLINE findIndexR #-}-findIndexR = uncurry V.findIndexR--findIndexR_naive :: (Double -> Bool, Vector Double) -> Maybe Int-{-# NOINLINE findIndexR_naive #-}-findIndexR_naive (pred, v) = fmap (V.length v - 1 -)- $ V.foldl (\a x -> if pred x- then Just 1- else succ<$>a) Nothing v--findIndexR_manual :: (Double -> Bool, Vector Double) -> Maybe Int-{-# NOINLINE findIndexR_manual #-}-findIndexR_manual (pred, v) = go $ V.length v - 1- where go i | i < 0 = Nothing- | pred (V.unsafeIndex v i) = Just i- | otherwise = go $ i-1-
− benchmarks/Algo/HybCC.hs
@@ -1,42 +0,0 @@-module Algo.HybCC (hybcc) where--import Data.Vector.Unboxed as V--hybcc :: (Int, Vector Int, Vector Int) -> Vector Int-{-# NOINLINE hybcc #-}-hybcc (n, e1, e2) = concomp (V.zip e1 e2) n- where- concomp es n- | V.null es = V.enumFromTo 0 (n-1)- | otherwise = V.backpermute ins ins- where- p = shortcut_all- $ V.update (V.enumFromTo 0 (n-1)) es-- (es',i) = compress p es- r = concomp es' (V.length i)- ins = V.update_ p i- $ V.backpermute i r-- enumerate bs = V.prescanl' (+) 0 $ V.map (\b -> if b then 1 else 0) bs-- pack_index bs = V.map fst- . V.filter snd- $ V.zip (V.enumFromTo 0 (V.length bs - 1)) bs-- shortcut_all p | p == pp = pp- | otherwise = shortcut_all pp- where- pp = V.backpermute p p-- compress p es = (new_es, pack_index roots)- where- (e1,e2) = V.unzip es- es' = V.map (\(x,y) -> if x > y then (y,x) else (x,y))- . V.filter (\(x,y) -> x /= y)- $ V.zip (V.backpermute p e1) (V.backpermute p e2)-- roots = V.zipWith (==) p (V.enumFromTo 0 (V.length p - 1))- labels = enumerate roots- (e1',e2') = V.unzip es'- new_es = V.zip (V.backpermute labels e1') (V.backpermute labels e2')
− benchmarks/Algo/Leaffix.hs
@@ -1,16 +0,0 @@-module Algo.Leaffix where--import Data.Vector.Unboxed as V--leaffix :: (Vector Int, Vector Int) -> Vector Int-{-# NOINLINE leaffix #-}-leaffix (ls,rs)- = leaffix (V.replicate (V.length ls) 1) ls rs- where- leaffix xs ls rs- = let zs = V.replicate (V.length ls * 2) 0- vs = V.update_ zs ls xs- sums = V.prescanl' (+) 0 vs- in- V.zipWith (-) (V.backpermute sums ls) (V.backpermute sums rs)-
− benchmarks/Algo/ListRank.hs
@@ -1,21 +0,0 @@-module Algo.ListRank-where--import Data.Vector.Unboxed as V--listRank :: Int -> Vector Int-{-# NOINLINE listRank #-}-listRank n = pointer_jump xs val- where- xs = 0 `V.cons` V.enumFromTo 0 (n-2)-- val = V.zipWith (\i j -> if i == j then 0 else 1)- xs (V.enumFromTo 0 (n-1))-- pointer_jump pt val- | npt == pt = val- | otherwise = pointer_jump npt nval- where- npt = V.backpermute pt pt- nval = V.zipWith (+) val (V.backpermute val pt)-
− benchmarks/Algo/MutableSet.hs
@@ -1,30 +0,0 @@-{-# LANGUAGE BangPatterns #-}--module Algo.MutableSet-where--import Prelude hiding(length, read)--import Data.Vector.Mutable--mutableSet :: IOVector Int -> IO Int-{-# NOINLINE mutableSet #-}-mutableSet v = do- let repetitions = 100 -- we repeat to reduce the standard deviation in measurements.- l = length v-- -- This function is tail recursive.- f :: Int -> Int -> IO Int- f i !curSum =- if i == 0- then- return curSum- else do- -- 'set' is what we want to benchmark.- set v i- -- In order to make it difficult for ghc to optimize the 'set' call- -- away, we read the value of one element and add it to a running sum- -- which is returned by the function.- val <- read v (l-1)- f (i-1) (curSum+val)- f repetitions 0
− benchmarks/Algo/Quickhull.hs
@@ -1,32 +0,0 @@-module Algo.Quickhull (quickhull) where--import Data.Vector.Unboxed as V--quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)-{-# NOINLINE quickhull #-}-quickhull (xs, ys) = xs' `seq` ys' `seq` (xs',ys')- where- (xs',ys') = V.unzip- $ hsplit points pmin pmax V.++ hsplit points pmax pmin-- imin = V.minIndex xs- imax = V.maxIndex xs-- points = V.zip xs ys- pmin = points V.! imin- pmax = points V.! imax--- hsplit points p1 p2- | V.length packed < 2 = p1 `V.cons` packed- | otherwise = hsplit packed p1 pm V.++ hsplit packed pm p2- where- cs = V.map (\p -> cross p p1 p2) points- packed = V.map fst- $ V.filter (\t -> snd t > 0)- $ V.zip points cs-- pm = points V.! V.maxIndex cs-- cross (x,y) (x1,y1) (x2,y2) = (x1-x)*(y2-y) - (y1-y)*(x2-x)-
− benchmarks/Algo/Rootfix.hs
@@ -1,15 +0,0 @@-module Algo.Rootfix where--import Data.Vector.Unboxed as V--rootfix :: (V.Vector Int, V.Vector Int) -> V.Vector Int-{-# NOINLINE rootfix #-}-rootfix (ls, rs) = rootfix (V.replicate (V.length ls) 1) ls rs- where- rootfix xs ls rs- = let zs = V.replicate (V.length ls * 2) 0- vs = V.update_ (V.update_ zs ls xs) rs (V.map negate xs)- sums = V.prescanl' (+) 0 vs- in- V.backpermute sums ls-
− benchmarks/Algo/Spectral.hs
@@ -1,21 +0,0 @@-module Algo.Spectral ( spectral ) where--import Data.Vector.Unboxed as V--import Data.Bits--spectral :: Vector Double -> Vector Double-{-# NOINLINE spectral #-}-spectral us = us `seq` V.map row (V.enumFromTo 0 (n-1))- where- n = V.length us-- row i = i `seq` V.sum (V.imap (\j u -> eval_A i j * u) us)-- eval_A i j = 1 / fromIntegral r- where- r = u + (i+1)- u = t `shiftR` 1- t = n * (n+1)- n = i+j-
− benchmarks/Algo/Tridiag.hs
@@ -1,16 +0,0 @@-module Algo.Tridiag ( tridiag ) where--import Data.Vector.Unboxed as V--tridiag :: (Vector Double, Vector Double, Vector Double, Vector Double)- -> Vector Double-{-# NOINLINE tridiag #-}-tridiag (as,bs,cs,ds) = V.prescanr' (\(c,d) x' -> d - c*x') 0- $ V.prescanl' modify (0,0)- $ V.zip (V.zip as bs) (V.zip cs ds)- where- modify (c',d') ((a,b),(c,d)) = - let id = 1 / (b - c'*a)- in- id `seq` (c*id, (d-d'*a)*id)-
benchmarks/Main.hs view
@@ -1,18 +1,21 @@+{-# LANGUAGE BangPatterns #-} module Main where -import Algo.MutableSet (mutableSet)-import Algo.ListRank (listRank)-import Algo.Rootfix (rootfix)-import Algo.Leaffix (leaffix)-import Algo.AwShCC (awshcc)-import Algo.HybCC (hybcc)-import Algo.Quickhull (quickhull)-import Algo.Spectral (spectral)-import Algo.Tridiag (tridiag)-import Algo.FindIndexR (findIndexR, findIndexR_naive, findIndexR_manual)+import Bench.Vector.Algo.MutableSet (mutableSet)+import Bench.Vector.Algo.ListRank (listRank)+import Bench.Vector.Algo.Rootfix (rootfix)+import Bench.Vector.Algo.Leaffix (leaffix)+import Bench.Vector.Algo.AwShCC (awshcc)+import Bench.Vector.Algo.HybCC (hybcc)+import Bench.Vector.Algo.Quickhull (quickhull)+import Bench.Vector.Algo.Spectral (spectral)+import Bench.Vector.Algo.Tridiag (tridiag)+import Bench.Vector.Algo.FindIndexR (findIndexR, findIndexR_naive, findIndexR_manual)+import Bench.Vector.Algo.NextPermutation (generatePermTests) -import TestData.ParenTree (parenTree)-import TestData.Graph (randomGraph)+import Bench.Vector.TestData.ParenTree (parenTree)+import Bench.Vector.TestData.Graph (randomGraph)+import Bench.Vector.Tasty import Data.Proxy import qualified Data.Vector.Mutable as MV@@ -24,22 +27,7 @@ import Test.Tasty.Options import Test.Tasty.Runners -newtype VectorSize = VectorSize Int -instance IsOption VectorSize where- defaultValue = VectorSize 2000000- parseValue = fmap VectorSize . safeRead- optionName = pure "size"- optionHelp = pure "Size of vectors used in benchmarks"--newtype RandomSeed = RandomSeed Int--instance IsOption RandomSeed where- defaultValue = RandomSeed 42- parseValue = fmap RandomSeed . safeRead- optionName = pure "seed"- optionHelp = pure "Random seed used in benchmarks"- indexFindThreshold :: Double indexFindThreshold = 2e-5 @@ -53,19 +41,17 @@ gen <- newIOGenM (mkStdGen useSeed) - let (lparens, rparens) = parenTree useSize- (nodes, edges1, edges2) <- randomGraph gen useSize- lparens `seq` rparens `seq` nodes `seq` edges1 `seq` edges2 `seq` return ()+ let (!lparens, !rparens) = parenTree useSize+ (!nodes, !edges1, !edges2) <- randomGraph gen useSize let randomVector l = U.replicateM l (uniformDoublePositive01M gen)- as <- randomVector useSize- bs <- randomVector useSize- cs <- randomVector useSize- ds <- randomVector useSize- sp <- randomVector (floor $ sqrt $ fromIntegral useSize)- as `seq` bs `seq` cs `seq` ds `seq` sp `seq` return ()-+ !as <- randomVector useSize+ !bs <- randomVector useSize+ !cs <- randomVector useSize+ !ds <- randomVector useSize+ !sp <- randomVector (floor $ sqrt $ fromIntegral useSize) vi <- MV.new useSize+ permTests <- generatePermTests gen useSize defaultMainWithIngredients ingredients $ bgroup "All" [ bench "listRank" $ whnf listRank useSize@@ -82,4 +68,5 @@ , bench "findIndexR_manual" $ whnf findIndexR_manual ((<indexFindThreshold), as) , bench "minimumOn" $ whnf (U.minimumOn (\x -> x*x*x)) as , bench "maximumOn" $ whnf (U.maximumOn (\x -> x*x*x)) as+ , bgroup "(next|prev)Permutation" $ map (\(name, act) -> bench name $ whnfIO act) permTests ]
− benchmarks/TestData/Graph.hs
@@ -1,41 +0,0 @@-module TestData.Graph- ( randomGraph- ) where--import System.Random.Stateful-import qualified Data.Vector as V-import qualified Data.Vector.Mutable as MV-import qualified Data.Vector.Unboxed as U--randomGraph- :: (StatefulGen g m, MV.PrimMonad m)- => g- -> Int- -> m (Int, U.Vector Int, U.Vector Int)-randomGraph g edges = do- let vertices = edges `div` 10- marr <- MV.replicate vertices []- addRandomEdges g vertices marr edges- arr <- V.unsafeFreeze marr- let (as, bs) = unzip [ (i, j) | i <- [0 .. vertices - 1], j <- arr V.! i ]- return (vertices, U.fromList as, U.fromList bs)--addRandomEdges- :: (StatefulGen g m, MV.PrimMonad m)- => g- -> Int- -> MV.MVector (MV.PrimState m) [Int]- -> Int- -> m ()-addRandomEdges g vertices arr = fill- where- fill 0 = return ()- fill e = do- m1 <- uniformRM (0, vertices - 1) g- m2 <- uniformRM (0, vertices - 1) g- let lo = min m1 m2- hi = max m1 m2- ns <- MV.read arr lo- if lo == hi || hi `elem` ns- then fill e- else MV.write arr lo (hi : ns) >> fill (e - 1)
− benchmarks/TestData/ParenTree.hs
@@ -1,20 +0,0 @@-module TestData.ParenTree where--import qualified Data.Vector.Unboxed as V--parenTree :: Int -> (V.Vector Int, V.Vector Int)-parenTree n = case go ([],[]) 0 (if even n then n else n+1) of- (ls,rs) -> (V.fromListN (length ls) (reverse ls),- V.fromListN (length rs) (reverse rs))- where- go (ls,rs) i j = case j-i of- 0 -> (ls,rs)- 2 -> (ls',rs')- d -> let k = ((d-2) `div` 4) * 2- in- go (go (ls',rs') (i+1) (i+1+k)) (i+1+k) (j-1)- where- ls' = i:ls- rs' = j-1:rs--
changelog.md view
@@ -1,3 +1,26 @@+# Changes in version 0.13.2.0++ * Strict boxed vector `Data.Vector.Strict` and `Data.Vector.Strict.Mutable` is+ added (#488). it ensures that all values in the vector are evaluated to WHNF.+ * `DoNotUnboxStrict`, `DoNotUnboxLazy`, and `DoNotUnboxNormalForm` wrapper are+ added for defining unbox instances for types that contain not unboxable fields.+ [#503](https://github.com/haskell/vector/issues/506),+ [#508](https://github.com/haskell/vector/pull/508)+ * `spanR` and `breakR` were added [#476](https://github.com/haskell/vector/pull/476).+ They allow parsing vector from the right.+ * We had some improvements on `*.Mutable.{next,prev}Permutation{,By}`+ [#498](https://github.com/haskell/vector/pull/498):+ * Add `*.Mutable.prevPermutation{,By}` and `*.Mutable.nextPermutationBy`+ * Improve time performance. We may now expect good specialization supported by inlining.+ The implementation has also been algorithmically updated: in the previous implementation+ the full enumeration of all the permutations of `[1..n]` took Omega(n*n!), but it now takes O(n!).+ * Add tests for `{next,prev}Permutation`+ * Add benchmarks for `{next,prev}Permutation`+ * Cabal >= 3.0 is now required for building package (#481).+ * `vector:benchmarks-O2` public sublibrary containing benchmarks is added (#481).+ * Type family `Mutable` provides instances for arrays from `primitive`.+ * Various documentation improvements.+ # Changes in version 0.13.1.0 * Specialized variants of `findIndexR` are reexported for all vector
src/Data/Vector.hs view
@@ -122,7 +122,7 @@ takeWhile, dropWhile, -- ** Partitioning- partition, unstablePartition, partitionWith, span, break, groupBy, group,+ partition, unstablePartition, partitionWith, span, break, spanR, breakR, groupBy, group, -- ** Searching elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,@@ -892,7 +892,7 @@ -- ------------------------ -- | /O(n)/ Yield the argument, but force it not to retain any extra memory,--- possibly by copying it.+-- by copying it. -- -- This is especially useful when dealing with slices. For example: --@@ -998,7 +998,7 @@ accumulate = G.accumulate -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the--- corresponding value @b@ from the the value vector,+-- corresponding value @b@ from the value vector, -- replace the element of the initial vector at -- position @i@ by @f a b@. --@@ -1400,16 +1400,62 @@ -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy -- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.span (<4) $ V.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9]) span :: (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE span #-} span = G.span -- | /O(n)/ Split the vector into the longest prefix of elements that do not -- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.break (>4) $ V.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9]) break :: (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE break #-} break = G.break +-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.spanR (>4) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+spanR :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE spanR #-}+spanR = G.spanR++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since NEXT_VERSION+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.breakR (<5) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+breakR :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE breakR #-}+breakR = G.breakR+ -- | /O(n)/ Split a vector into a list of slices, using a predicate function. -- -- The concatenation of this list of slices is equal to the argument vector,@@ -2126,7 +2172,15 @@ {-# INLINE toList #-} toList = G.toList --- | /O(n)/ Convert a list to a vector.+-- | /O(n)/ Convert a list to a vector. During the operation, the +-- vector’s capacity will be doubling until the list's contents are +-- in the vector. Depending on the list’s size, up to half of the vector’s +-- capacity might be empty. If you’d rather avoid this, you can use +-- 'fromListN', which will provide the exact space the list requires but will +-- prevent list fusion, or @'force' . 'fromList'@, which will create the +-- vector and then copy it without the superfluous space.+--+-- @since 0.3 fromList :: [a] -> Vector a {-# INLINE fromList #-} fromList = G.fromList@@ -2252,4 +2306,4 @@ -- $setup -- >>> :set -Wno-type-defaults--- >>> import Prelude (Char, String, Bool(True, False), min, max, fst, even, undefined)+-- >>> import Prelude (Char, String, Bool(True, False), min, max, fst, even, undefined, Ord(..))
src/Data/Vector/Generic.hs view
@@ -110,7 +110,7 @@ takeWhile, dropWhile, -- ** Partitioning- partition, partitionWith, unstablePartition, span, break, groupBy, group,+ partition, partitionWith, unstablePartition, span, break, spanR, breakR, groupBy, group, -- ** Searching elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,@@ -228,19 +228,35 @@ -- Indexing -- -------- +-- NOTE: [Strict indexing]+-- ~~~~~~~~~~~~~~~~~~~~~~~+--+-- Why index parameters are strict in indexing ((!), (!?)) functions+-- and functions for accessing elements in mutable arrays ('unsafeRead',+-- 'unsafeWrite', 'unsafeModify'), and slice functions?+--+-- These function call class methods ('basicUnsafeIndexM',+-- 'basicUnsafeRead', etc) and, unless (!) was already specialised to+-- a specific v, GHC has no clue that i is most certainly to be used+-- eagerly. Bang before i hints this vital for optimizer information.++ infixl 9 ! -- | O(1) Indexing. (!) :: (HasCallStack, Vector v a) => v a -> Int -> a {-# INLINE_FUSED (!) #-}-(!) v i = checkIndex Bounds i (length v) $ unBox (basicUnsafeIndexM v i)+-- See NOTE: [Strict indexing]+(!) v !i = checkIndex Bounds i (length v) $ unBox (basicUnsafeIndexM v i) infixl 9 !? -- | O(1) Safe indexing. (!?) :: Vector v a => v a -> Int -> Maybe a {-# INLINE_FUSED (!?) #-}+-- See NOTE: [Strict indexing] -- Use basicUnsafeIndexM @Box to perform the indexing eagerly.-v !? i | i `inRange` length v = case basicUnsafeIndexM v i of Box a -> Just a- | otherwise = Nothing+v !? (!i)+ | i `inRange` length v = case basicUnsafeIndexM v i of Box a -> Just a+ | otherwise = Nothing -- | /O(1)/ First element.@@ -256,7 +272,8 @@ -- | /O(1)/ Unsafe indexing without bounds checking. unsafeIndex :: Vector v a => v a -> Int -> a {-# INLINE_FUSED unsafeIndex #-}-unsafeIndex v i = checkIndex Unsafe i (length v) $ unBox (basicUnsafeIndexM v i)+-- See NOTE: [Strict indexing]+unsafeIndex v !i = checkIndex Unsafe i (length v) $ unBox (basicUnsafeIndexM v i) -- | /O(1)/ First element, without checking if the vector is empty. unsafeHead :: Vector v a => v a -> a@@ -316,7 +333,7 @@ -- element) is evaluated eagerly. indexM :: (HasCallStack, Vector v a, Monad m) => v a -> Int -> m a {-# INLINE_FUSED indexM #-}-indexM v i = checkIndex Bounds i (length v) $ liftBox $ basicUnsafeIndexM v i+indexM v !i = checkIndex Bounds i (length v) $ liftBox $ basicUnsafeIndexM v i -- | /O(1)/ First element of a vector in a monad. See 'indexM' for an -- explanation of why this is useful.@@ -334,7 +351,7 @@ -- explanation of why this is useful. unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a {-# INLINE_FUSED unsafeIndexM #-}-unsafeIndexM v i = checkIndex Unsafe i (length v)+unsafeIndexM v !i = checkIndex Unsafe i (length v) $ liftBox $ basicUnsafeIndexM v i @@ -452,7 +469,8 @@ -> v a -> v a {-# INLINE_FUSED unsafeSlice #-}-unsafeSlice i n v = checkSlice Unsafe i n (length v) $ basicUnsafeSlice i n v+-- See NOTE: [Strict indexing]+unsafeSlice !i !n v = checkSlice Unsafe i n (length v) $ basicUnsafeSlice i n v -- | /O(1)/ Yield all but the last element without copying. The vector may not -- be empty, but this is not checked.@@ -787,7 +805,7 @@ -- ------------------------ -- | /O(n)/ Yield the argument, but force it not to retain any extra memory,--- possibly by copying it.+-- by copying it. -- -- This is especially useful when dealing with slices. For example: --@@ -880,7 +898,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.accum (+) (V.fromList [1000,2000,3000]) [(2,4),(1,6),(0,3),(1,10)] -- [1003,2016,3004] accum :: Vector v a@@ -896,7 +914,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.accumulate (+) (V.fromList [1000,2000,3000]) (V.fromList [(2,4),(1,6),(0,3),(1,10)]) -- [1003,2016,3004] accumulate :: (Vector v a, Vector v (Int, b))@@ -908,7 +926,7 @@ accumulate f v us = accum_stream f v (stream us) -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the--- corresponding value @b@ from the the value vector,+-- corresponding value @b@ from the value vector, -- replace the element of the initial vector at -- position @i@ by @f a b@. --@@ -993,7 +1011,7 @@ -- NOTE: we do it this way to avoid triggering LiberateCase on n in -- polymorphic code index :: HasCallStack => Int -> Box a- index i = checkIndex Bounds i n $ basicUnsafeIndexM v i+ index !i = checkIndex Bounds i n $ basicUnsafeIndexM v i -- | Same as 'backpermute', but without bounds checking. unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a@@ -1010,7 +1028,7 @@ {-# INLINE index #-} -- NOTE: we do it this way to avoid triggering LiberateCase on n in -- polymorphic code- index i = checkIndex Unsafe i n $ basicUnsafeIndexM v i+ index !i = checkIndex Unsafe i n $ basicUnsafeIndexM v i -- Safe destructive updates -- ------------------------@@ -1021,8 +1039,8 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V--- >>> import qualified Data.Vector.Mutable as MV+-- >>> import qualified Data.Vector.Strict as V+-- >>> import qualified Data.Vector.Strict.Mutable as MV -- >>> V.modify (\v -> MV.write v 0 'x') $ V.replicate 4 'a' -- "xaaa" modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a@@ -1381,7 +1399,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.uniq $ V.fromList [1,3,3,200,3] -- [1,3,200,3] -- >>> import Data.Semigroup@@ -1536,25 +1554,77 @@ -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy -- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Strict as V+-- >>> V.span (<4) $ V.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9]) span :: Vector v a => (a -> Bool) -> v a -> (v a, v a) {-# INLINE span #-} span f = break (not . f) -- | /O(n)/ Split the vector into the longest prefix of elements that do not -- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Strict as V+-- >>> V.break (>4) $ V.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9]) break :: Vector v a => (a -> Bool) -> v a -> (v a, v a) {-# INLINE break #-} break f xs = case findIndex f xs of Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs) Nothing -> (xs, empty) +-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Strict as V+-- >>> V.spanR (>4) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+spanR :: Vector v a => (a -> Bool) -> v a -> (v a, v a)+{-# INLINE spanR #-}+spanR f = breakR (not . f)++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since NEXT_VERSION+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Strict as V+-- >>> V.breakR (<5) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+breakR :: Vector v a => (a -> Bool) -> v a -> (v a, v a)+{-# INLINE breakR #-}+breakR f xs = case findIndexR f xs of+ Just i -> ( unsafeSlice (i+1) (length xs - i - 1) xs+ , unsafeSlice 0 (i+1) xs)+ Nothing -> (xs, empty)++++ -- | /O(n)/ Split a vector into a list of slices. -- -- The concatenation of this list of slices is equal to the argument vector, -- and each slice contains only equal elements, as determined by the equality -- predicate function. ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> import Data.Char (isUpper) -- >>> V.groupBy (\a b -> isUpper a == isUpper b) (V.fromList "Mississippi River") -- ["M","ississippi ","R","iver"]@@ -1579,7 +1649,7 @@ -- -- This is the equivalent of 'groupBy (==)'. ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.group (V.fromList "Mississippi") -- ["M","i","ss","i","ss","i","pp","i"] --@@ -1743,7 +1813,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.all even $ V.fromList [2, 4, 12] -- True -- >>> V.all even $ V.fromList [2, 4, 13]@@ -1758,7 +1828,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.any even $ V.fromList [1, 3, 7] -- False -- >>> V.any even $ V.fromList [3, 2, 13]@@ -1773,7 +1843,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.and $ V.fromList [True, False] -- False -- >>> V.and V.empty@@ -1786,7 +1856,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.or $ V.fromList [True, False] -- True -- >>> V.or V.empty@@ -1799,7 +1869,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.sum $ V.fromList [300,20,1] -- 321 -- >>> V.sum (V.empty :: V.Vector Int)@@ -1812,7 +1882,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.product $ V.fromList [1,2,3,4] -- 24 -- >>> V.product (V.empty :: V.Vector Int)@@ -1826,7 +1896,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.maximum $ V.fromList [2, 1] -- 2 -- >>> import Data.Semigroup@@ -1846,7 +1916,7 @@ -- ==== __Examples__ -- -- >>> import Data.Ord--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.maximumBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')] -- (2,'a') -- >>> V.maximumBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]@@ -1866,7 +1936,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.maximumOn fst $ V.fromList [(2,'a'), (1,'b')] -- (2,'a') -- >>> V.maximumOn fst $ V.fromList [(1,'a'), (1,'b')]@@ -1887,7 +1957,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.minimum $ V.fromList [2, 1] -- 1 -- >>> import Data.Semigroup@@ -1906,7 +1976,7 @@ -- ==== __Examples__ -- -- >>> import Data.Ord--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.minimumBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')] -- (1,'b') -- >>> V.minimumBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]@@ -1926,7 +1996,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.minimumOn fst $ V.fromList [(2,'a'), (1,'b')] -- (1,'b') -- >>> V.minimumOn fst $ V.fromList [(1,'a'), (1,'b')]@@ -1955,7 +2025,7 @@ -- ==== __Examples__ -- -- >>> import Data.Ord--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.maxIndexBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')] -- 0 -- >>> V.maxIndexBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]@@ -1981,7 +2051,7 @@ -- ==== __Examples__ -- -- >>> import Data.Ord--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.minIndexBy (comparing fst) $ V.fromList [(2,'a'), (1,'b')] -- 1 -- >>> V.minIndexBy (comparing fst) $ V.fromList [(1,'a'), (1,'b')]@@ -2090,7 +2160,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.prescanl (+) 0 (V.fromList [1,2,3,4]) -- [0,1,3,6] prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a@@ -2110,7 +2180,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.postscanl (+) 0 (V.fromList [1,2,3,4]) -- [1,3,6,10] postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a@@ -2130,7 +2200,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.scanl (+) 0 (V.fromList [1,2,3,4]) -- [0,1,3,6,10] scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a@@ -2169,7 +2239,7 @@ -- results in an error; instead it produces an empty vector. -- -- ==== __Examples__--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict 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]@@ -2186,7 +2256,7 @@ -- results in an error; instead it produces an empty vector. -- -- ==== __Examples__--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict 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]@@ -2257,7 +2327,7 @@ -- results in an error; instead it produces an empty vector. -- -- ==== __Examples__--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict 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]@@ -2275,7 +2345,7 @@ -- results in an error; instead it produces an empty vector. -- -- ==== __Examples__--- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict 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]@@ -2294,7 +2364,15 @@ {-# INLINE toList #-} toList = Bundle.toList . stream --- | /O(n)/ Convert a list to a vector.+-- | /O(n)/ Convert a list to a vector. During the operation, the +-- vector’s capacity will be doubling until the list's contents are +-- in the vector. Depending on the list’s size, up to half of the vector’s +-- capacity might be empty. If you’d rather avoid this, you can use +-- 'fromListN', which will provide the exact space the list requires but will +-- prevent list fusion, or @'force' . 'fromList'@, which will create the +-- vector and then copy it without the superfluous space.+--+-- @since 0.4 fromList :: Vector v a => [a] -> v a {-# INLINE fromList #-} fromList = unstream . Bundle.fromList@@ -2311,7 +2389,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Strict as V -- >>> V.fromListN 3 [1,2,3,4,5] -- [1,2,3] -- >>> V.fromListN 3 [1]@@ -2482,7 +2560,7 @@ {-# INLINE get #-} get 0 = Nothing- get i = let i' = i-1+ get i = let !i' = i-1 in case basicUnsafeIndexM v i' of Box x -> Just (x, i') @@ -2659,4 +2737,4 @@ -- $setup -- >>> :set -XFlexibleContexts -- >>> :set -Wno-type-defaults--- >>> import Prelude (Bool(True, False), even)+-- >>> import Prelude (Bool(True, False), even, Ord(..))
src/Data/Vector/Generic/Base.hs view
@@ -28,6 +28,9 @@ import Data.Vector.Generic.Mutable.Base ( MVector ) import qualified Data.Vector.Generic.Mutable.Base as M import Data.Vector.Fusion.Util (Box(..), liftBox)+import qualified Data.Primitive.Array as Prim+import qualified Data.Primitive.SmallArray as Prim+import qualified Data.Primitive.PrimArray as Prim import Control.Monad.ST import Data.Kind (Type)@@ -36,6 +39,11 @@ -- the state token @s@. It is injective on GHC 8 and newer. type family Mutable (v :: Type -> Type) = (mv :: Type -> Type -> Type) | mv -> v +type instance Mutable Prim.Array = Prim.MutableArray+type instance Mutable Prim.SmallArray = Prim.SmallMutableArray+type instance Mutable Prim.PrimArray = Prim.MutablePrimArray++ -- | Class of immutable vectors. Every immutable vector is associated with its -- mutable version through the 'Mutable' type family. Methods of this class -- should not be used directly. Instead, "Data.Vector.Generic" and other@@ -137,7 +145,7 @@ -- -- > elemseq v x y = (singleton x `asTypeOf` v) `seq` y --- -- Default defintion: @a@ is not evaluated at all.+ -- Default definition: @a@ is not evaluated at all. elemseq :: v a -> a -> b -> b {-# INLINE elemseq #-}
src/Data/Vector/Generic/Mutable.hs view
@@ -58,7 +58,8 @@ ifoldr, ifoldr', ifoldrM, ifoldrM', -- * Modifying vectors- nextPermutation,+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy, -- ** Filling and copying set, copy, move, unsafeCopy, unsafeMove,@@ -91,9 +92,10 @@ import Control.Monad.Primitive ( PrimMonad(..), RealWorld, stToPrim ) import Prelude- ( Ord, Monad, Bool(..), Int, Maybe(..), Either(..)+ ( Ord, Monad, Bool(..), Int, Maybe(..), Either(..), Ordering(..) , return, otherwise, flip, const, seq, min, max, not, pure- , (>>=), (+), (-), (<), (<=), (>=), (==), (/=), (.), ($), (=<<), (>>), (<$>) )+ , (>>=), (+), (-), (<), (<=), (>), (>=), (==), (/=), (.), ($), (=<<), (>>), (<$>) )+import Data.Bits ( Bits(shiftR) ) #include "vector.h" @@ -425,8 +427,9 @@ -> v s a -> v s a {-# INLINE unsafeSlice #-}-unsafeSlice i n v = checkSlice Unsafe i n (length v)- $ basicUnsafeSlice i n v+-- See NOTE: [Strict indexing] in D.V.Generic+unsafeSlice !i !n v = checkSlice Unsafe i n (length v)+ $ basicUnsafeSlice i n v -- | Same as 'init', but doesn't do range checks. unsafeInit :: MVector v a => v s a -> v s a@@ -638,7 +641,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector.Mutable as MV+-- >>> import qualified Data.Vector.Strict.Mutable as MV -- >>> v <- MV.generate 10 (\x -> x*x) -- >>> MV.read v 3 -- 9@@ -654,7 +657,7 @@ -- -- ==== __Examples__ ----- >>> import qualified Data.Vector.Mutable as MV+-- >>> import qualified Data.Vector.Strict.Mutable as MV -- >>> v <- MV.generate 10 (\x -> x*x) -- >>> MV.readMaybe v 3 -- Just 9@@ -700,24 +703,27 @@ -- | Yield the element at the given position. No bounds checks are performed. unsafeRead :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a {-# INLINE unsafeRead #-}-unsafeRead v i = checkIndex Unsafe i (length v)- $ stToPrim- $ basicUnsafeRead v i+-- See NOTE: [Strict indexing] in D.V.Generic+unsafeRead v !i = checkIndex Unsafe i (length v)+ $ stToPrim+ $ basicUnsafeRead v i -- | Replace the element at the given position. No bounds checks are performed. unsafeWrite :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m () {-# INLINE unsafeWrite #-}-unsafeWrite v i x = checkIndex Unsafe i (length v)- $ stToPrim- $ basicUnsafeWrite v i x+-- See NOTE: [Strict indexing] in D.V.Generic+unsafeWrite v !i x = checkIndex Unsafe i (length v)+ $ stToPrim+ $ basicUnsafeWrite v i x -- | Modify the element at the given position. No bounds checks are performed. unsafeModify :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> a) -> Int -> m () {-# INLINE unsafeModify #-}-unsafeModify v f i = checkIndex Unsafe i (length v)- $ stToPrim- $ basicUnsafeRead v i >>= \x ->- basicUnsafeWrite v i (f x)+-- See NOTE: [Strict indexing] in D.V.Generic+unsafeModify v f !i = checkIndex Unsafe i (length v)+ $ stToPrim+ $ basicUnsafeRead v i >>= \x ->+ basicUnsafeWrite v i (f x) -- | Modify the element at the given position using a monadic -- function. No bounds checks are performed.@@ -725,8 +731,9 @@ -- @since 0.12.3.0 unsafeModifyM :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> m a) -> Int -> m () {-# INLINE unsafeModifyM #-}-unsafeModifyM v f i = checkIndex Unsafe i (length v)- $ stToPrim . basicUnsafeWrite v i =<< f =<< stToPrim (basicUnsafeRead v i)+-- See NOTE: [Strict indexing] in D.V.Generic+unsafeModifyM v f !i = checkIndex Unsafe i (length v)+ $ stToPrim . basicUnsafeWrite v i =<< f =<< stToPrim (basicUnsafeRead v i) -- | Swap the elements at the given positions. No bounds checks are performed. unsafeSwap :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> Int -> m ()@@ -1208,6 +1215,47 @@ -- Modifying vectors -- ----------------- ++-- | Compute the (lexicographically) next permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+nextPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool+{-# INLINE nextPermutation #-}+nextPermutation = nextPermutationByLt (<)++-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy cmp = nextPermutationByLt (\x y -> cmp x y == LT)++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = nextPermutationByLt (>)++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy cmp = nextPermutationByLt (\x y -> cmp x y == GT)+ {- http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations @@ -1219,30 +1267,51 @@ 2. Find the largest index l greater than k such that a[k] < a[l]. 3. Swap the value of a[k] with that of a[l]. 4. Reverse the sequence from a[k + 1] up to and including the final element a[n]++The algorithm has been updated to look up the k in Step 1 beginning from the+last of the vector; which renders the algorithm to achieve the average time+complexity of O(1) each call. The worst case time complexity is still O(n).+The orginal implementation, which scanned the vector from the left, had the+time complexity of O(n) on the best case. -} -- | Compute the (lexicographically) next permutation of the given vector in-place.--- Returns False when the input is the last permutation.-nextPermutation :: (PrimMonad m,Ord e,MVector v e) => v (PrimState m) e -> m Bool-nextPermutation v- | dim < 2 = return False- | otherwise = do- val <- unsafeRead v 0- (k,l) <- loop val (-1) 0 val 1- if k < 0- then return False- else unsafeSwap v k l >>- reverse (unsafeSlice (k+1) (dim-k-1) v) >>- return True- where loop !kval !k !l !prev !i- | i == dim = return (k,l)- | otherwise = do- cur <- unsafeRead v i- -- TODO: make tuple unboxed- let (kval',k') = if prev < cur then (prev,i-1) else (kval,k)- l' = if kval' < cur then i else l- loop kval' k' l' cur (i+1)- dim = length v+-- Here, the first argument should be a less-than comparison function.+-- Returns False when the input is the last permutation; in this case the vector+-- will not get updated, as opposed to the behavior of the C++ function +-- @std::next_permutation@.+nextPermutationByLt :: (PrimMonad m, MVector v e) => (e -> e -> Bool) -> v (PrimState m) e -> m Bool+{-# INLINE nextPermutationByLt #-}+nextPermutationByLt lt v+ | dim < 2 = return False+ | otherwise = stToPrim $ do+ !vlast <- unsafeRead v (dim - 1)+ decrLoop (dim - 2) vlast+ where+ dim = length v+ -- find the largest index k such that a[k] < a[k + 1], and then pass to the rest.+ decrLoop !i !vi1 | i >= 0 = do+ !vi <- unsafeRead v i+ if vi `lt` vi1 then swapLoop i vi (i+1) vi1 dim else decrLoop (i-1) vi+ decrLoop _ !_ = return False+ -- find the largest index l greater than k such that a[k] < a[l], and do the rest.+ swapLoop !k !vk = go+ where+ -- binary search.+ go !l !vl !r | r - l <= 1 = do+ -- Done; do the rest of the algorithm.+ unsafeWrite v k vl+ unsafeWrite v l vk+ reverse $ unsafeSlice (k + 1) (dim - k - 1) v+ return True+ go !l !vl !r = do+ !vmid <- unsafeRead v mid+ if vk `lt` vmid+ then go mid vmid r+ else go l vl mid+ where+ !mid = l + (r - l) `shiftR` 1+ -- $setup -- >>> import Prelude ((*))
src/Data/Vector/Mutable.hs view
@@ -58,7 +58,8 @@ ifoldr, ifoldr', ifoldrM, ifoldrM', -- * Modifying vectors- nextPermutation,+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy, -- ** Filling and copying set, copy, move, unsafeCopy, unsafeMove,@@ -574,10 +575,44 @@ -- ----------------- -- | Compute the (lexicographically) next permutation of the given vector in-place.--- Returns False when the input is the last permutation.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@. nextPermutation :: (PrimMonad m, Ord e) => MVector (PrimState m) e -> m Bool {-# INLINE nextPermutation #-} nextPermutation = G.nextPermutation++-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: PrimMonad m => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy = G.nextPermutationBy++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m, Ord e) => MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = G.prevPermutation++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: PrimMonad m => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy = G.prevPermutationBy -- Folds -- -----
src/Data/Vector/Primitive.hs view
@@ -107,7 +107,7 @@ takeWhile, dropWhile, -- ** Partitioning- partition, unstablePartition, partitionWith, span, break, groupBy, group,+ partition, unstablePartition, partitionWith, span, break, spanR, breakR, groupBy, group, -- ** Searching elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,@@ -731,7 +731,7 @@ -- ------------------------ -- | /O(n)/ Yield the argument, but force it not to retain any extra memory,--- possibly by copying it.+-- by copying it. -- -- This is especially useful when dealing with slices. For example: --@@ -802,7 +802,7 @@ accum = G.accum -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the--- corresponding value @b@ from the the value vector,+-- corresponding value @b@ from the value vector, -- replace the element of the initial vector at -- position @i@ by @f a b@. --@@ -1156,16 +1156,62 @@ -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy -- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Primitive as VP+-- >>> VP.span (<4) $ VP.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9]) span :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE span #-} span = G.span -- | /O(n)/ Split the vector into the longest prefix of elements that do not -- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Primitive as VP+-- >>> VP.break (>4) $ VP.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9]) break :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE break #-} break = G.break +-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Primitive as VP+-- >>> VP.spanR (>4) $ VP.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+spanR :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE spanR #-}+spanR = G.spanR++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since NEXT_VERSION+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Primitive as VP+-- >>> VP.breakR (<5) $ VP.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+breakR :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE breakR #-}+breakR = G.breakR+ -- | /O(n)/ Split a vector into a list of slices, using a predicate function. -- -- The concatenation of this list of slices is equal to the argument vector,@@ -1790,7 +1836,15 @@ {-# INLINE toList #-} toList = G.toList --- | /O(n)/ Convert a list to a vector.+-- | /O(n)/ Convert a list to a vector. During the operation, the +-- vector’s capacity will be doubling until the list's contents are +-- in the vector. Depending on the list’s size, up to half of the vector’s +-- capacity might be empty. If you’d rather avoid this, you can use +-- 'fromListN', which will provide the exact space the list requires but will +-- prevent list fusion, or @'force' . 'fromList'@, which will create the +-- vector and then copy it without the superfluous space.+--+-- @since 0.4 fromList :: Prim a => [a] -> Vector a {-# INLINE fromList #-} fromList = G.fromList@@ -1894,4 +1948,4 @@ copy = G.copy -- $setup--- >>> import Prelude (($), min, even, max, succ)+-- >>> import Prelude (($), min, even, max, succ, id, Ord(..))
src/Data/Vector/Primitive/Mutable.hs view
@@ -57,7 +57,8 @@ ifoldr, ifoldr', ifoldrM, ifoldrM', -- * Modifying vectors- nextPermutation,+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy, -- ** Filling and copying set, copy, move, unsafeCopy, unsafeMove,@@ -83,7 +84,7 @@ ) import Prelude- ( Ord, Bool, Int, Maybe+ ( Ord, Bool, Int, Maybe, Ordering(..) , otherwise, error, undefined, div, show, maxBound , (+), (*), (<), (>), (>=), (==), (&&), (||), ($), (++) ) @@ -540,10 +541,44 @@ -- ----------------- -- | Compute the (lexicographically) next permutation of the given vector in-place.--- Returns False when the input is the last permutation.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@. nextPermutation :: (PrimMonad m,Ord e,Prim e) => MVector (PrimState m) e -> m Bool {-# INLINE nextPermutation #-} nextPermutation = G.nextPermutation++-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: (PrimMonad m,Prim e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy = G.nextPermutationBy++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m,Ord e,Prim e) => MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = G.prevPermutation++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: (PrimMonad m,Prim e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy = G.prevPermutationBy -- Folds -- -----
src/Data/Vector/Storable.hs view
@@ -104,7 +104,7 @@ takeWhile, dropWhile, -- ** Partitioning- partition, unstablePartition, partitionWith, span, break, groupBy, group,+ partition, unstablePartition, partitionWith, span, break, spanR, breakR, groupBy, group, -- ** Searching elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,@@ -742,7 +742,7 @@ -- ------------------------ -- | /O(n)/ Yield the argument, but force it not to retain any extra memory,--- possibly by copying it.+-- by copying it. -- -- This is especially useful when dealing with slices. For example: --@@ -813,7 +813,7 @@ accum = G.accum -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the--- corresponding value @b@ from the the value vector,+-- corresponding value @b@ from the value vector, -- replace the element of the initial vector at -- position @i@ by @f a b@. --@@ -1178,16 +1178,62 @@ -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy -- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Storable as VS+-- >>> VS.span (<4) $ VS.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9]) span :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE span #-} span = G.span -- | /O(n)/ Split the vector into the longest prefix of elements that do not -- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Storable as VS+-- >>> VS.break (>4) $ VS.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9]) break :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE break #-} break = G.break +-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Storable as VS+-- >>> VS.spanR (>4) $ VS.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+spanR :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE spanR #-}+spanR = G.spanR++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since NEXT_VERSION+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Storable as VS+-- >>> VS.breakR (<5) $ VS.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+breakR :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE breakR #-}+breakR = G.breakR+ -- | /O(n)/ Split a vector into a list of slices, using a predicate function. -- -- The concatenation of this list of slices is equal to the argument vector,@@ -1837,7 +1883,15 @@ {-# INLINE toList #-} toList = G.toList --- | /O(n)/ Convert a list to a vector.+-- | /O(n)/ Convert a list to a vector. During the operation, the +-- vector’s capacity will be doubling until the list's contents are +-- in the vector. Depending on the list’s size, up to half of the vector’s +-- capacity might be empty. If you’d rather avoid this, you can use +-- 'fromListN', which will provide the exact space the list requires but will +-- prevent list fusion, or @'force' . 'fromList'@, which will create the +-- vector and then copy it without the superfluous space.+--+-- @since 0.4 fromList :: Storable a => [a] -> Vector a {-# INLINE fromList #-} fromList = G.fromList@@ -1998,4 +2052,4 @@ unsafeWith (Vector _ fp) = withForeignPtr fp -- $setup--- >>> import Prelude (Bool(..), Double, ($), (+), (/), succ, even, min, max)+-- >>> import Prelude (Bool(..), Double, ($), (+), (/), succ, even, min, max, id, Ord(..))
src/Data/Vector/Storable/Mutable.hs view
@@ -58,7 +58,8 @@ ifoldr, ifoldr', ifoldrM, ifoldrM', -- * Modifying vectors- nextPermutation,+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy, -- ** Filling and copying set, copy, move, unsafeCopy, unsafeMove,@@ -101,7 +102,7 @@ import GHC.Ptr (Ptr(..)) import Prelude- ( Ord, Bool, Maybe, IO+ ( Ord, Bool, Maybe, IO, Ordering(..) , return, otherwise, error, undefined, max, div, quot, maxBound, show , (-), (*), (<), (>), (>=), (==), (&&), (||), (.), ($), (++) ) @@ -248,7 +249,7 @@ {- AFTER primitive 0.7 is pretty old, move to using setPtr. which is really-a confusing misnomer for whats often called memset (intialize)+a confusing misnomer for what's often called memset (initialize) -} -- Fill a memory block with the given value. The length is in -- elements of type @a@ rather than in bytes.@@ -641,10 +642,44 @@ -- ----------------- -- | Compute the (lexicographically) next permutation of the given vector in-place.--- Returns False when the input is the last permutation.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@. nextPermutation :: (PrimMonad m, Storable e, Ord e) => MVector (PrimState m) e -> m Bool {-# INLINE nextPermutation #-} nextPermutation = G.nextPermutation++-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: (PrimMonad m, Storable e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy = G.nextPermutationBy++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m, Storable e, Ord e) => MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = G.prevPermutation++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: (PrimMonad m, Storable e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy = G.prevPermutationBy -- Folds -- -----
+ src/Data/Vector/Strict.hs view
@@ -0,0 +1,2611 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+-- |+-- Module : Data.Vector.Strict+-- Copyright : (c) Roman Leshchinskiy 2008-2010+-- Alexey Kuleshevich 2020-2022+-- Aleksey Khudyakov 2020-2022+-- Andrew Lelechenko 2020-2022+-- License : BSD-style+--+-- Maintainer : Haskell Libraries Team <libraries@haskell.org>+-- Stability : experimental+-- Portability : non-portable+--+-- Immutable strict boxed vectors (that is, polymorphic arrays capable+-- of holding any Haskell value). Vectors created using API for+-- immutable vector will have all elements evaluated to WHNF. Note+-- it's possible to create vector containing bottoms using mutable API+-- ('Data.Vector.Strict.Mutable.new' initialize vector with ⊥) fill+-- but all subsequent writes will be evauated to WHNF.+--+-- For unboxed arrays, use "Data.Vector.Unboxed".+module Data.Vector.Strict (+ -- * Boxed vectors+ Vector, MVector,++ -- * Accessors++ -- ** Length information+ length, null,++ -- ** Indexing+ (!), (!?), head, last,+ unsafeIndex, unsafeHead, unsafeLast,++ -- ** Monadic indexing+ indexM, headM, lastM,+ unsafeIndexM, unsafeHeadM, unsafeLastM,++ -- ** Extracting subvectors (slicing)+ slice, init, tail, take, drop, splitAt, uncons, unsnoc,+ unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,++ -- * Construction++ -- ** Initialisation+ empty, singleton, replicate, generate, iterateN,++ -- ** Monadic initialisation+ replicateM, generateM, iterateNM, create, createT,++ -- ** Unfolding+ unfoldr, unfoldrN, unfoldrExactN,+ unfoldrM, unfoldrNM, unfoldrExactNM,+ constructN, constructrN,++ -- ** Enumeration+ enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,++ -- ** Concatenation+ cons, snoc, (++), concat,++ -- ** Restricting memory usage+ force,++ -- * Modifying vectors++ -- ** Bulk updates+ (//), update, update_,+ unsafeUpd, unsafeUpdate, unsafeUpdate_,++ -- ** Accumulations+ accum, accumulate, accumulate_,+ unsafeAccum, unsafeAccumulate, unsafeAccumulate_,++ -- ** Permutations+ reverse, backpermute, unsafeBackpermute,++ -- ** Safe destructive updates+ modify,++ -- * Elementwise operations++ -- ** Indexing+ indexed,++ -- ** Mapping+ map, imap, concatMap,++ -- ** Monadic mapping+ mapM, imapM, mapM_, imapM_, forM, forM_,+ iforM, iforM_,++ -- ** Zipping+ zipWith, zipWith3, zipWith4, zipWith5, zipWith6,+ izipWith, izipWith3, izipWith4, izipWith5, izipWith6,+ zip, zip3, zip4, zip5, zip6,++ -- ** Monadic zipping+ zipWithM, izipWithM, zipWithM_, izipWithM_,++ -- ** Unzipping+ unzip, unzip3, unzip4, unzip5, unzip6,++ -- * Working with predicates++ -- ** Filtering+ filter, ifilter, filterM, uniq,+ mapMaybe, imapMaybe,+ mapMaybeM, imapMaybeM,+ catMaybes,+ takeWhile, dropWhile,++ -- ** Partitioning+ partition, unstablePartition, partitionWith, span, break, spanR, breakR, groupBy, group,++ -- ** Searching+ elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,++ -- * Folding+ foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',+ ifoldl, ifoldl', ifoldr, ifoldr',+ foldMap, foldMap',++ -- ** Specialised folds+ all, any, and, or,+ sum, product,+ maximum, maximumBy, maximumOn,+ minimum, minimumBy, minimumOn,+ minIndex, minIndexBy, maxIndex, maxIndexBy,++ -- ** Monadic folds+ foldM, ifoldM, foldM', ifoldM',+ fold1M, fold1M',foldM_, ifoldM_,+ foldM'_, ifoldM'_, fold1M_, fold1M'_,++ -- ** Monadic sequencing+ sequence, sequence_,++ -- * Scans+ prescanl, prescanl',+ postscanl, postscanl',+ scanl, scanl', scanl1, scanl1',+ iscanl, iscanl',+ prescanr, prescanr',+ postscanr, postscanr',+ scanr, scanr', scanr1, scanr1',+ iscanr, iscanr',++ -- ** Comparisons+ eqBy, cmpBy,++ -- * Conversions++ -- ** Lists+ toList, Data.Vector.Strict.fromList, Data.Vector.Strict.fromListN,+ -- ** Lazy vectors+ toLazy, fromLazy,+ -- ** Arrays+ toArray, fromArray, toArraySlice, unsafeFromArraySlice,++ -- ** Other vector types+ G.convert,++ -- ** Mutable vectors+ freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy+) where++import Data.Coerce+import Data.Vector.Strict.Mutable ( MVector(..) )+import Data.Primitive.Array+import qualified Data.Vector.Fusion.Bundle as Bundle+import qualified Data.Vector.Generic as G+import qualified Data.Vector as V++import Control.DeepSeq ( NFData(rnf)+#if MIN_VERSION_deepseq(1,4,3)+ , NFData1(liftRnf)+#endif+ )++import Control.Monad ( MonadPlus(..), ap )+#if !MIN_VERSION_base(4,13,0)+import Control.Monad (fail)+#endif+import Control.Monad.ST ( ST, runST )+import Control.Monad.Primitive+import qualified Control.Monad.Fail as Fail+import Control.Monad.Fix ( MonadFix (mfix) )+import Control.Monad.Zip+import Data.Function ( fix )++import Prelude+ ( Eq(..), Ord(..), Num, Enum, Monoid, Functor, Monad, Show, Bool, Ordering(..), Int, Maybe, Either+ , return, showsPrec, fmap, otherwise, id, flip, const+ , (>>=), (+), (-), (.), ($), seq)++import Data.Functor.Classes (Eq1 (..), Ord1 (..), Read1 (..), Show1 (..))+import Data.Typeable ( Typeable )+import Data.Data ( Data(..) )+import Text.Read ( Read(..), readListPrecDefault )+import Data.Semigroup ( Semigroup(..) )++import qualified Control.Applicative as Applicative+import qualified Data.Foldable as Foldable+import qualified Data.Traversable as Traversable++import qualified GHC.Exts as Exts (IsList(..))+++-- | Strict boxed vectors, supporting efficient slicing.+newtype Vector a = Vector (V.Vector a)+ deriving (Typeable, Foldable.Foldable, Semigroup, Monoid)++-- NOTE: [GND for strict vector]+-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+--+-- Strict boxed vectors (both mutable an immutable) are newtypes over+-- lazy ones. This makes it possible to use GND to derive instances.+-- However one must take care to preserve strictness since Vector+-- instance for lazy vectors would be used.+--+-- In general it's OK to derive instances where vectors are passed as+-- parameters (e.g. Eq, Ord) and not OK to derive ones where new+-- vector is created (e.g. Read, Functor)++liftRnfV :: (a -> ()) -> Vector a -> ()+liftRnfV elemRnf = foldl' (\_ -> elemRnf) ()++instance NFData a => NFData (Vector a) where+ rnf = liftRnfV rnf+ {-# INLINEABLE rnf #-}++#if MIN_VERSION_deepseq(1,4,3)+-- | @since 0.13.2.0+instance NFData1 Vector where+ liftRnf = liftRnfV+ {-# INLINEABLE liftRnf #-}+#endif++instance Show a => Show (Vector a) where+ showsPrec = G.showsPrec++instance Read a => Read (Vector a) where+ readPrec = G.readPrec+ readListPrec = readListPrecDefault++instance Show1 Vector where+ liftShowsPrec = G.liftShowsPrec++instance Read1 Vector where+ liftReadsPrec = G.liftReadsPrec++instance Exts.IsList (Vector a) where+ type Item (Vector a) = a+ fromList = Data.Vector.Strict.fromList+ fromListN = Data.Vector.Strict.fromListN+ toList = toList++instance Data a => Data (Vector a) where+ gfoldl = G.gfoldl+ toConstr _ = G.mkVecConstr "Data.Vector.Strict.Vector"+ gunfold = G.gunfold+ dataTypeOf _ = G.mkVecType "Data.Vector.Strict.Vector"+ dataCast1 = G.dataCast++type instance G.Mutable Vector = MVector++instance G.Vector Vector a where+ {-# INLINE basicUnsafeFreeze #-}+ basicUnsafeFreeze = coerce (G.basicUnsafeFreeze @V.Vector @a)+ {-# INLINE basicUnsafeThaw #-}+ basicUnsafeThaw = coerce (G.basicUnsafeThaw @V.Vector @a)+ {-# INLINE basicLength #-}+ basicLength = coerce (G.basicLength @V.Vector @a)+ {-# INLINE basicUnsafeSlice #-}+ basicUnsafeSlice = coerce (G.basicUnsafeSlice @V.Vector @a)+ {-# INLINE basicUnsafeIndexM #-}+ basicUnsafeIndexM = coerce (G.basicUnsafeIndexM @V.Vector @a)+ {-# INLINE basicUnsafeCopy #-}+ basicUnsafeCopy = coerce (G.basicUnsafeCopy @V.Vector @a)+ {-# INLINE elemseq #-}+ elemseq _ = seq++-- See NOTE: [GND for strict vector]+--+-- Deriving strategies are only available since 8.2. So we can't use+-- deriving newtype until we drop support for 8.0+instance Eq a => Eq (Vector a) where+ {-# INLINE (==) #-}+ (==) = coerce ((==) @(V.Vector a))++-- See NOTE: [GND for strict vector]+instance Ord a => Ord (Vector a) where+ {-# INLINE compare #-}+ compare = coerce (compare @(V.Vector a))+ {-# INLINE (<) #-}+ (<) = coerce ((<) @(V.Vector a))+ {-# INLINE (<=) #-}+ (<=) = coerce ((<=) @(V.Vector a))+ {-# INLINE (>) #-}+ (>) = coerce ((>) @(V.Vector a))+ {-# INLINE (>=) #-}+ (>=) = coerce ((>=) @(V.Vector a))++instance Eq1 Vector where+ liftEq eq xs ys = Bundle.eqBy eq (G.stream xs) (G.stream ys)++instance Ord1 Vector where+ liftCompare cmp xs ys = Bundle.cmpBy cmp (G.stream xs) (G.stream ys)++instance Functor Vector where+ {-# INLINE fmap #-}+ fmap = map++ {-# INLINE (<$) #-}+ (<$) = map . const++instance Monad Vector where+ {-# INLINE return #-}+ return = Applicative.pure++ {-# INLINE (>>=) #-}+ (>>=) = flip concatMap++#if !(MIN_VERSION_base(4,13,0))+ {-# INLINE fail #-}+ fail = Fail.fail -- == \ _str -> empty+#endif++-- | @since 0.13.2.0+instance Fail.MonadFail Vector where+ {-# INLINE fail #-}+ fail _ = empty++instance MonadPlus Vector where+ {-# INLINE mzero #-}+ mzero = empty++ {-# INLINE mplus #-}+ mplus = (++)++instance MonadZip Vector where+ {-# INLINE mzip #-}+ mzip = zip++ {-# INLINE mzipWith #-}+ mzipWith = zipWith++ {-# INLINE munzip #-}+ munzip = unzip++-- | This instance has the same semantics as the one for lists.+--+-- @since 0.13.2.0+instance MonadFix Vector where+ -- We take care to dispose of v0 as soon as possible (see headM docs).+ --+ -- It's perfectly safe to use non-monadic indexing within generate+ -- call since intermediate vector won't be created until result's+ -- value is demanded.+ {-# INLINE mfix #-}+ mfix f+ | null v0 = empty+ -- We take first element of resulting vector from v0 and create+ -- rest using generate. Note that cons should fuse with generate+ | otherwise = runST $ do+ h <- headM v0+ return $ cons h $+ generate (lv0 - 1) $+ \i -> fix (\a -> f a ! (i + 1))+ where+ -- Used to calculate size of resulting vector+ v0 = fix (f . head)+ !lv0 = length v0++instance Applicative.Applicative Vector where+ {-# INLINE pure #-}+ pure = singleton++ {-# INLINE (<*>) #-}+ (<*>) = ap++instance Applicative.Alternative Vector where+ {-# INLINE empty #-}+ empty = empty++ {-# INLINE (<|>) #-}+ (<|>) = (++)++instance Traversable.Traversable Vector where+ {-# INLINE traverse #-}+ traverse f xs =+ -- Get the length of the vector in /O(1)/ time+ let !n = G.length xs+ -- Use fromListN to be more efficient in construction of resulting vector+ -- Also behaves better with compact regions, preventing runtime exceptions+ in Data.Vector.Strict.fromListN n Applicative.<$> Traversable.traverse f (toList xs)++ {-# INLINE mapM #-}+ mapM = mapM++ {-# INLINE sequence #-}+ sequence = sequence++-- Length information+-- ------------------++-- | /O(1)/ Yield the length of the vector.+--+-- @since 0.13.2.0+length :: Vector a -> Int+{-# INLINE length #-}+length = G.length++-- | /O(1)/ Test whether a vector is empty.+--+-- @since 0.13.2.0+null :: Vector a -> Bool+{-# INLINE null #-}+null = G.null++-- Indexing+-- --------++-- | O(1) Indexing.+--+-- @since 0.13.2.0+(!) :: Vector a -> Int -> a+{-# INLINE (!) #-}+(!) = (G.!)++-- | O(1) Safe indexing.+--+-- @since 0.13.2.0+(!?) :: Vector a -> Int -> Maybe a+{-# INLINE (!?) #-}+(!?) = (G.!?)++-- | /O(1)/ First element.+--+-- @since 0.13.2.0+head :: Vector a -> a+{-# INLINE head #-}+head = G.head++-- | /O(1)/ Last element.+--+-- @since 0.13.2.0+last :: Vector a -> a+{-# INLINE last #-}+last = G.last++-- | /O(1)/ Unsafe indexing without bounds checking.+--+-- @since 0.13.2.0+unsafeIndex :: Vector a -> Int -> a+{-# INLINE unsafeIndex #-}+unsafeIndex = G.unsafeIndex++-- | /O(1)/ First element, without checking if the vector is empty.+--+-- @since 0.13.2.0+unsafeHead :: Vector a -> a+{-# INLINE unsafeHead #-}+unsafeHead = G.unsafeHead++-- | /O(1)/ Last element, without checking if the vector is empty.+--+-- @since 0.13.2.0+unsafeLast :: Vector a -> a+{-# INLINE unsafeLast #-}+unsafeLast = G.unsafeLast++-- Monadic indexing+-- ----------------++-- | /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.+--+-- @since 0.13.2.0+indexM :: Monad m => Vector a -> Int -> m a+{-# INLINE indexM #-}+indexM = G.indexM++-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+--+-- @since 0.13.2.0+headM :: Monad m => Vector a -> m a+{-# INLINE headM #-}+headM = G.headM++-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+--+-- @since 0.13.2.0+lastM :: Monad m => Vector a -> m a+{-# INLINE lastM #-}+lastM = G.lastM++-- | /O(1)/ Indexing in a monad, without bounds checks. See 'indexM' for an+-- explanation of why this is useful.+--+-- @since 0.13.2.0+unsafeIndexM :: Monad m => Vector a -> Int -> m a+{-# INLINE unsafeIndexM #-}+unsafeIndexM = G.unsafeIndexM++-- | /O(1)/ First element in a monad, without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+--+-- @since 0.13.2.0+unsafeHeadM :: Monad m => Vector a -> m a+{-# INLINE unsafeHeadM #-}+unsafeHeadM = G.unsafeHeadM++-- | /O(1)/ Last element in a monad, without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+--+-- @since 0.13.2.0+unsafeLastM :: Monad m => Vector a -> m a+{-# INLINE unsafeLastM #-}+unsafeLastM = G.unsafeLastM++-- Extracting subvectors (slicing)+-- -------------------------------++-- | /O(1)/ Yield a slice of the vector without copying it. The vector must+-- contain at least @i+n@ elements.+--+-- @since 0.13.2.0+slice :: Int -- ^ @i@ starting index+ -> Int -- ^ @n@ length+ -> Vector a+ -> Vector a+{-# INLINE slice #-}+slice = G.slice++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty.+--+-- @since 0.13.2.0+init :: Vector a -> Vector a+{-# INLINE init #-}+init = G.init++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty.+--+-- @since 0.13.2.0+tail :: Vector a -> Vector a+{-# INLINE tail #-}+tail = G.tail++-- | /O(1)/ Yield at the first @n@ elements without copying. The vector may+-- contain less than @n@ elements, in which case it is returned unchanged.+--+-- @since 0.13.2.0+take :: Int -> Vector a -> Vector a+{-# INLINE take #-}+take = G.take++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may+-- contain less than @n@ elements, in which case an empty vector is returned.+--+-- @since 0.13.2.0+drop :: Int -> Vector a -> Vector a+{-# INLINE drop #-}+drop = G.drop++-- | /O(1)/ Yield the first @n@ elements paired with the remainder, without copying.+--+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@,+-- but slightly more efficient.+--+-- @since 0.13.2.0+splitAt :: Int -> Vector a -> (Vector a, Vector a)+{-# INLINE splitAt #-}+splitAt = G.splitAt++-- | /O(1)/ Yield the 'head' and 'tail' of the vector, or 'Nothing' if+-- the vector is empty.+--+-- @since 0.13.2.0+uncons :: Vector a -> Maybe (a, Vector a)+{-# INLINE uncons #-}+uncons = G.uncons++-- | /O(1)/ Yield the 'last' and 'init' of the vector, or 'Nothing' if+-- the vector is empty.+--+-- @since 0.13.2.0+unsnoc :: Vector a -> Maybe (Vector a, a)+{-# INLINE unsnoc #-}+unsnoc = G.unsnoc++-- | /O(1)/ Yield a slice of the vector without copying. The vector must+-- contain at least @i+n@ elements, but this is not checked.+--+-- @since 0.13.2.0+unsafeSlice :: Int -- ^ @i@ starting index+ -> Int -- ^ @n@ length+ -> Vector a+ -> Vector a+{-# INLINE unsafeSlice #-}+unsafeSlice = G.unsafeSlice++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty, but this is not checked.+--+-- @since 0.13.2.0+unsafeInit :: Vector a -> Vector a+{-# INLINE unsafeInit #-}+unsafeInit = G.unsafeInit++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty, but this is not checked.+--+-- @since 0.13.2.0+unsafeTail :: Vector a -> Vector a+{-# INLINE unsafeTail #-}+unsafeTail = G.unsafeTail++-- | /O(1)/ Yield the first @n@ elements without copying. The vector must+-- contain at least @n@ elements, but this is not checked.+--+-- @since 0.13.2.0+unsafeTake :: Int -> Vector a -> Vector a+{-# INLINE unsafeTake #-}+unsafeTake = G.unsafeTake++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector+-- must contain at least @n@ elements, but this is not checked.+--+-- @since 0.13.2.0+unsafeDrop :: Int -> Vector a -> Vector a+{-# INLINE unsafeDrop #-}+unsafeDrop = G.unsafeDrop++-- Initialisation+-- --------------++-- | /O(1)/ The empty vector.+--+-- @since 0.13.2.0+empty :: Vector a+{-# INLINE empty #-}+empty = G.empty++-- | /O(1)/ A vector with exactly one element.+--+-- @since 0.13.2.0+singleton :: a -> Vector a+{-# INLINE singleton #-}+singleton = G.singleton++-- | /O(n)/ A vector of the given length with the same value in each position.+--+-- @since 0.13.2.0+replicate :: Int -> a -> Vector a+{-# INLINE replicate #-}+replicate = G.replicate++-- | /O(n)/ Construct a vector of the given length by applying the function to+-- each index.+--+-- @since 0.13.2.0+generate :: Int -> (Int -> a) -> Vector a+{-# INLINE generate #-}+generate = G.generate++-- | /O(n)/ Apply the function \(\max(n - 1, 0)\) times to an initial value, producing a vector+-- of length \(\max(n, 0)\). The 0th element will contain the initial value, which is why there+-- is one less function application than the number of elements in the produced vector.+--+-- \( \underbrace{x, f (x), f (f (x)), \ldots}_{\max(0,n)\rm{~elements}} \)+--+-- ===__Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.iterateN 0 undefined undefined :: V.Vector String+-- []+-- >>> V.iterateN 4 (\x -> x <> x) "Hi"+-- ["Hi","HiHi","HiHiHiHi","HiHiHiHiHiHiHiHi"]+--+-- @since 0.13.2.0+iterateN :: Int -> (a -> a) -> a -> Vector a+{-# INLINE iterateN #-}+iterateN = G.iterateN++-- Unfolding+-- ---------++-- | /O(n)/ Construct a vector by repeatedly applying the generator function+-- to a seed. The generator function yields 'Just' the next element and the+-- new seed or 'Nothing' if there are no more elements.+--+-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10+-- > = <10,9,8,7,6,5,4,3,2,1>+--+-- @since 0.13.2.0+unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a+{-# INLINE unfoldr #-}+unfoldr = G.unfoldr++-- | /O(n)/ Construct a vector with at most @n@ elements by repeatedly applying+-- the generator function to a seed. The generator function yields 'Just' the+-- next element and the new seed or 'Nothing' if there are no more elements.+--+-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>+--+-- @since 0.13.2.0+unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a+{-# INLINE unfoldrN #-}+unfoldrN = G.unfoldrN++-- | /O(n)/ Construct a vector with exactly @n@ elements by repeatedly applying+-- the generator function to a seed. The generator function yields the+-- next element and the new seed.+--+-- > unfoldrExactN 3 (\n -> (n,n-1)) 10 = <10,9,8>+--+-- @since 0.13.2.0+unfoldrExactN :: Int -> (b -> (a, b)) -> b -> Vector a+{-# INLINE unfoldrExactN #-}+unfoldrExactN = G.unfoldrExactN++-- | /O(n)/ Construct a vector by repeatedly applying the monadic+-- generator function to a seed. The generator function yields 'Just'+-- the next element and the new seed or 'Nothing' if there are no more+-- elements.+--+-- @since 0.13.2.0+unfoldrM :: (Monad m) => (b -> m (Maybe (a, b))) -> b -> m (Vector a)+{-# INLINE unfoldrM #-}+unfoldrM = G.unfoldrM++-- | /O(n)/ Construct a vector by repeatedly applying the monadic+-- generator function to a seed. The generator function yields 'Just'+-- the next element and the new seed or 'Nothing' if there are no more+-- elements.+--+-- @since 0.13.2.0+unfoldrNM :: (Monad m) => Int -> (b -> m (Maybe (a, b))) -> b -> m (Vector a)+{-# INLINE unfoldrNM #-}+unfoldrNM = G.unfoldrNM++-- | /O(n)/ Construct a vector with exactly @n@ elements by repeatedly+-- applying the monadic generator function to a seed. The generator+-- function yields the next element and the new seed.+--+-- @since 0.13.2.0+unfoldrExactNM :: (Monad m) => Int -> (b -> m (a, b)) -> b -> m (Vector a)+{-# INLINE unfoldrExactNM #-}+unfoldrExactNM = G.unfoldrExactNM++-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the+-- generator function to the already constructed part of the vector.+--+-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in <a,b,c>+--+-- @since 0.13.2.0+constructN :: Int -> (Vector a -> a) -> Vector a+{-# INLINE constructN #-}+constructN = G.constructN++-- | /O(n)/ Construct a vector with @n@ elements from right to left by+-- repeatedly applying the generator function to the already constructed part+-- of the vector.+--+-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in <c,b,a>+--+-- @since 0.13.2.0+constructrN :: Int -> (Vector a -> a) -> Vector a+{-# INLINE constructrN #-}+constructrN = G.constructrN++-- Enumeration+-- -----------++-- | /O(n)/ Yield a vector of the given length, containing the values @x@, @x+1@+-- etc. This operation is usually more efficient than 'enumFromTo'.+--+-- > enumFromN 5 3 = <5,6,7>+--+-- @since 0.13.2.0+enumFromN :: Num a => a -> Int -> Vector a+{-# INLINE enumFromN #-}+enumFromN = G.enumFromN++-- | /O(n)/ Yield a vector of the given length, containing the values @x@, @x+y@,+-- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'.+--+-- > enumFromStepN 1 2 5 = <1,3,5,7,9>+--+-- @since 0.13.2.0+enumFromStepN :: Num a => a -> a -> Int -> Vector a+{-# INLINE enumFromStepN #-}+enumFromStepN = G.enumFromStepN++-- | /O(n)/ Enumerate values from @x@ to @y@.+--+-- /WARNING:/ This operation can be very inefficient. If possible, use+-- 'enumFromN' instead.+--+-- @since 0.13.2.0+enumFromTo :: Enum a => a -> a -> Vector a+{-# INLINE enumFromTo #-}+enumFromTo = G.enumFromTo++-- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@.+--+-- /WARNING:/ This operation can be very inefficient. If possible, use+-- 'enumFromStepN' instead.+--+-- @since 0.13.2.0+enumFromThenTo :: Enum a => a -> a -> a -> Vector a+{-# INLINE enumFromThenTo #-}+enumFromThenTo = G.enumFromThenTo++-- Concatenation+-- -------------++-- | /O(n)/ Prepend an element.+--+-- @since 0.13.2.0+cons :: a -> Vector a -> Vector a+{-# INLINE cons #-}+cons = G.cons++-- | /O(n)/ Append an element.+--+-- @since 0.13.2.0+snoc :: Vector a -> a -> Vector a+{-# INLINE snoc #-}+snoc = G.snoc++infixr 5 +++-- | /O(m+n)/ Concatenate two vectors.+--+-- @since 0.13.2.0+(++) :: Vector a -> Vector a -> Vector a+{-# INLINE (++) #-}+(++) = (G.++)++-- | /O(n)/ Concatenate all vectors in the list.+--+-- @since 0.13.2.0+concat :: [Vector a] -> Vector a+{-# INLINE concat #-}+concat = G.concat++-- Monadic initialisation+-- ----------------------++-- | /O(n)/ Execute the monadic action the given number of times and store the+-- results in a vector.+--+-- @since 0.13.2.0+replicateM :: Monad m => Int -> m a -> m (Vector a)+{-# INLINE replicateM #-}+replicateM = G.replicateM++-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index.+--+-- @since 0.13.2.0+generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)+{-# INLINE generateM #-}+generateM = G.generateM++-- | /O(n)/ Apply the monadic function \(\max(n - 1, 0)\) times to an initial value, producing a vector+-- of length \(\max(n, 0)\). The 0th element will contain the initial value, which is why there+-- is one less function application than the number of elements in the produced vector.+--+-- For a non-monadic version, see `iterateN`.+--+-- @since 0.13.2.0+iterateNM :: Monad m => Int -> (a -> m a) -> a -> m (Vector a)+{-# INLINE iterateNM #-}+iterateNM = G.iterateNM++-- | Execute the monadic action and freeze the resulting vector.+--+-- @+-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\'; return v }) = \<'a','b'\>+-- @+--+-- @since 0.13.2.0+create :: (forall s. ST s (MVector s a)) -> Vector a+{-# INLINE create #-}+-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120+create p = G.create p++-- | Execute the monadic action and freeze the resulting vectors.+--+-- @since 0.13.2.0+createT :: Traversable.Traversable f => (forall s. ST s (f (MVector s a))) -> f (Vector a)+{-# INLINE createT #-}+createT p = G.createT p++++-- Restricting memory usage+-- ------------------------++-- | /O(n)/ Yield the argument, but force it not to retain any extra memory,+-- by copying it.+--+-- This is especially useful when dealing with slices. For example:+--+-- > force (slice 0 2 <huge vector>)+--+-- Here, the slice retains a reference to the huge vector. Forcing it creates+-- a copy of just the elements that belong to the slice and allows the huge+-- vector to be garbage collected.+--+-- @since 0.13.2.0+force :: Vector a -> Vector a+{-# INLINE force #-}+force = G.force++-- Bulk updates+-- ------------++-- | /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>+--+-- @since 0.13.2.0+(//) :: Vector a -- ^ initial vector (of length @m@)+ -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)+ -> Vector a+{-# INLINE (//) #-}+(//) = (G.//)++-- | /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>+--+-- @since 0.13.2.0+update :: Vector a -- ^ initial vector (of length @m@)+ -> Vector (Int, a) -- ^ vector of index/value pairs (of length @n@)+ -> Vector a+{-# INLINE update #-}+update = G.update++-- | /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)+-- @+--+-- @since 0.13.2.0+update_ :: Vector a -- ^ initial vector (of length @m@)+ -> Vector Int -- ^ index vector (of length @n1@)+ -> Vector a -- ^ value vector (of length @n2@)+ -> Vector a+{-# INLINE update_ #-}+update_ = G.update_++-- | Same as ('//'), but without bounds checking.+--+-- @since 0.13.2.0+unsafeUpd :: Vector a -> [(Int, a)] -> Vector a+{-# INLINE unsafeUpd #-}+unsafeUpd = G.unsafeUpd++-- | Same as 'update', but without bounds checking.+--+-- @since 0.13.2.0+unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a+{-# INLINE unsafeUpdate #-}+unsafeUpdate = G.unsafeUpdate++-- | Same as 'update_', but without bounds checking.+--+-- @since 0.13.2.0+unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a+{-# INLINE unsafeUpdate_ #-}+unsafeUpdate_ = G.unsafeUpdate_++-- Accumulations+-- -------------++-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element+-- @a@ at position @i@ by @f a b@.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.accum (+) (V.fromList [1000,2000,3000]) [(2,4),(1,6),(0,3),(1,10)]+-- [1003,2016,3004]+--+-- @since 0.13.2.0+accum :: (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+{-# INLINE accum #-}+accum = G.accum++-- | /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__+--+-- >>> 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]+--+-- @since 0.13.2.0+accumulate :: (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+{-# INLINE accumulate #-}+accumulate = G.accumulate++-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the+-- corresponding value @b@ from 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)+-- @+--+-- @since 0.13.2.0+accumulate_ :: (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+{-# INLINE accumulate_ #-}+accumulate_ = G.accumulate_++-- | Same as 'accum', but without bounds checking.+--+-- @since 0.13.2.0+unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a+{-# INLINE unsafeAccum #-}+unsafeAccum = G.unsafeAccum++-- | Same as 'accumulate', but without bounds checking.+--+-- @since 0.13.2.0+unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a+{-# INLINE unsafeAccumulate #-}+unsafeAccumulate = G.unsafeAccumulate++-- | Same as 'accumulate_', but without bounds checking.+--+-- @since 0.13.2.0+unsafeAccumulate_+ :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a+{-# INLINE unsafeAccumulate_ #-}+unsafeAccumulate_ = G.unsafeAccumulate_++-- Permutations+-- ------------++-- | /O(n)/ Reverse a vector.+--+-- @since 0.13.2.0+reverse :: Vector a -> Vector a+{-# INLINE reverse #-}+reverse = G.reverse++-- | /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>+--+-- @since 0.13.2.0+backpermute :: Vector a -> Vector Int -> Vector a+{-# INLINE backpermute #-}+backpermute = G.backpermute++-- | Same as 'backpermute', but without bounds checking.+--+-- @since 0.13.2.0+unsafeBackpermute :: Vector a -> Vector Int -> Vector a+{-# INLINE unsafeBackpermute #-}+unsafeBackpermute = G.unsafeBackpermute++-- Safe destructive updates+-- ------------------------++-- | Apply a destructive operation to a vector. The operation may be+-- performed in place if it is safe to do so and will modify a copy of the+-- vector otherwise (see 'Data.Vector.Generic.New.New' for details).+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Mutable as MV+-- >>> V.modify (\v -> MV.write v 0 'x') $ V.replicate 4 'a'+-- "xaaa"+--+-- @since 0.13.2.0+modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a+{-# INLINE modify #-}+modify p = G.modify p++-- Indexing+-- --------++-- | /O(n)/ Pair each element in a vector with its index.+--+-- @since 0.13.2.0+indexed :: Vector a -> Vector (Int,a)+{-# INLINE indexed #-}+indexed = G.indexed++-- Mapping+-- -------++-- | /O(n)/ Map a function over a vector.+--+-- @since 0.13.2.0+map :: (a -> b) -> Vector a -> Vector b+{-# INLINE map #-}+map = G.map++-- | /O(n)/ Apply a function to every element of a vector and its index.+--+-- @since 0.13.2.0+imap :: (Int -> a -> b) -> Vector a -> Vector b+{-# INLINE imap #-}+imap = G.imap++-- | Map a function over a vector and concatenate the results.+--+-- @since 0.13.2.0+concatMap :: (a -> Vector b) -> Vector a -> Vector b+{-# INLINE concatMap #-}+concatMap = G.concatMap++-- Monadic mapping+-- ---------------++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results.+--+-- @since 0.13.2.0+mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)+{-# INLINE mapM #-}+mapM = G.mapM++-- | /O(n)/ Apply the monadic action to every element of a vector and its+-- index, yielding a vector of results.+--+-- @since 0.13.2.0+imapM :: Monad m => (Int -> a -> m b) -> Vector a -> m (Vector b)+{-# INLINE imapM #-}+imapM = G.imapM++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results.+--+-- @since 0.13.2.0+mapM_ :: Monad m => (a -> m b) -> Vector a -> m ()+{-# INLINE mapM_ #-}+mapM_ = G.mapM_++-- | /O(n)/ Apply the monadic action to every element of a vector and its+-- index, ignoring the results.+--+-- @since 0.13.2.0+imapM_ :: Monad m => (Int -> a -> m b) -> Vector a -> m ()+{-# INLINE imapM_ #-}+imapM_ = G.imapM_++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results. Equivalent to @flip 'mapM'@.+--+-- @since 0.13.2.0+forM :: Monad m => Vector a -> (a -> m b) -> m (Vector b)+{-# INLINE forM #-}+forM = G.forM++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results. Equivalent to @flip 'mapM_'@.+--+-- @since 0.13.2.0+forM_ :: Monad m => Vector a -> (a -> m b) -> m ()+{-# INLINE forM_ #-}+forM_ = G.forM_++-- | /O(n)/ Apply the monadic action to all elements of the vector and their indices, yielding a+-- vector of results. Equivalent to @'flip' 'imapM'@.+--+-- @since 0.13.2.0+iforM :: Monad m => Vector a -> (Int -> a -> m b) -> m (Vector b)+{-# INLINE iforM #-}+iforM = G.iforM++-- | /O(n)/ Apply the monadic action to all elements of the vector and their indices+-- and ignore the results. Equivalent to @'flip' 'imapM_'@.+--+-- @since 0.13.2.0+iforM_ :: Monad m => Vector a -> (Int -> a -> m b) -> m ()+{-# INLINE iforM_ #-}+iforM_ = G.iforM_++-- Zipping+-- -------++-- | /O(min(m,n))/ Zip two vectors with the given function.+--+-- @since 0.13.2.0+zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c+{-# INLINE zipWith #-}+zipWith = G.zipWith++-- | Zip three vectors with the given function.+--+-- @since 0.13.2.0+zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d+{-# INLINE zipWith3 #-}+zipWith3 = G.zipWith3++zipWith4 :: (a -> b -> c -> d -> e)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+{-# INLINE zipWith4 #-}+zipWith4 = G.zipWith4++zipWith5 :: (a -> b -> c -> d -> e -> f)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+ -> Vector f+{-# INLINE zipWith5 #-}+zipWith5 = G.zipWith5++zipWith6 :: (a -> b -> c -> d -> e -> f -> g)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+ -> Vector f -> Vector g+{-# INLINE zipWith6 #-}+zipWith6 = G.zipWith6++-- | /O(min(m,n))/ Zip two vectors with a function that also takes the+-- elements' indices.+--+-- @since 0.13.2.0+izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c+{-# INLINE izipWith #-}+izipWith = G.izipWith++-- | Zip three vectors and their indices with the given function.+--+-- @since 0.13.2.0+izipWith3 :: (Int -> a -> b -> c -> d)+ -> Vector a -> Vector b -> Vector c -> Vector d+{-# INLINE izipWith3 #-}+izipWith3 = G.izipWith3++izipWith4 :: (Int -> a -> b -> c -> d -> e)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+{-# INLINE izipWith4 #-}+izipWith4 = G.izipWith4++izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+ -> Vector f+{-# INLINE izipWith5 #-}+izipWith5 = G.izipWith5++izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)+ -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e+ -> Vector f -> Vector g+{-# INLINE izipWith6 #-}+izipWith6 = G.izipWith6++-- | /O(min(m,n))/ Zip two vectors.+--+-- @since 0.13.2.0+zip :: Vector a -> Vector b -> Vector (a, b)+{-# INLINE zip #-}+zip = G.zip++-- | Zip together three vectors into a vector of triples.+--+-- @since 0.13.2.0+zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)+{-# INLINE zip3 #-}+zip3 = G.zip3++zip4 :: Vector a -> Vector b -> Vector c -> Vector d+ -> Vector (a, b, c, d)+{-# INLINE zip4 #-}+zip4 = G.zip4++zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e+ -> Vector (a, b, c, d, e)+{-# INLINE zip5 #-}+zip5 = G.zip5++zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f+ -> Vector (a, b, c, d, e, f)+{-# INLINE zip6 #-}+zip6 = G.zip6++-- Unzipping+-- ---------++-- | /O(min(m,n))/ Unzip a vector of pairs.+--+-- @since 0.13.2.0+unzip :: Vector (a, b) -> (Vector a, Vector b)+{-# INLINE unzip #-}+unzip = G.unzip++unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)+{-# INLINE unzip3 #-}+unzip3 = G.unzip3++unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)+{-# INLINE unzip4 #-}+unzip4 = G.unzip4++unzip5 :: Vector (a, b, c, d, e)+ -> (Vector a, Vector b, Vector c, Vector d, Vector e)+{-# INLINE unzip5 #-}+unzip5 = G.unzip5++unzip6 :: Vector (a, b, c, d, e, f)+ -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)+{-# INLINE unzip6 #-}+unzip6 = G.unzip6++-- Monadic zipping+-- ---------------++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a+-- vector of results.+--+-- @since 0.13.2.0+zipWithM :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)+{-# INLINE zipWithM #-}+zipWithM = G.zipWithM++-- | /O(min(m,n))/ Zip the two vectors with a monadic action that also takes+-- the element index and yield a vector of results.+--+-- @since 0.13.2.0+izipWithM :: Monad m => (Int -> a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)+{-# INLINE izipWithM #-}+izipWithM = G.izipWithM++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the+-- results.+--+-- @since 0.13.2.0+zipWithM_ :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m ()+{-# INLINE zipWithM_ #-}+zipWithM_ = G.zipWithM_++-- | /O(min(m,n))/ Zip the two vectors with a monadic action that also takes+-- the element index and ignore the results.+--+-- @since 0.13.2.0+izipWithM_ :: Monad m => (Int -> a -> b -> m c) -> Vector a -> Vector b -> m ()+{-# INLINE izipWithM_ #-}+izipWithM_ = G.izipWithM_++-- Filtering+-- ---------++-- | /O(n)/ Drop all elements that do not satisfy the predicate.+--+-- @since 0.13.2.0+filter :: (a -> Bool) -> Vector a -> Vector a+{-# INLINE filter #-}+filter = G.filter++-- | /O(n)/ Drop all elements that do not satisfy the predicate which is applied to+-- the values and their indices.+--+-- @since 0.13.2.0+ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a+{-# INLINE ifilter #-}+ifilter = G.ifilter++-- | /O(n)/ Drop repeated adjacent elements. The first element in each group is returned.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.uniq $ V.fromList [1,3,3,200,3]+-- [1,3,200,3]+-- >>> import Data.Semigroup+-- >>> V.uniq $ V.fromList [ Arg 1 'a', Arg 1 'b', Arg 1 'c']+-- [Arg 1 'a']+--+-- @since 0.13.2.0+uniq :: (Eq a) => Vector a -> Vector a+{-# INLINE uniq #-}+uniq = G.uniq++-- | /O(n)/ Map the values and collect the 'Just' results.+--+-- @since 0.13.2.0+mapMaybe :: (a -> Maybe b) -> Vector a -> Vector b+{-# INLINE mapMaybe #-}+mapMaybe = G.mapMaybe++-- | /O(n)/ Map the indices/values and collect the 'Just' results.+--+-- @since 0.13.2.0+imapMaybe :: (Int -> a -> Maybe b) -> Vector a -> Vector b+{-# INLINE imapMaybe #-}+imapMaybe = G.imapMaybe++-- | /O(n)/ Return a Vector of all the 'Just' values.+--+-- @since 0.13.2.0+catMaybes :: Vector (Maybe a) -> Vector a+{-# INLINE catMaybes #-}+catMaybes = mapMaybe id++-- | /O(n)/ Drop all elements that do not satisfy the monadic predicate.+--+-- @since 0.13.2.0+filterM :: Monad m => (a -> m Bool) -> Vector a -> m (Vector a)+{-# INLINE filterM #-}+filterM = G.filterM++-- | /O(n)/ Apply the monadic function to each element of the vector and+-- discard elements returning 'Nothing'.+--+-- @since 0.13.2.0+mapMaybeM :: Monad m => (a -> m (Maybe b)) -> Vector a -> m (Vector b)+{-# INLINE mapMaybeM #-}+mapMaybeM = G.mapMaybeM++-- | /O(n)/ Apply the monadic function to each element of the vector and its index.+-- Discard elements returning 'Nothing'.+--+-- @since 0.13.2.0+imapMaybeM :: Monad m => (Int -> a -> m (Maybe b)) -> Vector a -> m (Vector b)+{-# INLINE imapMaybeM #-}+imapMaybeM = G.imapMaybeM++-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate.+-- The current implementation is not copy-free, unless the result vector is+-- fused away.+--+-- @since 0.13.2.0+takeWhile :: (a -> Bool) -> Vector a -> Vector a+{-# INLINE takeWhile #-}+takeWhile = G.takeWhile++-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate+-- without copying.+--+-- @since 0.13.2.0+dropWhile :: (a -> Bool) -> Vector a -> Vector a+{-# INLINE dropWhile #-}+dropWhile = G.dropWhile++-- Parititioning+-- -------------++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't. The+-- relative order of the elements is preserved at the cost of a sometimes+-- reduced performance compared to 'unstablePartition'.+--+-- @since 0.13.2.0+partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE partition #-}+partition = G.partition++-- | /O(n)/ Split the vector into two parts, the first one containing the+-- @`Left`@ elements and the second containing the @`Right`@ elements.+-- The relative order of the elements is preserved.+--+-- @since 0.13.2.0+partitionWith :: (a -> Either b c) -> Vector a -> (Vector b, Vector c)+{-# INLINE partitionWith #-}+partitionWith = G.partitionWith++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't.+-- The order of the elements is not preserved, but the operation is often+-- faster than 'partition'.+--+-- @since 0.13.2.0+unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE unstablePartition #-}+unstablePartition = G.unstablePartition++-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.span (<4) $ V.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9])+--+-- @since 0.13.2.0+span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE span #-}+span = G.span++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.break (>4) $ V.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9])+--+-- @since 0.13.2.0+break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE break #-}+break = G.break++-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.spanR (>4) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+--+-- @since 0.13.2.0+spanR :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE spanR #-}+spanR = G.spanR++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since 0.13.2.0+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.breakR (<5) $ V.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+--+-- @since 0.13.2.0+breakR :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE breakR #-}+breakR = G.breakR++-- | /O(n)/ Split a vector into a list of slices, using a predicate function.+--+-- The concatenation of this list of slices is equal to the argument vector,+-- and each slice contains only equal elements, as determined by the equality+-- predicate function.+--+-- Does not fuse.+--+-- >>> import qualified Data.Vector as V+-- >>> import Data.Char (isUpper)+-- >>> V.groupBy (\a b -> isUpper a == isUpper b) (V.fromList "Mississippi River")+-- ["M","ississippi ","R","iver"]+--+-- See also 'Data.List.groupBy', 'group'.+--+-- @since 0.13.2.0+groupBy :: (a -> a -> Bool) -> Vector a -> [Vector a]+{-# INLINE groupBy #-}+groupBy = G.groupBy++-- | /O(n)/ Split a vector into a list of slices of the input vector.+--+-- The concatenation of this list of slices is equal to the argument vector,+-- and each slice contains only equal elements.+--+-- Does not fuse.+--+-- This is the equivalent of 'groupBy (==)'.+--+-- >>> import qualified Data.Vector as V+-- >>> V.group (V.fromList "Mississippi")+-- ["M","i","ss","i","ss","i","pp","i"]+--+-- See also 'Data.List.group'.+--+-- @since 0.13.2.0+group :: Eq a => Vector a -> [Vector a]+{-# INLINE group #-}+group = G.groupBy (==)++-- Searching+-- ---------++infix 4 `elem`+-- | /O(n)/ Check if the vector contains an element.+--+-- @since 0.13.2.0+elem :: Eq a => a -> Vector a -> Bool+{-# INLINE elem #-}+elem = G.elem++infix 4 `notElem`+-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem').+--+-- @since 0.13.2.0+notElem :: Eq a => a -> Vector a -> Bool+{-# INLINE notElem #-}+notElem = G.notElem++-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'+-- if no such element exists.+--+-- @since 0.13.2.0+find :: (a -> Bool) -> Vector a -> Maybe a+{-# INLINE find #-}+find = G.find++-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate+-- or 'Nothing' if no such element exists.+--+-- @since 0.13.2.0+findIndex :: (a -> Bool) -> Vector a -> Maybe Int+{-# INLINE findIndex #-}+findIndex = G.findIndex++-- | /O(n)/ Yield 'Just' the index of the /last/ element matching the predicate+-- or 'Nothing' if no such element exists.+--+-- Does not fuse.+--+-- @since 0.13.2.0+findIndexR :: (a -> Bool) -> Vector a -> Maybe Int+{-# INLINE findIndexR #-}+findIndexR = G.findIndexR++-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending+-- order.+--+-- @since 0.13.2.0+findIndices :: (a -> Bool) -> Vector a -> Vector Int+{-# INLINE findIndices #-}+findIndices = G.findIndices++-- | /O(n)/ Yield 'Just' the index of the first occurrence of the given element or+-- 'Nothing' if the vector does not contain the element. This is a specialised+-- version of 'findIndex'.+--+-- @since 0.13.2.0+elemIndex :: Eq a => a -> Vector a -> Maybe Int+{-# INLINE elemIndex #-}+elemIndex = G.elemIndex++-- | /O(n)/ Yield the indices of all occurrences of the given element in+-- ascending order. This is a specialised version of 'findIndices'.+--+-- @since 0.13.2.0+elemIndices :: Eq a => a -> Vector a -> Vector Int+{-# INLINE elemIndices #-}+elemIndices = G.elemIndices++-- Folding+-- -------++-- | /O(n)/ Left fold.+--+-- @since 0.13.2.0+foldl :: (a -> b -> a) -> a -> Vector b -> a+{-# INLINE foldl #-}+foldl = G.foldl++-- | /O(n)/ Left fold on non-empty vectors.+--+-- @since 0.13.2.0+foldl1 :: (a -> a -> a) -> Vector a -> a+{-# INLINE foldl1 #-}+foldl1 = G.foldl1++-- | /O(n)/ Left fold with strict accumulator.+--+-- @since 0.13.2.0+foldl' :: (a -> b -> a) -> a -> Vector b -> a+{-# INLINE foldl' #-}+foldl' = G.foldl'++-- | /O(n)/ Left fold on non-empty vectors with strict accumulator.+--+-- @since 0.13.2.0+foldl1' :: (a -> a -> a) -> Vector a -> a+{-# INLINE foldl1' #-}+foldl1' = G.foldl1'++-- | /O(n)/ Right fold.+--+-- @since 0.13.2.0+foldr :: (a -> b -> b) -> b -> Vector a -> b+{-# INLINE foldr #-}+foldr = G.foldr++-- | /O(n)/ Right fold on non-empty vectors.+--+-- @since 0.13.2.0+foldr1 :: (a -> a -> a) -> Vector a -> a+{-# INLINE foldr1 #-}+foldr1 = G.foldr1++-- | /O(n)/ Right fold with a strict accumulator.+--+-- @since 0.13.2.0+foldr' :: (a -> b -> b) -> b -> Vector a -> b+{-# INLINE foldr' #-}+foldr' = G.foldr'++-- | /O(n)/ Right fold on non-empty vectors with strict accumulator.+--+-- @since 0.13.2.0+foldr1' :: (a -> a -> a) -> Vector a -> a+{-# INLINE foldr1' #-}+foldr1' = G.foldr1'++-- | /O(n)/ Left fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a+{-# INLINE ifoldl #-}+ifoldl = G.ifoldl++-- | /O(n)/ Left fold with strict accumulator using a function applied to each element+-- and its index.+--+-- @since 0.13.2.0+ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a+{-# INLINE ifoldl' #-}+ifoldl' = G.ifoldl'++-- | /O(n)/ Right fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b+{-# INLINE ifoldr #-}+ifoldr = G.ifoldr++-- | /O(n)/ Right fold with strict accumulator using a function applied to each+-- element and its index.+--+-- @since 0.13.2.0+ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b+{-# INLINE ifoldr' #-}+ifoldr' = G.ifoldr'++-- | /O(n)/ Map each element of the structure to a monoid and combine+-- the results. It uses the same implementation as the corresponding method+-- of the 'Foldable' type class. Note that it's implemented in terms of 'foldr'+-- and won't fuse with functions that traverse the vector from left to+-- right ('map', 'generate', etc.).+--+-- @since 0.13.2.0+foldMap :: (Monoid m) => (a -> m) -> Vector a -> m+{-# INLINE foldMap #-}+foldMap = G.foldMap++-- | /O(n)/ Like 'foldMap', but strict in the accumulator. It uses the same+-- implementation as the corresponding method of the 'Foldable' type class.+-- Note that it's implemented in terms of 'foldl'', so it fuses in most+-- contexts.+--+-- @since 0.13.2.0+foldMap' :: (Monoid m) => (a -> m) -> Vector a -> m+{-# INLINE foldMap' #-}+foldMap' = G.foldMap'+++-- Specialised folds+-- -----------------++-- | /O(n)/ Check if all elements satisfy the predicate.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.all even $ V.fromList [2, 4, 12]+-- True+-- >>> V.all even $ V.fromList [2, 4, 13]+-- False+-- >>> V.all even (V.empty :: V.Vector Int)+-- True+--+-- @since 0.13.2.0+all :: (a -> Bool) -> Vector a -> Bool+{-# INLINE all #-}+all = G.all++-- | /O(n)/ Check if any element satisfies the predicate.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.any even $ V.fromList [1, 3, 7]+-- False+-- >>> V.any even $ V.fromList [3, 2, 13]+-- True+-- >>> V.any even (V.empty :: V.Vector Int)+-- False+--+-- @since 0.13.2.0+any :: (a -> Bool) -> Vector a -> Bool+{-# INLINE any #-}+any = G.any++-- | /O(n)/ Check if all elements are 'True'.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.and $ V.fromList [True, False]+-- False+-- >>> V.and V.empty+-- True+--+-- @since 0.13.2.0+and :: Vector Bool -> Bool+{-# INLINE and #-}+and = G.and++-- | /O(n)/ Check if any element is 'True'.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.or $ V.fromList [True, False]+-- True+-- >>> V.or V.empty+-- False+--+-- @since 0.13.2.0+or :: Vector Bool -> Bool+{-# INLINE or #-}+or = G.or++-- | /O(n)/ Compute the sum of the elements.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.sum $ V.fromList [300,20,1]+-- 321+-- >>> V.sum (V.empty :: V.Vector Int)+-- 0+--+-- @since 0.13.2.0+sum :: Num a => Vector a -> a+{-# INLINE sum #-}+sum = G.sum++-- | /O(n)/ Compute the product of the elements.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.product $ V.fromList [1,2,3,4]+-- 24+-- >>> V.product (V.empty :: V.Vector Int)+-- 1+--+-- @since 0.13.2.0+product :: Num a => Vector a -> a+{-# INLINE product #-}+product = G.product++-- | /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__+--+-- >>> 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'+--+-- @since 0.13.2.0+maximum :: Ord a => Vector a -> a+{-# INLINE maximum #-}+maximum = G.maximum++-- | /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+-- 'Data.List.maximumBy' which returns the last tie.+--+-- ==== __Examples__+--+-- >>> 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')+--+-- @since 0.13.2.0+maximumBy :: (a -> a -> Ordering) -> Vector a -> a+{-# INLINE maximumBy #-}+maximumBy = G.maximumBy++-- | /O(n)/ Yield the maximum element of the vector by comparing the results+-- of a key function on each element. In case of a tie, the first occurrence+-- wins. The vector may not be empty.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.maximumOn fst $ V.fromList [(2,'a'), (1,'b')]+-- (2,'a')+-- >>> V.maximumOn fst $ V.fromList [(1,'a'), (1,'b')]+-- (1,'a')+--+-- @since 0.13.2.0+maximumOn :: Ord b => (a -> b) -> Vector a -> a+{-# INLINE maximumOn #-}+maximumOn = G.maximumOn++-- | /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__+--+-- >>> 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'+--+-- @since 0.13.2.0+minimum :: Ord a => Vector a -> a+{-# INLINE minimum #-}+minimum = G.minimum++-- | /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__+--+-- >>> 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')+--+-- @since 0.13.2.0+minimumBy :: (a -> a -> Ordering) -> Vector a -> a+{-# INLINE minimumBy #-}+minimumBy = G.minimumBy++-- | /O(n)/ Yield the minimum element of the vector by comparing the results+-- of a key function on each element. In case of a tie, the first occurrence+-- wins. The vector may not be empty.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.minimumOn fst $ V.fromList [(2,'a'), (1,'b')]+-- (1,'b')+-- >>> V.minimumOn fst $ V.fromList [(1,'a'), (1,'b')]+-- (1,'a')+--+-- @since 0.13.2.0+minimumOn :: Ord b => (a -> b) -> Vector a -> a+{-# INLINE minimumOn #-}+minimumOn = G.minimumOn++-- | /O(n)/ Yield the index of the maximum element of the vector. The vector+-- may not be empty.+--+-- @since 0.13.2.0+maxIndex :: Ord a => Vector a -> Int+{-# INLINE maxIndex #-}+maxIndex = G.maxIndex++-- | /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__+--+-- >>> 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+--+-- @since 0.13.2.0+maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int+{-# INLINE maxIndexBy #-}+maxIndexBy = G.maxIndexBy++-- | /O(n)/ Yield the index of the minimum element of the vector. The vector+-- may not be empty.+--+-- @since 0.13.2.0+minIndex :: Ord a => Vector a -> Int+{-# INLINE minIndex #-}+minIndex = G.minIndex++-- | /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__+--+-- >>> 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+--+-- @since 0.13.2.0+minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int+{-# INLINE minIndexBy #-}+minIndexBy = G.minIndexBy++-- Monadic folds+-- -------------++-- | /O(n)/ Monadic fold.+--+-- @since 0.13.2.0+foldM :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a+{-# INLINE foldM #-}+foldM = G.foldM++-- | /O(n)/ Monadic fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldM :: Monad m => (a -> Int -> b -> m a) -> a -> Vector b -> m a+{-# INLINE ifoldM #-}+ifoldM = G.ifoldM++-- | /O(n)/ Monadic fold over non-empty vectors.+--+-- @since 0.13.2.0+fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a+{-# INLINE fold1M #-}+fold1M = G.fold1M++-- | /O(n)/ Monadic fold with strict accumulator.+--+-- @since 0.13.2.0+foldM' :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a+{-# INLINE foldM' #-}+foldM' = G.foldM'++-- | /O(n)/ Monadic fold with strict accumulator using a function applied to each+-- element and its index.+--+-- @since 0.13.2.0+ifoldM' :: Monad m => (a -> Int -> b -> m a) -> a -> Vector b -> m a+{-# INLINE ifoldM' #-}+ifoldM' = G.ifoldM'++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator.+--+-- @since 0.13.2.0+fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a+{-# INLINE fold1M' #-}+fold1M' = G.fold1M'++-- | /O(n)/ Monadic fold that discards the result.+--+-- @since 0.13.2.0+foldM_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold that discards the result using a function applied to+-- each element and its index.+--+-- @since 0.13.2.0+ifoldM_ :: Monad m => (a -> Int -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE ifoldM_ #-}+ifoldM_ = G.ifoldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result.+--+-- @since 0.13.2.0+fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M_ #-}+fold1M_ = G.fold1M_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result.+--+-- @since 0.13.2.0+foldM'_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+-- using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldM'_ :: Monad m => (a -> Int -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE ifoldM'_ #-}+ifoldM'_ = G.ifoldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result.+--+-- @since 0.13.2.0+fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_++-- Monadic sequencing+-- ------------------++-- | Evaluate each action and collect the results.+--+-- @since 0.13.2.0+sequence :: Monad m => Vector (m a) -> m (Vector a)+{-# INLINE sequence #-}+sequence = G.sequence++-- | Evaluate each action and discard the results.+--+-- @since 0.13.2.0+sequence_ :: Monad m => Vector (m a) -> m ()+{-# INLINE sequence_ #-}+sequence_ = G.sequence_++-- Scans+-- -----++-- | /O(n)/ Left-to-right prescan.+--+-- @+-- prescanl f z = 'init' . 'scanl' f z+-- @+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.prescanl (+) 0 (V.fromList [1,2,3,4])+-- [0,1,3,6]+--+-- @since 0.13.2.0+prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE prescanl #-}+prescanl = G.prescanl++-- | /O(n)/ Left-to-right prescan with strict accumulator.+--+-- @since 0.13.2.0+prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE prescanl' #-}+prescanl' = G.prescanl'++-- | /O(n)/ Left-to-right postscan.+--+-- @+-- postscanl f z = 'tail' . 'scanl' f z+-- @+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.postscanl (+) 0 (V.fromList [1,2,3,4])+-- [1,3,6,10]+--+-- @since 0.13.2.0+postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE postscanl #-}+postscanl = G.postscanl++-- | /O(n)/ Left-to-right postscan with strict accumulator.+--+-- @since 0.13.2.0+postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE postscanl' #-}+postscanl' = G.postscanl'++-- | /O(n)/ Left-to-right scan.+--+-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>+-- > where y1 = z+-- > yi = f y(i-1) x(i-1)+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> V.scanl (+) 0 (V.fromList [1,2,3,4])+-- [0,1,3,6,10]+--+-- @since 0.13.2.0+scanl :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE scanl #-}+scanl = G.scanl++-- | /O(n)/ Left-to-right scan with strict accumulator.+--+-- @since 0.13.2.0+scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE scanl' #-}+scanl' = G.scanl'++-- | /O(n)/ Left-to-right scan over a vector with its index.+--+-- @since 0.13.2.0+iscanl :: (Int -> a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE iscanl #-}+iscanl = G.iscanl++-- | /O(n)/ Left-to-right scan over a vector (strictly) with its index.+--+-- @since 0.13.2.0+iscanl' :: (Int -> a -> b -> a) -> a -> Vector b -> Vector a+{-# INLINE iscanl' #-}+iscanl' = G.iscanl'++-- | /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__+-- >>> 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)+-- []+--+-- @since 0.13.2.0+scanl1 :: (a -> a -> a) -> Vector a -> Vector a+{-# INLINE scanl1 #-}+scanl1 = G.scanl1++-- | /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__+-- >>> 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)+-- []+--+-- @since 0.13.2.0+scanl1' :: (a -> a -> a) -> Vector a -> Vector a+{-# INLINE scanl1' #-}+scanl1' = G.scanl1'++-- | /O(n)/ Right-to-left prescan.+--+-- @+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'+-- @+--+-- @since 0.13.2.0+prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE prescanr #-}+prescanr = G.prescanr++-- | /O(n)/ Right-to-left prescan with strict accumulator.+--+-- @since 0.13.2.0+prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE prescanr' #-}+prescanr' = G.prescanr'++-- | /O(n)/ Right-to-left postscan.+--+-- @since 0.13.2.0+postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE postscanr #-}+postscanr = G.postscanr++-- | /O(n)/ Right-to-left postscan with strict accumulator.+--+-- @since 0.13.2.0+postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE postscanr' #-}+postscanr' = G.postscanr'++-- | /O(n)/ Right-to-left scan.+--+-- @since 0.13.2.0+scanr :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE scanr #-}+scanr = G.scanr++-- | /O(n)/ Right-to-left scan with strict accumulator.+--+-- @since 0.13.2.0+scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE scanr' #-}+scanr' = G.scanr'++-- | /O(n)/ Right-to-left scan over a vector with its index.+--+-- @since 0.13.2.0+iscanr :: (Int -> a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE iscanr #-}+iscanr = G.iscanr++-- | /O(n)/ Right-to-left scan over a vector (strictly) with its index.+--+-- @since 0.13.2.0+iscanr' :: (Int -> a -> b -> b) -> b -> Vector a -> Vector b+{-# INLINE iscanr' #-}+iscanr' = G.iscanr'++-- | /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__+-- >>> 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)+-- []+--+-- @since 0.13.2.0+scanr1 :: (a -> a -> a) -> Vector a -> Vector a+{-# INLINE scanr1 #-}+scanr1 = G.scanr1++-- | /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__+-- >>> 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)+-- []+--+-- @since 0.13.2.0+scanr1' :: (a -> a -> a) -> Vector a -> Vector a+{-# INLINE scanr1' #-}+scanr1' = G.scanr1'++-- Comparisons+-- ------------------------++-- | /O(n)/ Check if two vectors are equal using the supplied equality+-- predicate.+--+-- @since 0.13.2.0+eqBy :: (a -> b -> Bool) -> Vector a -> Vector b -> Bool+{-# INLINE eqBy #-}+eqBy = G.eqBy++-- | /O(n)/ Compare two vectors using the supplied comparison function for+-- vector elements. Comparison works the same as for lists.+--+-- > cmpBy compare == compare+--+-- @since 0.13.2.0+cmpBy :: (a -> b -> Ordering) -> Vector a -> Vector b -> Ordering+cmpBy = G.cmpBy++-- Conversions - Lists+-- ------------------------++-- | /O(n)/ Convert a vector to a list.+--+-- @since 0.13.2.0+toList :: Vector a -> [a]+{-# INLINE toList #-}+toList = G.toList++-- | /O(n)/ Convert a list to a vector. During the operation, the +-- vector’s capacity will be doubling until the list's contents are +-- in the vector. Depending on the list’s size, up to half of the vector’s +-- capacity might be empty. If you’d rather avoid this, you can use +-- 'fromListN', which will provide the exact space the list requires but will +-- prevent list fusion, or @'force' . 'fromList'@, which will create the +-- vector and then copy it without the superfluous space.+--+-- @since 0.13.2.0+fromList :: [a] -> Vector a+{-# INLINE fromList #-}+fromList = G.fromList++-- | /O(n)/ Convert the first @n@ elements of a list to a vector. It's+-- expected that the supplied list will be exactly @n@ elements long. As+-- an optimization, this function allocates a buffer for @n@ elements, which+-- could be used for DoS-attacks by exhausting the memory if an attacker controls+-- that parameter.+--+-- @+-- fromListN n xs = 'fromList' ('take' n xs)+-- @+--+-- @since 0.13.2.0+fromListN :: Int -> [a] -> Vector a+{-# INLINE fromListN #-}+fromListN = G.fromListN++-- Conversions - Lazy vectors+-- -----------------------------++-- | /O(1)/ Convert strict array to lazy array+toLazy :: Vector a -> V.Vector a+toLazy (Vector v) = v++-- | /O(n)/ Convert lazy array to strict array. This function reduces+-- each element of vector to WHNF.+fromLazy :: V.Vector a -> Vector a+fromLazy vec = liftRnfV (`seq` ()) v `seq` v where v = Vector vec+++-- Conversions - Arrays+-- -----------------------------++-- | /O(n)/ Convert an array to a vector and reduce each element to WHNF.+--+-- @since 0.13.2.0+fromArray :: Array a -> Vector a+{-# INLINE fromArray #-}+fromArray arr = liftRnfV (`seq` ()) vec `seq` vec+ where+ vec = Vector $ V.fromArray arr++-- | /O(n)/ Convert a vector to an array.+--+-- @since 0.13.2.0+toArray :: Vector a -> Array a+{-# INLINE toArray #-}+toArray (Vector v) = V.toArray v++-- | /O(1)/ Extract the underlying `Array`, offset where vector starts and the+-- total number of elements in the vector. Below property always holds:+--+-- > let (array, offset, len) = toArraySlice v+-- > v === unsafeFromArraySlice len offset array+--+-- @since 0.13.2.0+toArraySlice :: Vector a -> (Array a, Int, Int)+{-# INLINE toArraySlice #-}+toArraySlice (Vector v) = V.toArraySlice v+++-- | /O(n)/ Convert an array slice to a vector and reduce each element to WHNF.+--+-- This function is very unsafe, because constructing an invalid+-- vector can yield almost all other safe functions in this module+-- unsafe. These are equivalent:+--+-- > unsafeFromArraySlice len offset === unsafeTake len . unsafeDrop offset . fromArray+--+-- @since 0.13.2.0+unsafeFromArraySlice ::+ Array a -- ^ Immutable boxed array.+ -> Int -- ^ Offset+ -> Int -- ^ Length+ -> Vector a+{-# INLINE unsafeFromArraySlice #-}+unsafeFromArraySlice arr offset len = liftRnfV (`seq` ()) vec `seq` vec+ where vec = Vector (V.unsafeFromArraySlice arr offset len)++++-- Conversions - Mutable vectors+-- -----------------------------++-- | /O(1)/ Unsafely convert a mutable vector to an immutable one without+-- copying. The mutable vector may not be used after this operation.+--+-- @since 0.13.2.0+unsafeFreeze :: PrimMonad m => MVector (PrimState m) a -> m (Vector a)+{-# INLINE unsafeFreeze #-}+unsafeFreeze = G.unsafeFreeze++-- | /O(n)/ Yield an immutable copy of the mutable vector.+--+-- @since 0.13.2.0+freeze :: PrimMonad m => MVector (PrimState m) a -> m (Vector a)+{-# INLINE freeze #-}+freeze = G.freeze++-- | /O(1)/ Unsafely convert an immutable vector to a mutable one+-- without copying. Note that this is a very dangerous function and+-- generally it's only safe to read from the resulting vector. In this+-- case, the immutable vector could be used safely as well.+--+-- Problems with mutation happen because GHC has a lot of freedom to+-- introduce sharing. As a result mutable vectors produced by+-- @unsafeThaw@ may or may not share the same underlying buffer. For+-- example:+--+-- > foo = do+-- > let vec = V.generate 10 id+-- > mvec <- V.unsafeThaw vec+-- > do_something mvec+--+-- Here GHC could lift @vec@ outside of foo which means that all calls to+-- @do_something@ will use same buffer with possibly disastrous+-- results. Whether such aliasing happens or not depends on the program in+-- question, optimization levels, and GHC flags.+--+-- All in all, attempts to modify a vector produced by @unsafeThaw@ fall out of+-- domain of software engineering and into realm of black magic, dark+-- rituals, and unspeakable horrors. The only advice that could be given+-- is: "Don't attempt to mutate a vector produced by @unsafeThaw@ unless you+-- know how to prevent GHC from aliasing buffers accidentally. We don't."+--+-- @since 0.13.2.0+unsafeThaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)+{-# INLINE unsafeThaw #-}+unsafeThaw = G.unsafeThaw++-- | /O(n)/ Yield a mutable copy of an immutable vector.+--+-- @since 0.13.2.0+thaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)+{-# INLINE thaw #-}+thaw = G.thaw++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length. This is not checked.+--+-- @since 0.13.2.0+unsafeCopy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()+{-# INLINE unsafeCopy #-}+unsafeCopy = G.unsafeCopy++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length.+--+-- @since 0.13.2.0+copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()+{-# INLINE copy #-}+copy = G.copy++-- $setup+-- >>> :set -Wno-type-defaults+-- >>> import Prelude (Char, String, Bool(True, False), min, max, fst, even, undefined, Ord(..))
+ src/Data/Vector/Strict/Mutable.hs view
@@ -0,0 +1,787 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE RoleAnnotations #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE ScopedTypeVariables #-}+-- |+-- Module : Data.Vector.Strict.Mutable+-- Copyright : (c) Roman Leshchinskiy 2008-2010+-- Alexey Kuleshevich 2020-2022+-- Aleksey Khudyakov 2020-2022+-- Andrew Lelechenko 2020-2022+-- License : BSD-style+--+-- Maintainer : Haskell Libraries Team <libraries@haskell.org>+-- Stability : experimental+-- Portability : non-portable+--+-- Mutable strict boxed vectors. Strict means that all writes to+-- vector are evaluated to WHNF. However vector may contain bottoms,+-- since all elements of vector allocated using 'new' or 'unsafeNew'+-- are set to ⊥.+module Data.Vector.Strict.Mutable (+ -- * Mutable boxed vectors+ MVector(MVector), IOVector, STVector,++ -- * Accessors++ -- ** Length information+ length, null,++ -- ** Extracting subvectors+ slice, init, tail, take, drop, splitAt,+ unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,++ -- ** Overlapping+ overlaps,++ -- * Construction++ -- ** Initialisation+ new, unsafeNew, replicate, replicateM, generate, generateM, clone,++ -- ** Growing+ grow, unsafeGrow,++ -- ** Restricting memory usage+ clear,++ -- * Accessing individual elements+ read, readMaybe, write, modify, modifyM, swap, exchange,+ unsafeRead, unsafeWrite, unsafeModify, unsafeModifyM, unsafeSwap, unsafeExchange,++ -- * Folds+ mapM_, imapM_, forM_, iforM_,+ foldl, foldl', foldM, foldM',+ foldr, foldr', foldrM, foldrM',+ ifoldl, ifoldl', ifoldM, ifoldM',+ ifoldr, ifoldr', ifoldrM, ifoldrM',++ -- * Modifying vectors+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy,++ -- ** Filling and copying+ set, copy, move, unsafeCopy, unsafeMove,+ -- ** Lazy arrays+ toLazy, fromLazy,+ -- ** Arrays+ fromMutableArray, toMutableArray,++ -- * Re-exports+ PrimMonad, PrimState, RealWorld+) where++import Data.Coerce+import qualified Data.Vector.Generic.Mutable as G+import qualified Data.Vector.Mutable as MV+import Data.Primitive.Array+import Control.Monad.Primitive++import Prelude+ ( Ord, Monad(..), Bool, Int, Maybe, Ordering(..)+ , return, ($), (<$>) )++import Data.Typeable ( Typeable )++#include "vector.h"++type role MVector nominal representational++-- | Mutable boxed vectors keyed on the monad they live in ('IO' or @'ST' s@).+newtype MVector s a = MVector (MV.MVector s a)+ deriving ( Typeable )++type IOVector = MVector RealWorld+type STVector s = MVector s++instance G.MVector MVector a where+ {-# INLINE basicLength #-}+ basicLength = coerce (G.basicLength @MV.MVector @a)+ {-# INLINE basicUnsafeSlice #-}+ basicUnsafeSlice = coerce (G.basicUnsafeSlice @MV.MVector @a)+ {-# INLINE basicOverlaps #-}+ basicOverlaps = coerce (G.basicOverlaps @MV.MVector @a)+ {-# INLINE basicUnsafeNew #-}+ basicUnsafeNew = coerce (G.basicUnsafeNew @MV.MVector @a)+ {-# INLINE basicInitialize #-}+ -- initialization is unnecessary for boxed vectors+ basicInitialize _ = return ()+ {-# INLINE basicUnsafeReplicate #-}+ basicUnsafeReplicate n !x = coerce (G.basicUnsafeReplicate @MV.MVector @a) n x+ {-# INLINE basicUnsafeRead #-}+ basicUnsafeRead = coerce (G.basicUnsafeRead @MV.MVector @a)+ {-# INLINE basicUnsafeWrite #-}+ basicUnsafeWrite vec j !x = (coerce (G.basicUnsafeWrite @MV.MVector @a)) vec j x++ {-# INLINE basicUnsafeCopy #-}+ basicUnsafeCopy = coerce (G.basicUnsafeCopy @MV.MVector @a)++ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove = coerce (G.basicUnsafeMove @MV.MVector @a)+ {-# INLINE basicClear #-}+ basicClear = coerce (G.basicClear @MV.MVector @a)+++-- Length information+-- ------------------++-- | Length of the mutable vector.+--+-- @since 0.13.2.0+length :: MVector s a -> Int+{-# INLINE length #-}+length = G.length++-- | Check whether the vector is empty.+--+-- @since 0.13.2.0+null :: MVector s a -> Bool+{-# INLINE null #-}+null = G.null++-- Extracting subvectors+-- ---------------------++-- | Yield a part of the mutable vector without copying it. The vector must+-- contain at least @i+n@ elements.+--+-- @since 0.13.2.0+slice :: Int -- ^ @i@ starting index+ -> Int -- ^ @n@ length+ -> MVector s a+ -> MVector s a+{-# INLINE slice #-}+slice = G.slice++-- | Take the @n@ first elements of the mutable vector without making a+-- copy. For negative @n@, the empty vector is returned. If @n@ is larger+-- than the vector's length, the vector is returned unchanged.+--+-- @since 0.13.2.0+take :: Int -> MVector s a -> MVector s a+{-# INLINE take #-}+take = G.take++-- | Drop the @n@ first element of the mutable vector without making a+-- copy. For negative @n@, the vector is returned unchanged. If @n@ is+-- larger than the vector's length, the empty vector is returned.+--+-- @since 0.13.2.0+drop :: Int -> MVector s a -> MVector s a+{-# INLINE drop #-}+drop = G.drop++-- | /O(1)/ Split the mutable vector into the first @n@ elements+-- and the remainder, without copying.+--+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@,+-- but slightly more efficient.+--+-- @since 0.13.2.0+splitAt :: Int -> MVector s a -> (MVector s a, MVector s a)+{-# INLINE splitAt #-}+splitAt = G.splitAt++-- | Drop the last element of the mutable vector without making a copy.+-- If the vector is empty, an exception is thrown.+--+-- @since 0.13.2.0+init :: MVector s a -> MVector s a+{-# INLINE init #-}+init = G.init++-- | Drop the first element of the mutable vector without making a copy.+-- If the vector is empty, an exception is thrown.+--+-- @since 0.13.2.0+tail :: MVector s a -> MVector s a+{-# INLINE tail #-}+tail = G.tail++-- | Yield a part of the mutable vector without copying it. No bounds checks+-- are performed.+--+-- @since 0.13.2.0+unsafeSlice :: Int -- ^ starting index+ -> Int -- ^ length of the slice+ -> MVector s a+ -> MVector s a+{-# INLINE unsafeSlice #-}+unsafeSlice = G.unsafeSlice++-- | Unsafe variant of 'take'. If @n@ is out of range, it will+-- simply create an invalid slice that likely violate memory safety.+--+-- @since 0.13.2.0+unsafeTake :: Int -> MVector s a -> MVector s a+{-# INLINE unsafeTake #-}+unsafeTake = G.unsafeTake++-- | Unsafe variant of 'drop'. If @n@ is out of range, it will+-- simply create an invalid slice that likely violate memory safety.+--+-- @since 0.13.2.0+unsafeDrop :: Int -> MVector s a -> MVector s a+{-# INLINE unsafeDrop #-}+unsafeDrop = G.unsafeDrop++-- | Same as 'init', but doesn't do range checks.+--+-- @since 0.13.2.0+unsafeInit :: MVector s a -> MVector s a+{-# INLINE unsafeInit #-}+unsafeInit = G.unsafeInit++-- | Same as 'tail', but doesn't do range checks.+--+-- @since 0.13.2.0+unsafeTail :: MVector s a -> MVector s a+{-# INLINE unsafeTail #-}+unsafeTail = G.unsafeTail++-- Overlapping+-- -----------++-- | Check whether two vectors overlap.+--+-- @since 0.13.2.0+overlaps :: MVector s a -> MVector s a -> Bool+{-# INLINE overlaps #-}+overlaps = G.overlaps++-- Initialisation+-- --------------++-- | Create a mutable vector of the given length.+--+-- @since 0.13.2.0+new :: PrimMonad m => Int -> m (MVector (PrimState m) a)+{-# INLINE new #-}+new = G.new++-- | Create a mutable vector of the given length. The vector elements+-- are set to bottom, so accessing them will cause an exception.+--+-- @since 0.13.2.0+unsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) a)+{-# INLINE unsafeNew #-}+unsafeNew = G.unsafeNew++-- | Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with an initial value.+--+-- @since 0.13.2.0+replicate :: PrimMonad m => Int -> a -> m (MVector (PrimState m) a)+{-# INLINE replicate #-}+replicate = G.replicate++-- | Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with values produced by repeatedly executing the monadic action.+--+-- @since 0.13.2.0+replicateM :: PrimMonad m => Int -> m a -> m (MVector (PrimState m) a)+{-# INLINE replicateM #-}+replicateM = G.replicateM++-- | /O(n)/ Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with the results of applying the function to each index.+-- Iteration starts at index 0.+--+-- @since 0.13.2.0+generate :: (PrimMonad m) => Int -> (Int -> a) -> m (MVector (PrimState m) a)+{-# INLINE generate #-}+generate = G.generate++-- | /O(n)/ Create a mutable vector of the given length (0 if the length is+-- negative) and fill it with the results of applying the monadic function to each+-- index. Iteration starts at index 0.+--+-- @since 0.13.2.0+generateM :: (PrimMonad m) => Int -> (Int -> m a) -> m (MVector (PrimState m) a)+{-# INLINE generateM #-}+generateM = G.generateM++-- | Create a copy of a mutable vector.+--+-- @since 0.13.2.0+clone :: PrimMonad m => MVector (PrimState m) a -> m (MVector (PrimState m) a)+{-# INLINE clone #-}+clone = G.clone++-- Growing+-- -------++-- | Grow a boxed vector by the given number of elements. The number must be+-- non-negative. This has the same semantics as 'G.grow' for generic vectors. It differs+-- from @grow@ functions for unpacked vectors, however, in that only pointers to+-- values are copied over, therefore the values themselves will be shared between the+-- two vectors. This is an important distinction to know about during memory+-- usage analysis and in case the values themselves are of a mutable type, e.g.+-- 'Data.IORef.IORef' or another mutable vector.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector as V+-- >>> import qualified Data.Vector.Mutable as MV+-- >>> mv <- V.thaw $ V.fromList ([10, 20, 30] :: [Integer])+-- >>> mv' <- MV.grow mv 2+--+-- The two extra elements at the end of the newly allocated vector will be+-- uninitialized and will result in an error if evaluated, so me must overwrite+-- them with new values first:+--+-- >>> MV.write mv' 3 999+-- >>> MV.write mv' 4 777+-- >>> V.freeze mv'+-- [10,20,30,999,777]+--+-- It is important to note that the source mutable vector is not affected when+-- the newly allocated one is mutated.+--+-- >>> MV.write mv' 2 888+-- >>> V.freeze mv'+-- [10,20,888,999,777]+-- >>> V.freeze mv+-- [10,20,30]+--+-- @since 0.13.2.0+grow :: PrimMonad m+ => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)+{-# INLINE grow #-}+grow = G.grow++-- | Grow a vector by the given number of elements. The number must be non-negative, but+-- this is not checked. This has the same semantics as 'G.unsafeGrow' for generic vectors.+--+-- @since 0.13.2.0+unsafeGrow :: PrimMonad m+ => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)+{-# INLINE unsafeGrow #-}+unsafeGrow = G.unsafeGrow++-- Restricting memory usage+-- ------------------------++-- | Reset all elements of the vector to some undefined value, clearing all+-- references to external objects.+--+-- @since 0.13.2.0+clear :: PrimMonad m => MVector (PrimState m) a -> m ()+{-# INLINE clear #-}+clear = G.clear++-- Accessing individual elements+-- -----------------------------++-- | Yield the element at the given position. Will throw an exception if+-- the index is out of range.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Mutable as MV+-- >>> v <- MV.generate 10 (\x -> x*x)+-- >>> MV.read v 3+-- 9+--+-- @since 0.13.2.0+read :: PrimMonad m => MVector (PrimState m) a -> Int -> m a+{-# INLINE read #-}+read = G.read++-- | Yield the element at the given position. Returns 'Nothing' if+-- the index is out of range.+--+-- @since 0.13.2.0+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Mutable as MV+-- >>> v <- MV.generate 10 (\x -> x*x)+-- >>> MV.readMaybe v 3+-- Just 9+-- >>> MV.readMaybe v 13+-- Nothing+--+-- @since 0.13.2.0+readMaybe :: (PrimMonad m) => MVector (PrimState m) a -> Int -> m (Maybe a)+{-# INLINE readMaybe #-}+readMaybe = G.readMaybe++-- | Replace the element at the given position.+--+-- @since 0.13.2.0+write :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()+{-# INLINE write #-}+write = G.write++-- | Modify the element at the given position.+--+-- @since 0.13.2.0+modify :: PrimMonad m => MVector (PrimState m) a -> (a -> a) -> Int -> m ()+{-# INLINE modify #-}+modify = G.modify++-- | Modify the element at the given position using a monadic function.+--+-- @since 0.13.2.0+modifyM :: (PrimMonad m) => MVector (PrimState m) a -> (a -> m a) -> Int -> m ()+{-# INLINE modifyM #-}+modifyM = G.modifyM++-- | Swap the elements at the given positions.+--+-- @since 0.13.2.0+swap :: PrimMonad m => MVector (PrimState m) a -> Int -> Int -> m ()+{-# INLINE swap #-}+swap = G.swap++-- | Replace the element at the given position and return the old element.+--+-- @since 0.13.2.0+exchange :: (PrimMonad m) => MVector (PrimState m) a -> Int -> a -> m a+{-# INLINE exchange #-}+exchange = G.exchange++-- | Yield the element at the given position. No bounds checks are performed.+--+-- @since 0.13.2.0+unsafeRead :: PrimMonad m => MVector (PrimState m) a -> Int -> m a+{-# INLINE unsafeRead #-}+unsafeRead = G.unsafeRead++-- | Replace the element at the given position. No bounds checks are performed.+--+-- @since 0.13.2.0+unsafeWrite :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()+{-# INLINE unsafeWrite #-}+unsafeWrite = G.unsafeWrite++-- | Modify the element at the given position. No bounds checks are performed.+--+-- @since 0.13.2.0+unsafeModify :: PrimMonad m => MVector (PrimState m) a -> (a -> a) -> Int -> m ()+{-# INLINE unsafeModify #-}+unsafeModify = G.unsafeModify++-- | Modify the element at the given position using a monadic+-- function. No bounds checks are performed.+--+-- @since 0.13.2.0+unsafeModifyM :: (PrimMonad m) => MVector (PrimState m) a -> (a -> m a) -> Int -> m ()+{-# INLINE unsafeModifyM #-}+unsafeModifyM = G.unsafeModifyM++-- | Swap the elements at the given positions. No bounds checks are performed.+--+-- @since 0.13.2.0+unsafeSwap :: PrimMonad m => MVector (PrimState m) a -> Int -> Int -> m ()+{-# INLINE unsafeSwap #-}+unsafeSwap = G.unsafeSwap++-- | Replace the element at the given position and return the old element. No+-- bounds checks are performed.+--+-- @since 0.13.2.0+unsafeExchange :: (PrimMonad m) => MVector (PrimState m) a -> Int -> a -> m a+{-# INLINE unsafeExchange #-}+unsafeExchange = G.unsafeExchange++-- Filling and copying+-- -------------------++-- | Set all elements of the vector to the given value.+--+-- @since 0.13.2.0+set :: PrimMonad m => MVector (PrimState m) a -> a -> m ()+{-# INLINE set #-}+set = G.set++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap.+--+-- @since 0.13.2.0+copy :: PrimMonad m => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE copy #-}+copy = G.copy++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap, but this is not checked.+--+-- @since 0.13.2.0+unsafeCopy :: PrimMonad m => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeCopy #-}+unsafeCopy = G.unsafeCopy++-- | Move the contents of a vector. The two vectors must have the same+-- length.+--+-- If the vectors do not overlap, then this is equivalent to 'copy'.+-- Otherwise, the copying is performed as if the source vector were+-- copied to a temporary vector and then the temporary vector was copied+-- to the target vector.+--+-- @since 0.13.2.0+move :: PrimMonad m => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE move #-}+move = G.move++-- | Move the contents of a vector. The two vectors must have the same+-- length, but this is not checked.+--+-- If the vectors do not overlap, then this is equivalent to 'unsafeCopy'.+-- Otherwise, the copying is performed as if the source vector were+-- copied to a temporary vector and then the temporary vector was copied+-- to the target vector.+--+-- @since 0.13.2.0+unsafeMove :: PrimMonad m => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove = G.unsafeMove++-- Modifying vectors+-- -----------------++-- | Compute the (lexicographically) next permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutation :: (PrimMonad m, Ord e) => MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutation #-}+nextPermutation = G.nextPermutation++-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: PrimMonad m => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy = G.nextPermutationBy++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m, Ord e) => MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = G.prevPermutation++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: PrimMonad m => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy = G.prevPermutationBy+++-- Folds+-- -----++-- | /O(n)/ Apply the monadic action to every element of the vector, discarding the results.+--+-- @since 0.13.2.0+mapM_ :: (PrimMonad m) => (a -> m b) -> MVector (PrimState m) a -> m ()+{-# INLINE mapM_ #-}+mapM_ = G.mapM_++-- | /O(n)/ Apply the monadic action to every element of the vector and its index, discarding the results.+--+-- @since 0.13.2.0+imapM_ :: (PrimMonad m) => (Int -> a -> m b) -> MVector (PrimState m) a -> m ()+{-# INLINE imapM_ #-}+imapM_ = G.imapM_++-- | /O(n)/ Apply the monadic action to every element of the vector,+-- discarding the results. It's the same as @flip mapM_@.+--+-- @since 0.13.2.0+forM_ :: (PrimMonad m) => MVector (PrimState m) a -> (a -> m b) -> m ()+{-# INLINE forM_ #-}+forM_ = G.forM_++-- | /O(n)/ Apply the monadic action to every element of the vector+-- and its index, discarding the results. It's the same as @flip imapM_@.+--+-- @since 0.13.2.0+iforM_ :: (PrimMonad m) => MVector (PrimState m) a -> (Int -> a -> m b) -> m ()+{-# INLINE iforM_ #-}+iforM_ = G.iforM_++-- | /O(n)/ Pure left fold.+--+-- @since 0.13.2.0+foldl :: (PrimMonad m) => (b -> a -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldl #-}+foldl = G.foldl++-- | /O(n)/ Pure left fold with strict accumulator.+--+-- @since 0.13.2.0+foldl' :: (PrimMonad m) => (b -> a -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldl' #-}+foldl' = G.foldl'++-- | /O(n)/ Pure left fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldl :: (PrimMonad m) => (b -> Int -> a -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldl #-}+ifoldl = G.ifoldl++-- | /O(n)/ Pure left fold with strict accumulator using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldl' :: (PrimMonad m) => (b -> Int -> a -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldl' #-}+ifoldl' = G.ifoldl'++-- | /O(n)/ Pure right fold.+--+-- @since 0.13.2.0+foldr :: (PrimMonad m) => (a -> b -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldr #-}+foldr = G.foldr++-- | /O(n)/ Pure right fold with strict accumulator.+--+-- @since 0.13.2.0+foldr' :: (PrimMonad m) => (a -> b -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldr' #-}+foldr' = G.foldr'++-- | /O(n)/ Pure right fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldr :: (PrimMonad m) => (Int -> a -> b -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldr #-}+ifoldr = G.ifoldr++-- | /O(n)/ Pure right fold with strict accumulator using a function applied+-- to each element and its index.+--+-- @since 0.13.2.0+ifoldr' :: (PrimMonad m) => (Int -> a -> b -> b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldr' #-}+ifoldr' = G.ifoldr'++-- | /O(n)/ Monadic fold.+--+-- @since 0.13.2.0+foldM :: (PrimMonad m) => (b -> a -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldM #-}+foldM = G.foldM++-- | /O(n)/ Monadic fold with strict accumulator.+--+-- @since 0.13.2.0+foldM' :: (PrimMonad m) => (b -> a -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldM' #-}+foldM' = G.foldM'++-- | /O(n)/ Monadic fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldM :: (PrimMonad m) => (b -> Int -> a -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldM #-}+ifoldM = G.ifoldM++-- | /O(n)/ Monadic fold with strict accumulator using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldM' :: (PrimMonad m) => (b -> Int -> a -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldM' #-}+ifoldM' = G.ifoldM'++-- | /O(n)/ Monadic right fold.+--+-- @since 0.13.2.0+foldrM :: (PrimMonad m) => (a -> b -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldrM #-}+foldrM = G.foldrM++-- | /O(n)/ Monadic right fold with strict accumulator.+--+-- @since 0.13.2.0+foldrM' :: (PrimMonad m) => (a -> b -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE foldrM' #-}+foldrM' = G.foldrM'++-- | /O(n)/ Monadic right fold using a function applied to each element and its index.+--+-- @since 0.13.2.0+ifoldrM :: (PrimMonad m) => (Int -> a -> b -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldrM #-}+ifoldrM = G.ifoldrM++-- | /O(n)/ Monadic right fold with strict accumulator using a function applied+-- to each element and its index.+--+-- @since 0.13.2.0+ifoldrM' :: (PrimMonad m) => (Int -> a -> b -> m b) -> b -> MVector (PrimState m) a -> m b+{-# INLINE ifoldrM' #-}+ifoldrM' = G.ifoldrM'++-- Conversions - Lazy vectors+-- -----------------------------++-- | /O(1)/ Convert strict mutable vector to lazy mutable+-- vector. Vectors will share mutable buffer+toLazy :: MVector s a -> MV.MVector s a+{-# INLINE toLazy #-}+toLazy (MVector vec) = vec++-- | /O(n)/ Convert lazy mutable vector to strict mutable+-- vector. Vectors will share mutable buffer. This function evaluates+-- vector elements to WHNF.+fromLazy :: PrimMonad m => MV.MVector (PrimState m) a -> m (MVector (PrimState m) a)+fromLazy mvec = stToPrim $ do+ G.foldM' (\_ !_ -> return ()) () mvec+ return $ MVector mvec+++-- Conversions - Arrays+-- -----------------------------++-- | /O(n)/ Make a copy of a mutable array to a new mutable+-- vector. All elements of a vector are evaluated to WHNF+--+-- @since 0.13.2.0+fromMutableArray :: PrimMonad m => MutableArray (PrimState m) a -> m (MVector (PrimState m) a)+{-# INLINE fromMutableArray #-}+fromMutableArray marr = stToPrim $ do+ mvec <- MVector <$> MV.fromMutableArray marr+ foldM' (\_ !_ -> return ()) () mvec+ return mvec++-- | /O(n)/ Make a copy of a mutable vector into a new mutable array.+--+-- @since 0.13.2.0+toMutableArray :: PrimMonad m => MVector (PrimState m) a -> m (MutableArray (PrimState m) a)+{-# INLINE toMutableArray #-}+toMutableArray (MVector v) = MV.toMutableArray v++-- $setup+-- >>> import Prelude (Integer,Num(..))
src/Data/Vector/Unboxed.hs view
@@ -13,15 +13,43 @@ -- Stability : experimental -- Portability : non-portable ----- Adaptive unboxed vectors. The implementation is based on type families+-- Adaptive unboxed vectors. The implementation is based on data families -- and picks an efficient, specialised representation for every element type.--- For example, unboxed vectors of pairs are represented as pairs of unboxed--- vectors.+-- For example, vector of fixed size primitives are backed by+-- 'Data.Vector.Primitive.Vector', unboxed vectors of tuples are represented+-- as tuples of unboxed vectors (see 'zip'\/'unzip'). Note that vector is+-- only adaptive types could pick boxed representation for data type\/field+-- of record. However all library instances are backed by unboxed array(s). ----- Implementing unboxed vectors for new data types can be very easy. Here is--- how the library does this for 'Complex' by simply wrapping vectors of--- pairs.+-- Defining new instances of unboxed vectors is somewhat complicated since+-- it requires defining two data family and two type class instances. Latter+-- two could be generated using @GeneralizedNewtypeDeriving@ or @DerivingVia@ --+-- >>> :set -XTypeFamilies -XStandaloneDeriving -XMultiParamTypeClasses -XGeneralizedNewtypeDeriving+-- >>>+-- >>> import qualified Data.Vector.Generic as VG+-- >>> import qualified Data.Vector.Generic.Mutable as VGM+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>>+-- >>> newtype Foo = Foo Int+-- >>>+-- >>> newtype instance VU.MVector s Foo = MV_Int (VU.MVector s Int)+-- >>> newtype instance VU.Vector Foo = V_Int (VU.Vector Int)+-- >>> deriving instance VGM.MVector VU.MVector Foo+-- >>> deriving instance VG.Vector VU.Vector Foo+-- >>> instance VU.Unbox Foo+--+-- For other data types we have several newtype wrappers for use with+-- @DerivingVia@. See documentation of 'As' and 'IsoUnbox' for defining +-- unboxed vector of product types. 'UnboxViaPrim' could be used to define+-- vector of instances of 'Data.Vector.Primitive.Prim'. Similarly+-- 'DoNotUnboxStrict'/'DoNotUnboxLazy'/'DoNotUnboxNormalForm' could be used+-- to represent polymorphic fields as boxed vectors.+--+-- Or if everything else fails instances could be written by hand.+-- Here is how the library does this for 'Complex' by simply wrapping+-- vectors of pairs.+-- -- @ -- newtype instance 'MVector' s ('Complex' a) = MV_Complex ('MVector' s (a,a)) -- newtype instance 'Vector' ('Complex' a) = V_Complex ('Vector' (a,a))@@ -38,26 +66,6 @@ -- -- instance ('RealFloat' a, 'Unbox' a) => 'Unbox' ('Complex' a) -- @------ For newtypes, defining instances is easier since one could use--- @GeneralizedNewtypeDeriving@ in order to derive instances for--- 'Data.Vector.Generic.Vector' and 'Data.Vector.Generic.Mutable.MVector',--- since they're very cumbersome to write by hand:------ >>> :set -XTypeFamilies -XStandaloneDeriving -XMultiParamTypeClasses -XGeneralizedNewtypeDeriving--- >>>--- >>> import qualified Data.Vector.Generic as VG--- >>> import qualified Data.Vector.Generic.Mutable as VGM--- >>> import qualified Data.Vector.Unboxed as VU--- >>>--- >>> newtype Foo = Foo Int--- >>>--- >>> newtype instance VU.MVector s Foo = MV_Int (VU.MVector s Int)--- >>> newtype instance VU.Vector Foo = V_Int (VU.Vector Int)--- >>> deriving instance VGM.MVector VU.MVector Foo--- >>> deriving instance VG.Vector VU.Vector Foo--- >>> instance VU.Unbox Foo- module Data.Vector.Unboxed ( -- * Unboxed vectors Vector(V_UnboxAs, V_UnboxViaPrim), MVector(..), Unbox,@@ -132,12 +140,15 @@ -- ** Zipping zipWith, zipWith3, zipWith4, zipWith5, zipWith6, izipWith, izipWith3, izipWith4, izipWith5, izipWith6,+ -- *** Zipping tuples+ -- $zip zip, zip3, zip4, zip5, zip6, -- ** Monadic zipping zipWithM, izipWithM, zipWithM_, izipWithM_, -- ** Unzipping+ -- $unzip unzip, unzip3, unzip4, unzip5, unzip6, -- * Working with predicates@@ -149,7 +160,7 @@ takeWhile, dropWhile, -- ** Partitioning- partition, unstablePartition, partitionWith, span, break, groupBy, group,+ partition, unstablePartition, partitionWith, span, break, spanR, breakR, groupBy, group, -- ** Searching elem, notElem, find, findIndex, findIndexR, findIndices, elemIndex, elemIndices,@@ -198,7 +209,14 @@ -- ** Deriving via UnboxViaPrim(..), As(..),- IsoUnbox(..)+ IsoUnbox(..),++ -- *** /Lazy/ boxing+ DoNotUnboxLazy(..),++ -- *** /Strict/ boxing+ DoNotUnboxStrict(..),+ DoNotUnboxNormalForm(..) ) where import Data.Vector.Unboxed.Base@@ -698,7 +716,7 @@ -- ------------------------ -- | /O(n)/ Yield the argument, but force it not to retain any extra memory,--- possibly by copying it.+-- by copying it. -- -- This is especially useful when dealing with slices. For example: --@@ -808,7 +826,7 @@ accumulate = G.accumulate -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the--- corresponding value @b@ from the the value vector,+-- corresponding value @b@ from the value vector, -- replace the element of the initial vector at -- position @i@ by @f a b@. --@@ -970,6 +988,26 @@ -- Zipping -- ------- +-- $zip+--+-- Following functions could be used to construct vector of tuples+-- from tuple of vectors. This operation is done in /O(1)/ time and+-- will share underlying buffers.+--+-- Note that variants from "Data.Vector.Generic" doesn't have this+-- property.++-- $unzip+--+-- Following functions could be used to access underlying+-- representation of array of tuples. They convert array to tuple of+-- arrays. This operation is done in /O(1)/ time and will share+-- underlying buffers.+--+-- Note that variants from "Data.Vector.Generic" doesn't have this+-- property.++ -- | /O(min(m,n))/ Zip two vectors with the given function. zipWith :: (Unbox a, Unbox b, Unbox c) => (a -> b -> c) -> Vector a -> Vector b -> Vector c@@ -1169,16 +1207,62 @@ -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy -- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> VU.span (<4) $ VU.generate 10 id+-- ([0,1,2,3],[4,5,6,7,8,9]) span :: Unbox a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE span #-} span = G.span -- | /O(n)/ Split the vector into the longest prefix of elements that do not -- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> VU.break (>4) $ VU.generate 10 id+-- ([0,1,2,3,4],[5,6,7,8,9]) break :: Unbox a => (a -> Bool) -> Vector a -> (Vector a, Vector a) {-# INLINE break #-} break = G.break +-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+--+-- Does not fuse.+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> VU.spanR (>4) $ VU.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+spanR :: Unbox a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE spanR #-}+spanR = G.spanR++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+--+-- Does not fuse.+--+-- @since NEXT_VERSION+--+-- ==== __Examples__+--+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> VU.breakR (<5) $ VU.generate 10 id+-- ([5,6,7,8,9],[0,1,2,3,4])+breakR :: Unbox a => (a -> Bool) -> Vector a -> (Vector a, Vector a)+{-# INLINE breakR #-}+breakR = G.breakR+ -- | /O(n)/ Split a vector into a list of slices, using a predicate function. -- -- The concatenation of this list of slices is equal to the argument vector,@@ -1882,7 +1966,15 @@ {-# INLINE toList #-} toList = G.toList --- | /O(n)/ Convert a list to a vector.+-- | /O(n)/ Convert a list to a vector. During the operation, the+-- vector’s capacity will be doubling until the list's contents are+-- in the vector. Depending on the list’s size, up to half of the vector’s+-- capacity might be empty. If you’d rather avoid this, you can use+-- 'fromListN', which will provide the exact space the list requires but will+-- prevent list fusion, or @'force' . 'fromList'@, which will create the+-- vector and then copy it without the superfluous space.+--+-- @since 0.3 fromList :: Unbox a => [a] -> Vector a {-# INLINE fromList #-} fromList = G.fromList@@ -1974,4 +2066,4 @@ #include "unbox-tuple-instances" -- $setup--- >>> import Prelude (Bool(True, False), ($), (+), min, max, even, fst, pred, succ, undefined)+-- >>> import Prelude (Bool(True, False), ($), (+), min, max, even, fst, pred, id, succ, undefined, Ord(..))
src/Data/Vector/Unboxed/Base.hs view
@@ -27,11 +27,14 @@ module Data.Vector.Unboxed.Base ( MVector(..), IOVector, STVector, Vector(..), Unbox,- UnboxViaPrim(..), As(..), IsoUnbox(..)+ UnboxViaPrim(..), As(..), IsoUnbox(..),+ DoNotUnboxLazy(..), DoNotUnboxNormalForm(..), DoNotUnboxStrict(..) ) where import qualified Data.Vector.Generic as G import qualified Data.Vector.Generic.Mutable as M+import qualified Data.Vector as B+import qualified Data.Vector.Strict as S import qualified Data.Vector.Primitive as P @@ -41,6 +44,7 @@ #if MIN_VERSION_deepseq(1,4,3) , NFData1(liftRnf) #endif+ , force ) import Control.Monad.Primitive@@ -763,6 +767,266 @@ basicUnsafeIndexM (V_Arg v) i = uncurry Arg `liftM` G.basicUnsafeIndexM v i elemseq _ (Arg x y) z = G.elemseq (undefined :: Vector a) x $ G.elemseq (undefined :: Vector b) y z++-- -------+-- Unboxing the boxed values+-- -------++-- | Newtype which allows to derive unbox instances for type @a@ which+-- is normally a "boxed" type. The newtype does not alter the strictness+-- semantics of the underlying type and inherits the laizness of said type.+-- For a strict newtype wrapper, see 'DoNotUnboxStrict'.+--+-- 'DoNotUnboxLazy' is intended to be unsed in conjunction with the newtype 'As'+-- and the type class 'IsoUnbox'. Here's an example which uses the following+-- explicit 'IsoUnbox' instance:+--+--+-- >>> :set -XTypeFamilies -XStandaloneDeriving -XDerivingVia+-- >>> :set -XMultiParamTypeClasses -XTypeOperators -XFlexibleInstances+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> import qualified Data.Vector.Unboxed.Mutable as VUM+-- >>> import qualified Data.Vector.Generic as VG+-- >>> import qualified Data.Vector.Generic.Mutable as VGM+-- >>> :{+-- >>> data Foo a = Foo Int a+-- >>> deriving (Eq, Ord, Show)+-- >>> instance VU.IsoUnbox (Foo a) (Int, VU.DoNotUnboxLazy a) where+-- >>> toURepr (Foo i a) = (i, VU.DoNotUnboxLazy a)+-- >>> fromURepr (i, VU.DoNotUnboxLazy a) = Foo i a+-- >>> {-# INLINE toURepr #-}+-- >>> {-# INLINE fromURepr #-}+-- >>> newtype instance VU.MVector s (Foo a) = MV_Foo (VU.MVector s (Int, VU.DoNotUnboxLazy a))+-- >>> newtype instance VU.Vector (Foo a) = V_Foo (VU.Vector (Int, VU.DoNotUnboxLazy a))+-- >>> deriving via (Foo a `VU.As` (Int, VU.DoNotUnboxLazy a)) instance VGM.MVector VUM.MVector (Foo a)+-- >>> deriving via (Foo a `VU.As` (Int, VU.DoNotUnboxLazy a)) instance VG.Vector VU.Vector (Foo a)+-- >>> instance VU.Unbox (Foo a)+-- >>> :}+--+-- >>> VU.fromListN 3 [ Foo 4 "Haskell's", Foo 8 "strong", Foo 16 "types" ]+-- [Foo 4 "Haskell's",Foo 8 "strong",Foo 16 "types"]+--+-- @since 0.13.2.0+newtype DoNotUnboxLazy a = DoNotUnboxLazy a++newtype instance MVector s (DoNotUnboxLazy a) = MV_DoNotUnboxLazy (B.MVector s a)+newtype instance Vector (DoNotUnboxLazy a) = V_DoNotUnboxLazy (B.Vector a)++instance M.MVector MVector (DoNotUnboxLazy a) where+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicOverlaps #-}+ {-# INLINE basicUnsafeNew #-}+ {-# INLINE basicInitialize #-}+ {-# INLINE basicUnsafeReplicate #-}+ {-# INLINE basicUnsafeRead #-}+ {-# INLINE basicUnsafeWrite #-}+ {-# INLINE basicClear #-}+ {-# INLINE basicSet #-}+ {-# INLINE basicUnsafeCopy #-}+ {-# INLINE basicUnsafeGrow #-}+ basicLength = coerce $ M.basicLength @B.MVector @a+ basicUnsafeSlice = coerce $ M.basicUnsafeSlice @B.MVector @a+ basicOverlaps = coerce $ M.basicOverlaps @B.MVector @a+ basicUnsafeNew = coerce $ M.basicUnsafeNew @B.MVector @a+ basicInitialize = coerce $ M.basicInitialize @B.MVector @a+ basicUnsafeReplicate = coerce $ M.basicUnsafeReplicate @B.MVector @a+ basicUnsafeRead = coerce $ M.basicUnsafeRead @B.MVector @a+ basicUnsafeWrite = coerce $ M.basicUnsafeWrite @B.MVector @a+ basicClear = coerce $ M.basicClear @B.MVector @a+ basicSet = coerce $ M.basicSet @B.MVector @a+ basicUnsafeCopy = coerce $ M.basicUnsafeCopy @B.MVector @a+ basicUnsafeMove = coerce $ M.basicUnsafeMove @B.MVector @a+ basicUnsafeGrow = coerce $ M.basicUnsafeGrow @B.MVector @a++instance G.Vector Vector (DoNotUnboxLazy a) where+ {-# INLINE basicUnsafeFreeze #-}+ {-# INLINE basicUnsafeThaw #-}+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicUnsafeIndexM #-}+ {-# INLINE elemseq #-}+ basicUnsafeFreeze = coerce $ G.basicUnsafeFreeze @B.Vector @a+ basicUnsafeThaw = coerce $ G.basicUnsafeThaw @B.Vector @a+ basicLength = coerce $ G.basicLength @B.Vector @a+ basicUnsafeSlice = coerce $ G.basicUnsafeSlice @B.Vector @a+ basicUnsafeIndexM = coerce $ G.basicUnsafeIndexM @B.Vector @a+ basicUnsafeCopy = coerce $ G.basicUnsafeCopy @B.Vector @a+ elemseq _ = seq++instance Unbox (DoNotUnboxLazy a)++-- | Newtype which allows to derive unbox instances for type @a@ which+-- is normally a "boxed" type. The newtype stictly evaluates the wrapped values+-- ensuring that the unboxed vector contains no (direct) thunks.+-- For a less strict newtype wrapper, see 'DoNotUnboxLazy'.+-- For a more strict newtype wrapper, see 'DoNotUnboxNormalForm'.+--+-- 'DoNotUnboxStrict' is intended to be unsed in conjunction with the newtype 'As'+-- and the type class 'IsoUnbox'. Here's an example which uses the following+-- explicit 'IsoUnbox' instance:+--+--+-- >>> :set -XBangPatterns -XTypeFamilies -XStandaloneDeriving -XDerivingVia+-- >>> :set -XMultiParamTypeClasses -XTypeOperators -XFlexibleInstances+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> import qualified Data.Vector.Unboxed.Mutable as VUM+-- >>> import qualified Data.Vector.Generic as VG+-- >>> import qualified Data.Vector.Generic.Mutable as VGM+-- >>> :{+-- >>> data Bar a = Bar Int a+-- >>> deriving Show+-- >>> instance VU.IsoUnbox (Bar a) (Int, VU.DoNotUnboxStrict a) where+-- >>> toURepr (Bar i !a) = (i, VU.DoNotUnboxStrict a)+-- >>> fromURepr (i, VU.DoNotUnboxStrict a) = Bar i a+-- >>> {-# INLINE toURepr #-}+-- >>> {-# INLINE fromURepr #-}+-- >>> newtype instance VU.MVector s (Bar a) = MV_Bar (VU.MVector s (Int, VU.DoNotUnboxStrict a))+-- >>> newtype instance VU.Vector (Bar a) = V_Bar (VU.Vector (Int, VU.DoNotUnboxStrict a))+-- >>> deriving via (Bar a `VU.As` (Int, VU.DoNotUnboxStrict a)) instance VGM.MVector VUM.MVector (Bar a)+-- >>> deriving via (Bar a `VU.As` (Int, VU.DoNotUnboxStrict a)) instance VG.Vector VU.Vector (Bar a)+-- >>> instance VU.Unbox (Bar a)+-- >>> :}+--+-- >>> VU.fromListN 3 [ Bar 3 "Bye", Bar 2 "for", Bar 1 "now" ]+-- [Bar 3 "Bye",Bar 2 "for",Bar 1 "now"]+--+-- @since 0.13.2.0+newtype DoNotUnboxStrict a = DoNotUnboxStrict a++newtype instance MVector s (DoNotUnboxStrict a) = MV_DoNotUnboxStrict (S.MVector s a)+newtype instance Vector (DoNotUnboxStrict a) = V_DoNotUnboxStrict (S.Vector a)++instance M.MVector MVector (DoNotUnboxStrict a) where+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicOverlaps #-}+ {-# INLINE basicUnsafeNew #-}+ {-# INLINE basicInitialize #-}+ {-# INLINE basicUnsafeReplicate #-}+ {-# INLINE basicUnsafeRead #-}+ {-# INLINE basicUnsafeWrite #-}+ {-# INLINE basicClear #-}+ {-# INLINE basicSet #-}+ {-# INLINE basicUnsafeCopy #-}+ {-# INLINE basicUnsafeGrow #-}+ basicLength = coerce $ M.basicLength @S.MVector @a+ basicUnsafeSlice = coerce $ M.basicUnsafeSlice @S.MVector @a+ basicOverlaps = coerce $ M.basicOverlaps @S.MVector @a+ basicUnsafeNew = coerce $ M.basicUnsafeNew @S.MVector @a+ basicInitialize = coerce $ M.basicInitialize @S.MVector @a+ basicUnsafeReplicate = coerce $ M.basicUnsafeReplicate @S.MVector @a+ basicUnsafeRead = coerce $ M.basicUnsafeRead @S.MVector @a+ basicUnsafeWrite = coerce $ M.basicUnsafeWrite @S.MVector @a+ basicClear = coerce $ M.basicClear @S.MVector @a+ basicSet = coerce $ M.basicSet @S.MVector @a+ basicUnsafeCopy = coerce $ M.basicUnsafeCopy @S.MVector @a+ basicUnsafeMove = coerce $ M.basicUnsafeMove @S.MVector @a+ basicUnsafeGrow = coerce $ M.basicUnsafeGrow @S.MVector @a++instance G.Vector Vector (DoNotUnboxStrict a) where+ {-# INLINE basicUnsafeFreeze #-}+ {-# INLINE basicUnsafeThaw #-}+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicUnsafeIndexM #-}+ {-# INLINE elemseq #-}+ basicUnsafeFreeze = coerce $ G.basicUnsafeFreeze @S.Vector @a+ basicUnsafeThaw = coerce $ G.basicUnsafeThaw @S.Vector @a+ basicLength = coerce $ G.basicLength @S.Vector @a+ basicUnsafeSlice = coerce $ G.basicUnsafeSlice @S.Vector @a+ basicUnsafeIndexM = coerce $ G.basicUnsafeIndexM @S.Vector @a+ basicUnsafeCopy = coerce $ G.basicUnsafeCopy @S.Vector @a+ elemseq _ = seq++instance Unbox (DoNotUnboxStrict a)++-- | Newtype which allows to derive unbox instances for type @a@ which+-- is normally a "boxed" type. The newtype stictly evaluates the wrapped values+-- via thier requisite 'NFData' instance, ensuring that the unboxed vector+-- contains only values reduced to normal form.+-- For a less strict newtype wrappers, see 'DoNotUnboxLazy' and 'DoNotUnboxStrict'.+--+-- 'DoNotUnboxNormalForm' is intended to be unsed in conjunction with the newtype 'As'+-- and the type class 'IsoUnbox'. Here's an example which uses the following+-- explicit 'IsoUnbox' instance:+--+--+-- >>> :set -XTypeFamilies -XStandaloneDeriving -XDerivingVia+-- >>> :set -XMultiParamTypeClasses -XTypeOperators -XFlexibleInstances+-- >>> import qualified Data.Vector.Unboxed as VU+-- >>> import qualified Data.Vector.Unboxed.Mutable as VUM+-- >>> import qualified Data.Vector.Generic as VG+-- >>> import qualified Data.Vector.Generic.Mutable as VGM+-- >>> import qualified Control.DeepSeq as NF+-- >>> :{+-- >>> data Baz a = Baz Int a+-- >>> deriving Show+-- >>> instance NF.NFData a => VU.IsoUnbox (Baz a) (Int, VU.DoNotUnboxNormalForm a) where+-- >>> toURepr (Baz i a) = (i, VU.DoNotUnboxNormalForm $ NF.force a)+-- >>> fromURepr (i, VU.DoNotUnboxNormalForm a) = Baz i a+-- >>> {-# INLINE toURepr #-}+-- >>> {-# INLINE fromURepr #-}+-- >>> newtype instance VU.MVector s (Baz a) = MV_Baz (VU.MVector s (Int, VU.DoNotUnboxNormalForm a))+-- >>> newtype instance VU.Vector (Baz a) = V_Baz (VU.Vector (Int, VU.DoNotUnboxNormalForm a))+-- >>> deriving via (Baz a `VU.As` (Int, VU.DoNotUnboxNormalForm a)) instance NF.NFData a => VGM.MVector VUM.MVector (Baz a)+-- >>> deriving via (Baz a `VU.As` (Int, VU.DoNotUnboxNormalForm a)) instance NF.NFData a => VG.Vector VU.Vector (Baz a)+-- >>> instance NF.NFData a => VU.Unbox (Baz a)+-- >>> :}+--+-- >>> VU.fromListN 3 [ Baz 3 "Fully", Baz 9 "evaluated", Baz 27 "data" ]+-- [Baz 3 "Fully",Baz 9 "evaluated",Baz 27 "data"]+--+-- @since 0.13.2.0+newtype DoNotUnboxNormalForm a = DoNotUnboxNormalForm a++newtype instance MVector s (DoNotUnboxNormalForm a) = MV_DoNotUnboxNormalForm (S.MVector s a)+newtype instance Vector (DoNotUnboxNormalForm a) = V_DoNotUnboxNormalForm (S.Vector a)++instance NFData a => M.MVector MVector (DoNotUnboxNormalForm a) where+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicOverlaps #-}+ {-# INLINE basicUnsafeNew #-}+ {-# INLINE basicInitialize #-}+ {-# INLINE basicUnsafeReplicate #-}+ {-# INLINE basicUnsafeRead #-}+ {-# INLINE basicUnsafeWrite #-}+ {-# INLINE basicClear #-}+ {-# INLINE basicSet #-}+ {-# INLINE basicUnsafeCopy #-}+ {-# INLINE basicUnsafeGrow #-}+ basicLength = coerce $ M.basicLength @S.MVector @a+ basicUnsafeSlice = coerce $ M.basicUnsafeSlice @S.MVector @a+ basicOverlaps = coerce $ M.basicOverlaps @S.MVector @a+ basicUnsafeNew = coerce $ M.basicUnsafeNew @S.MVector @a+ basicInitialize = coerce $ M.basicInitialize @S.MVector @a+ basicUnsafeReplicate = coerce (\i x -> M.basicUnsafeReplicate @S.MVector @a i (force x))+ basicUnsafeRead = coerce $ M.basicUnsafeRead @S.MVector @a+ basicUnsafeWrite = coerce (\v i x -> M.basicUnsafeWrite @S.MVector @a v i (force x))+ basicClear = coerce $ M.basicClear @S.MVector @a+ basicSet = coerce (\v x -> M.basicSet @S.MVector @a v (force x))+ basicUnsafeCopy = coerce $ M.basicUnsafeCopy @S.MVector @a+ basicUnsafeMove = coerce $ M.basicUnsafeMove @S.MVector @a+ basicUnsafeGrow = coerce $ M.basicUnsafeGrow @S.MVector @a++instance NFData a => G.Vector Vector (DoNotUnboxNormalForm a) where+ {-# INLINE basicUnsafeFreeze #-}+ {-# INLINE basicUnsafeThaw #-}+ {-# INLINE basicLength #-}+ {-# INLINE basicUnsafeSlice #-}+ {-# INLINE basicUnsafeIndexM #-}+ {-# INLINE elemseq #-}+ basicUnsafeFreeze = coerce $ G.basicUnsafeFreeze @S.Vector @a+ basicUnsafeThaw = coerce $ G.basicUnsafeThaw @S.Vector @a+ basicLength = coerce $ G.basicLength @S.Vector @a+ basicUnsafeSlice = coerce $ G.basicUnsafeSlice @S.Vector @a+ basicUnsafeIndexM = coerce $ G.basicUnsafeIndexM @S.Vector @a+ basicUnsafeCopy = coerce $ G.basicUnsafeCopy @S.Vector @a+ elemseq _ x y = rnf (coerce x :: a) `seq` y++instance NFData a => Unbox (DoNotUnboxNormalForm a)+ deriveNewtypeInstances((), Any, Bool, Any, V_Any, MV_Any) deriveNewtypeInstances((), All, Bool, All, V_All, MV_All)
src/Data/Vector/Unboxed/Mutable.hs view
@@ -42,6 +42,7 @@ clear, -- * Zipping and unzipping+ -- $zip zip, zip3, zip4, zip5, zip6, unzip, unzip3, unzip4, unzip5, unzip6, @@ -57,7 +58,8 @@ ifoldr, ifoldr', ifoldrM, ifoldrM', -- * Modifying vectors- nextPermutation,+ nextPermutation, nextPermutationBy,+ prevPermutation, prevPermutationBy, -- ** Filling and copying set, copy, move, unsafeCopy, unsafeMove,@@ -70,7 +72,7 @@ import Data.Vector.Fusion.Util ( delayed_min ) import Control.Monad.Primitive -import Prelude ( Ord, Bool, Int, Maybe )+import Prelude ( Ord, Bool, Int, Maybe, Ordering(..) ) -- don't import an unused Data.Vector.Internal.Check #define NOT_VECTOR_MODULE@@ -443,11 +445,45 @@ -- ----------------- -- | Compute the (lexicographically) next permutation of the given vector in-place.--- Returns False when the input is the last permutation.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@. nextPermutation :: (PrimMonad m,Ord e,Unbox e) => MVector (PrimState m) e -> m Bool {-# INLINE nextPermutation #-} nextPermutation = G.nextPermutation +-- | Compute the (lexicographically) next permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly descending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::next_permutation@.+--+-- @since 0.13.2.0+nextPermutationBy :: (PrimMonad m,Unbox e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE nextPermutationBy #-}+nextPermutationBy = G.nextPermutationBy++-- | Compute the (lexicographically) previous permutation of the given vector in-place.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutation :: (PrimMonad m,Ord e,Unbox e) => MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutation #-}+prevPermutation = G.prevPermutation++-- | Compute the (lexicographically) previous permutation of the given vector in-place,+-- using the provided comparison function.+-- Returns False when the input is the last item in the enumeration, i.e., if it is in+-- weakly ascending order. In this case the vector will not get updated,+-- as opposed to the behavior of the C++ function @std::prev_permutation@.+--+-- @since 0.13.2.0+prevPermutationBy :: (PrimMonad m,Unbox e) => (e -> e -> Ordering) -> MVector (PrimState m) e -> m Bool+{-# INLINE prevPermutationBy #-}+prevPermutationBy = G.prevPermutationBy+ -- Folds -- ----- @@ -596,6 +632,13 @@ {-# INLINE ifoldrM' #-} ifoldrM' = G.ifoldrM' ++-- $zip+--+-- Following functions provide access to the representation of vector+-- of tuples. Internally it's product of vectors for each element of+-- tuple. Conversions are performed in /O(1)/ and produced vector will+-- share underlying buffers with parameter vectors. #define DEFINE_MUTABLE #include "unbox-tuple-instances"
tests/Boilerplater.hs view
@@ -1,5 +1,6 @@ module Boilerplater where +import Data.List (stripPrefix) import Test.Tasty.QuickCheck import Language.Haskell.TH@@ -8,20 +9,4 @@ testProperties :: [Name] -> Q Exp testProperties nms = fmap ListE $ sequence [[| testProperty $(stringE prop_name) $(varE nm) |] | nm <- nms- , Just prop_name <- [stripPrefix_maybe "prop_" (nameBase nm)]]---- This nice clean solution doesn't quite work since I need to use lexically-scoped type--- variables, which aren't supported by Template Haskell. Argh!--- testProperties :: Q [Dec] -> Q Exp--- testProperties mdecs = do--- decs <- mdecs--- property_exprs <- sequence [[| testProperty "$prop_name" $(return $ VarE nm) |]--- | FunD nm _clauses <- decs--- , Just prop_name <- [stripPrefix_maybe "prop_" (nameBase nm)]]--- return $ LetE decs (ListE property_exprs)--stripPrefix_maybe :: String -> String -> Maybe String-stripPrefix_maybe prefix what- | what_start == prefix = Just what_end- | otherwise = Nothing- where (what_start, what_end) = splitAt (length prefix) what+ , Just prop_name <- [stripPrefix "prop_" (nameBase nm)]]
tests/Main.hs view
@@ -1,15 +1,25 @@ module Main (main) where -import qualified Tests.Vector import qualified Tests.Vector.UnitTests+import qualified Tests.Vector.Boxed+import qualified Tests.Vector.Primitive+import qualified Tests.Vector.Storable+import qualified Tests.Vector.Strict+import qualified Tests.Vector.Unboxed import qualified Tests.Bundle import qualified Tests.Move import Test.Tasty (defaultMain,testGroup) main :: IO ()-main = defaultMain $ testGroup "toplevel" $ Tests.Bundle.tests- ++ Tests.Vector.tests- ++ Tests.Vector.UnitTests.tests- ++ Tests.Move.tests-+main = defaultMain $ testGroup "toplevel" $ concat+ [ Tests.Bundle.tests+ , [ testGroup "Tests.Vector.Boxed" Tests.Vector.Boxed.tests+ , testGroup "Tests.Vector.Primitive" Tests.Vector.Primitive.tests+ , testGroup "Tests.Vector.Storable" Tests.Vector.Storable.tests+ , testGroup "Tests.Vector.Strict" Tests.Vector.Strict.tests+ , testGroup "Tests.Vector.Unboxed" Tests.Vector.Unboxed.tests+ ]+ , Tests.Vector.UnitTests.tests+ , Tests.Move.tests+ ]
− tests/Setup.hs
@@ -1,3 +0,0 @@-import Distribution.Simple-main = defaultMain-
tests/Tests/Move.hs view
@@ -7,8 +7,8 @@ import Utilities () import Control.Monad (replicateM)-import Control.Monad.ST (runST)-import Data.List (sort,permutations)+import Control.Monad.ST (ST, runST)+import Data.List (sort,sortBy,permutations) import qualified Data.Vector.Generic as G import qualified Data.Vector.Generic.Mutable as M@@ -41,9 +41,39 @@ testPermutations :: Bool testPermutations = all checkPermutations [1..7] +checkRevPermutations :: Int -> Bool+checkRevPermutations n = runST $ do+ vec <- U.thaw (U.fromList [n,n-1..1])+ res <- replicateM (product [1..n]) $ M.prevPermutation vec >> U.freeze vec >>= return . U.toList+ return $! ([n,n-1..1] : res) == sortBy (flip compare) (permutations [n,n-1..1]) ++ [[1..n]]++testRevPermutations :: Bool+testRevPermutations = all checkRevPermutations [1..7]++nextPermutationBijective :: (M.MVector v a, Ord a) => v s a -> ST s ()+nextPermutationBijective v = do+ res <- M.nextPermutation v+ if res then return () else M.reverse v++prevPermutationBijective :: (M.MVector v a, Ord a) => v s a -> ST s ()+prevPermutationBijective v = do+ res <- M.prevPermutation v+ if res then return () else M.reverse v++testNPPermutationIsId :: (G.Vector v a, Ord a, Show (v a), Eq (v a)) => v a -> Property +testNPPermutationIsId v = v === G.modify (\mv -> nextPermutationBijective mv >> prevPermutationBijective mv) v++testPNPermutationIsId :: (G.Vector v a, Ord a, Show (v a), Eq (v a)) => v a -> Property+testPNPermutationIsId v = v === G.modify (\mv -> prevPermutationBijective mv >> nextPermutationBijective mv) v+ tests = [testProperty "Data.Vector.Mutable (Move)" (testMove :: V.Vector Int -> Property), testProperty "Data.Vector.Primitive.Mutable (Move)" (testMove :: P.Vector Int -> Property), testProperty "Data.Vector.Unboxed.Mutable (Move)" (testMove :: U.Vector Int -> Property), testProperty "Data.Vector.Storable.Mutable (Move)" (testMove :: S.Vector Int -> Property),- testProperty "Data.Vector.Generic.Mutable (nextPermutation)" testPermutations]+ testProperty "Data.Vector.Generic.Mutable (nextPermutation)" testPermutations,+ testProperty "Data.Vector.Generic.Mutable (prevPermutation)" testRevPermutations,+ testProperty "Data.Vector.Generic.Mutable (nextPermutation then prevPermutation = id)" + (testNPPermutationIsId :: U.Vector Int -> Property),+ testProperty "Data.Vector.Generic.Mutable (prevPermutation then nextPermutation = id)"+ (testPNPermutationIsId :: U.Vector Int -> Property)]
− tests/Tests/Vector.hs
@@ -1,15 +0,0 @@-{-# LANGUAGE ConstraintKinds #-}-module Tests.Vector (tests) where--import Test.Tasty (testGroup)-import qualified Tests.Vector.Boxed-import qualified Tests.Vector.Primitive-import qualified Tests.Vector.Storable-import qualified Tests.Vector.Unboxed--tests =- [ testGroup "Tests.Vector.Boxed" Tests.Vector.Boxed.tests- , testGroup "Tests.Vector.Primitive" Tests.Vector.Primitive.tests- , testGroup "Tests.Vector.Storable" Tests.Vector.Storable.tests- , testGroup "Tests.Vector.Unboxed" Tests.Vector.Unboxed.tests- ]
tests/Tests/Vector/Property.hs view
@@ -171,6 +171,7 @@ 'prop_partition, {- 'prop_unstablePartition, -} 'prop_partitionWith, 'prop_span, 'prop_break,+ 'prop_spanR, 'prop_breakR, 'prop_groupBy, -- Searching@@ -337,6 +338,8 @@ = V.partitionWith `eq` partitionWith prop_span :: P ((a -> Bool) -> v a -> (v a, v a)) = V.span `eq` span prop_break :: P ((a -> Bool) -> v a -> (v a, v a)) = V.break `eq` break+ prop_spanR :: P ((a -> Bool) -> v a -> (v a, v a)) = V.spanR `eq` spanR+ prop_breakR :: P ((a -> Bool) -> v a -> (v a, v a)) = V.breakR `eq` breakR prop_groupBy :: P ((a -> a -> Bool) -> v a -> [v a]) = V.groupBy `eq` groupBy prop_elem :: P (a -> v a -> Bool) = V.elem `eq` elem
+ tests/Tests/Vector/Strict.hs view
@@ -0,0 +1,52 @@+{-# LANGUAGE ConstraintKinds #-}+module Tests.Vector.Strict (tests) where++import Test.Tasty+import qualified Data.Vector.Strict+import Tests.Vector.Property++import GHC.Exts (inline)+++testGeneralBoxedVector+ :: forall a. (CommonContext a Data.Vector.Strict.Vector, Ord a, Data a)+ => Data.Vector.Strict.Vector a -> [TestTree]+testGeneralBoxedVector dummy = concatMap ($ dummy)+ [+ testSanity+ , inline testPolymorphicFunctions+ , testOrdFunctions+ , testTuplyFunctions+ , testNestedVectorFunctions+ , testMonoidFunctions+ , testFunctorFunctions+ , testMonadFunctions+ , testApplicativeFunctions+ , testAlternativeFunctions+ , testSequenceFunctions+ , testDataFunctions+ ]++testBoolBoxedVector dummy = concatMap ($ dummy)+ [+ testGeneralBoxedVector+ , testBoolFunctions+ ]++testNumericBoxedVector+ :: forall a. (CommonContext a Data.Vector.Strict.Vector, Ord a, Num a, Enum a, Random a, Data a)+ => Data.Vector.Strict.Vector a -> [TestTree]+testNumericBoxedVector dummy = concatMap ($ dummy)+ [+ testGeneralBoxedVector+ , testNumFunctions+ , testEnumFunctions+ ]++tests =+ [ testGroup "Bool" $+ testBoolBoxedVector (undefined :: Data.Vector.Strict.Vector Bool)+ , testGroup "Int" $+ testNumericBoxedVector (undefined :: Data.Vector.Strict.Vector Int)+ , testGroup "unstream" $ testUnstream (undefined :: Data.Vector.Strict.Vector Int)+ ]
tests/Utilities.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE DefaultSignatures #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE GADTs #-}@@ -6,12 +7,14 @@ import Test.QuickCheck +import Control.Arrow ((***)) import Data.Foldable import Data.Bifunctor import qualified Data.Vector as DV import qualified Data.Vector.Generic as DVG import qualified Data.Vector.Primitive as DVP import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Strict as DVV import qualified Data.Vector.Unboxed as DVU import qualified Data.Vector.Fusion.Bundle as S @@ -43,6 +46,12 @@ instance (CoArbitrary a, DVS.Storable a) => CoArbitrary (DVS.Vector a) where coarbitrary = coarbitrary . DVS.toList +instance (Arbitrary a) => Arbitrary (DVV.Vector a) where+ arbitrary = fmap DVV.fromList arbitrary++instance (CoArbitrary a) => CoArbitrary (DVV.Vector a) where+ coarbitrary = coarbitrary . DVV.toList+ instance (Arbitrary a, DVU.Unbox a) => Arbitrary (DVU.Vector a) where arbitrary = fmap DVU.fromList arbitrary @@ -95,6 +104,11 @@ model = map model . DVS.toList unmodel = DVS.fromList . map unmodel +instance (Eq a, TestData a) => TestData (DVV.Vector a) where+ type Model (DVV.Vector a) = [Model a]+ model = map model . DVV.toList+ unmodel = DVV.fromList . map unmodel+ instance (Eq a, DVU.Unbox a, TestData a) => TestData (DVU.Vector a) where type Model (DVU.Vector a) = [Model a] model = map model . DVU.toList@@ -291,6 +305,12 @@ imapMaybe f = catMaybes . withIndexFirst map f indexedLeftFold fld f z = fld (uncurry . f) z . zip [0..]++spanR :: (a -> Bool) -> [a] -> ([a], [a])+spanR f = (reverse *** reverse) . span f . reverse++breakR :: (a -> Bool) -> [a] -> ([a], [a])+breakR f = (reverse *** reverse) . break f . reverse ifoldl :: (a -> Int -> a -> a) -> a -> [a] -> a ifoldl = indexedLeftFold foldl
tests/doctests.hs view
@@ -25,6 +25,9 @@ , [ "src/Data/Vector.hs" , "src/Data/Vector/Mutable.hs" ]+ , [ "src/Data/Vector/Strict.hs"+ , "src/Data/Vector/Strict/Mutable.hs"+ ] , [ "src/Data/Vector/Generic.hs" , "src/Data/Vector/Generic/Mutable.hs" ]
vector.cabal view
@@ -1,7 +1,9 @@+Cabal-Version: 3.0+Build-Type: Simple Name: vector-Version: 0.13.1.0+Version: 0.13.2.0 -- don't forget to update the changelog file!-License: BSD3+License: BSD-3-Clause License-File: LICENSE Author: Roman Leshchinskiy <rl@cse.unsw.edu.au> Maintainer: Haskell Libraries Team <libraries@haskell.org>@@ -42,30 +44,31 @@ * <http://haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial> Tested-With:- GHC == 8.0.2,- GHC == 8.2.2,- GHC == 8.4.4,- GHC == 8.6.5,- GHC == 8.8.4,- GHC == 8.10.7,- GHC == 9.0.2,- GHC == 9.2.8,- GHC == 9.4.6,- GHC == 9.6.2- --Cabal-Version: >= 1.10-Build-Type: Simple+ GHC == 8.0.2+ GHC == 8.2.2+ GHC == 8.4.4+ GHC == 8.6.5+ GHC == 8.8.4+ GHC == 8.10.7+ GHC == 9.0.2+ GHC == 9.2.8+ GHC == 9.4.8+ GHC == 9.6.4+ GHC == 9.8.2 -Extra-Source-Files:+Extra-doc-files: changelog.md README.md tests/LICENSE- tests/Setup.hs- tests/Main.hs+Extra-Source-Files: internal/GenUnboxTuple.hs internal/unbox-tuple-instances +source-repository head+ type: git+ location: https://github.com/haskell/vector.git+ subdir: vector+ Flag BoundsChecks Description: Enable bounds checking Default: True@@ -88,8 +91,17 @@ Default: False Manual: True +-- This common sets warning flags passed to GHC as controlled by Wall cabal flag+common flag-Wall+ Ghc-Options: -Wall+ if !flag(Wall)+ Ghc-Options: -fno-warn-orphans+ if impl(ghc >= 8.0) && impl(ghc < 8.1)+ Ghc-Options: -Wno-redundant-constraints + Library+ import: flag-Wall Default-Language: Haskell2010 Other-Extensions: BangPatterns@@ -133,6 +145,9 @@ Data.Vector.Unboxed.Mutable Data.Vector.Unboxed + Data.Vector.Strict.Mutable+ Data.Vector.Strict+ Data.Vector.Mutable Data.Vector @@ -145,18 +160,12 @@ Install-Includes: vector.h - Build-Depends: base >= 4.9 && < 4.20+ Build-Depends: base >= 4.9 && < 4.22 , primitive >= 0.6.4.0 && < 0.10 , deepseq >= 1.1 && < 1.6 , vector-stream >= 0.1 && < 0.2 - Ghc-Options: -O2 -Wall-- if !flag(Wall)- Ghc-Options: -fno-warn-orphans-- if impl(ghc >= 8.0) && impl(ghc < 8.1)- Ghc-Options: -Wno-redundant-constraints+ Ghc-Options: -O2 if flag(BoundsChecks) cpp-options: -DVECTOR_BOUNDS_CHECKS@@ -167,37 +176,39 @@ if flag(InternalChecks) cpp-options: -DVECTOR_INTERNAL_CHECKS -source-repository head- type: git- location: https://github.com/haskell/vector.git- subdir: vector --test-suite vector-tests-O0+-- We want to build test suite in two variants. One built with -O0+-- and another with -O2 in order to catch bugs caused by invalid+-- rewrite rules+common tests-common Default-Language: Haskell2010- type: exitcode-stdio-1.0- Main-Is: Main.hs-- other-modules: Boilerplater- Tests.Bundle- Tests.Move- Tests.Vector- Tests.Vector.Property- Tests.Vector.Boxed- Tests.Vector.Storable- Tests.Vector.Primitive- Tests.Vector.Unboxed- Tests.Vector.UnitTests- Utilities-- hs-source-dirs: tests- Build-Depends: base >= 4.5 && < 5, template-haskell, base-orphans >= 0.6, vector,- primitive, random,- QuickCheck >= 2.9 && < 2.15, HUnit, tasty,- tasty-hunit, tasty-quickcheck,- transformers >= 0.2.0.0+ Ghc-Options: -fno-warn-missing-signatures+ hs-source-dirs: tests+ Build-Depends: base >= 4.5 && < 5+ , template-haskell+ , base-orphans >= 0.6+ , vector+ , primitive+ , random+ , QuickCheck >= 2.9 && < 2.15+ , tasty+ , tasty-hunit+ , tasty-quickcheck+ , transformers >= 0.2.0.0+ Other-Modules:+ Boilerplater+ Tests.Bundle+ Tests.Move+ Tests.Vector.Property+ Tests.Vector.Boxed+ Tests.Vector.Strict+ Tests.Vector.Storable+ Tests.Vector.Primitive+ Tests.Vector.Unboxed+ Tests.Vector.UnitTests+ Utilities - default-extensions: CPP,+ default-extensions: ScopedTypeVariables, PatternGuards, MultiParamTypeClasses,@@ -207,75 +218,30 @@ TypeFamilies, TemplateHaskell - Ghc-Options: -O0 -threaded- Ghc-Options: -Wall-- if !flag(Wall)- Ghc-Options: -fno-warn-orphans -fno-warn-missing-signatures- if impl(ghc >= 8.0) && impl(ghc < 8.1)- Ghc-Options: -Wno-redundant-constraints-+test-suite vector-tests-O0+ import: flag-Wall, tests-common+ type: exitcode-stdio-1.0+ Main-Is: Main.hs+ Ghc-Options: -O0 -threaded test-suite vector-tests-O2- Default-Language: Haskell2010- type: exitcode-stdio-1.0- Main-Is: Main.hs-- other-modules: Boilerplater- Tests.Bundle- Tests.Move- Tests.Vector- Tests.Vector.Property- Tests.Vector.Boxed- Tests.Vector.Storable- Tests.Vector.Primitive- Tests.Vector.Unboxed- Tests.Vector.UnitTests- Utilities-- hs-source-dirs: tests- Build-Depends: base >= 4.5 && < 5, template-haskell, base-orphans >= 0.6, vector,- primitive, random,- QuickCheck >= 2.9 && < 2.15, HUnit, tasty,- tasty-hunit, tasty-quickcheck,- transformers >= 0.2.0.0-- default-extensions: CPP,- ScopedTypeVariables,- PatternGuards,- MultiParamTypeClasses,- FlexibleContexts,- RankNTypes,- TypeSynonymInstances,- TypeFamilies,- TemplateHaskell-- Ghc-Options: -Wall- Ghc-Options: -O2 -threaded- if !flag(Wall)- Ghc-Options: -fno-warn-orphans -fno-warn-missing-signatures- if impl(ghc >= 8.0) && impl(ghc < 8.1)- Ghc-Options: -Wno-redundant-constraints+ import: flag-Wall, tests-common+ type: exitcode-stdio-1.0+ Main-Is: Main.hs+ Ghc-Options: -O2 -threaded test-suite vector-doctest type: exitcode-stdio-1.0 main-is: doctests.hs hs-source-dirs: tests default-language: Haskell2010- -- Older GHC don't support DerivingVia+ -- Older GHC don't support DerivingVia and doctests use them if impl(ghc < 8.6) buildable: False- -- GHC 8.10 fails to run doctests for some reason- if impl(ghc >= 8.10) && impl(ghc < 8.11)- buildable: False- -- GHC 9.0 fails to run doctests for some reason too- if impl(ghc >= 9.0) && impl(ghc < 9.1)- buildable: False- -- And GHC 9.2 too- if impl(ghc >= 9.2) && impl(ghc < 9.2.3)+ -- Attempts to run doctests on macos on GHC8.10 and 9.0 cause linker errors:+ -- > ld: warning: -undefined dynamic_lookup may not work with chained fixups+ if os(darwin) && impl(ghc >= 8.10) && impl(ghc < 9.2) buildable: False- if impl(ghc >= 9.2.3) && impl(ghc < 9.3)- buildable: True build-depends: base -any , doctest >=0.15 && <0.23@@ -283,9 +249,9 @@ , vector -any test-suite vector-inspection+ import: flag-Wall type: exitcode-stdio-1.0 hs-source-dirs: tests-inspect- Ghc-Options: -Wall main-is: main.hs default-language: Haskell2010 Other-modules: Inspect@@ -299,6 +265,32 @@ , tasty , tasty-inspection-testing >= 0.1 +library benchmarks-O2+ visibility: public+ ghc-options: -O2+ hs-source-dirs: benchlib+ Default-Language: Haskell2010+ build-depends:+ base+ , random >= 1.2+ , tasty+ , vector+ exposed-modules:+ Bench.Vector.Algo.MutableSet+ Bench.Vector.Algo.ListRank+ Bench.Vector.Algo.Rootfix+ Bench.Vector.Algo.Leaffix+ Bench.Vector.Algo.AwShCC+ Bench.Vector.Algo.HybCC+ Bench.Vector.Algo.Quickhull+ Bench.Vector.Algo.Spectral+ Bench.Vector.Algo.Tridiag+ Bench.Vector.Algo.FindIndexR+ Bench.Vector.Algo.NextPermutation+ Bench.Vector.TestData.ParenTree+ Bench.Vector.TestData.Graph+ Bench.Vector.Tasty+ benchmark algorithms type: exitcode-stdio-1.0 main-is: Main.hs@@ -311,19 +303,6 @@ , tasty , tasty-bench >= 0.2.1 , vector+ , vector:benchmarks-O2 ghc-options: -O2-- other-modules:- Algo.MutableSet- Algo.ListRank- Algo.Rootfix- Algo.Leaffix- Algo.AwShCC- Algo.HybCC- Algo.Quickhull- Algo.Spectral- Algo.Tridiag- Algo.FindIndexR- TestData.ParenTree- TestData.Graph