vector 0.7.0.1 → 0.7.1
raw patch · 20 files changed
+840/−93 lines, 20 files
Files
- Data/Vector.hs +74/−6
- Data/Vector/Fusion/Stream.hs +6/−1
- Data/Vector/Fusion/Stream/Monadic.hs +17/−0
- Data/Vector/Fusion/Util.hs +5/−1
- Data/Vector/Generic.hs +118/−13
- Data/Vector/Generic/Mutable.hs +61/−4
- Data/Vector/Mutable.hs +101/−5
- Data/Vector/Primitive.hs +46/−5
- Data/Vector/Primitive/Mutable.hs +46/−4
- Data/Vector/Storable.hs +66/−7
- Data/Vector/Storable/Mutable.hs +88/−7
- Data/Vector/Unboxed.hs +58/−5
- Data/Vector/Unboxed/Base.hs +3/−0
- Data/Vector/Unboxed/Mutable.hs +41/−4
- benchmarks/vector-benchmarks.cabal +3/−3
- internal/GenUnboxTuple.hs +7/−1
- internal/unbox-tuple-instances +79/−24
- tests/Main.hs +2/−0
- tests/vector-tests.cabal +1/−1
- vector.cabal +18/−2
Data/Vector.hs view
@@ -40,16 +40,16 @@ unsafeIndexM, unsafeHeadM, unsafeLastM, -- ** Extracting subvectors (slicing)- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- * Construction -- ** Initialisation- empty, singleton, replicate, generate,+ empty, singleton, replicate, generate, iterateN, -- ** Monadic initialisation- replicateM, create,+ replicateM, generateM, create, -- ** Unfolding unfoldr, unfoldrN,@@ -81,6 +81,9 @@ -- * Elementwise operations + -- ** Indexing+ indexed,+ -- ** Mapping map, imap, concatMap, @@ -122,7 +125,11 @@ -- ** Monadic folds foldM, foldM', fold1M, fold1M',+ foldM_, foldM'_, fold1M_, fold1M'_, + -- ** Monadic sequencing+ sequence, sequence_,+ -- * Prefix sums (scans) prescanl, prescanl', postscanl, postscanl',@@ -155,7 +162,7 @@ import Prelude hiding ( length, null, replicate, (++), concat, head, last,- init, tail, take, drop, reverse,+ init, tail, take, drop, splitAt, reverse, map, concatMap, zipWith, zipWith3, zip, zip3, unzip, unzip3, filter, takeWhile, dropWhile, span, break,@@ -164,7 +171,7 @@ all, any, and, or, sum, product, minimum, maximum, scanl, scanl1, scanr, scanr1, enumFromTo, enumFromThenTo,- mapM, mapM_ )+ mapM, mapM_, sequence, sequence_ ) import qualified Prelude @@ -387,6 +394,14 @@ {-# 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.+{-# INLINE splitAt #-}+splitAt :: Int -> Vector a -> (Vector a, Vector a)+splitAt = G.splitAt+ -- | /O(1)/ Yield a slice of the vector without copying. The vector must -- contain at least @i+n@ elements but this is not checked. unsafeSlice :: Int -- ^ @i@ starting index@@ -444,6 +459,11 @@ {-# INLINE generate #-} generate = G.generate +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Int -> (a -> a) -> a -> Vector a+{-# INLINE iterateN #-}+iterateN = G.iterateN+ -- Unfolding -- --------- @@ -534,6 +554,12 @@ {-# INLINE replicateM #-} replicateM = G.replicateM +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)+{-# INLINE generateM #-}+generateM = G.generateM+ -- | Execute the monadic action and freeze the resulting vector. -- -- @@@ -720,6 +746,14 @@ {-# INLINE modify #-} modify p = G.modify p +-- Indexing+-- --------++-- | /O(n)/ Pair each element in a vector with its index+indexed :: Vector a -> Vector (Int,a)+{-# INLINE indexed #-}+indexed = G.indexed+ -- Mapping -- ------- @@ -1162,10 +1196,44 @@ {-# INLINE foldM' #-} foldM' = G.foldM' --- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a {-# INLINE fold1M' #-} fold1M' = G.fold1M'++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+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+foldM'_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_++-- Monadic sequencing+-- ------------------++-- | Evaluate each action and collect the results+sequence :: Monad m => Vector (m a) -> m (Vector a)+{-# INLINE sequence #-}+sequence = G.sequence++-- | Evaluate each action and discard the results+sequence_ :: Monad m => Vector (m a) -> m ()+{-# INLINE sequence_ #-}+sequence_ = G.sequence_ -- Prefix sums (scans) -- -------------------
Data/Vector/Fusion/Stream.hs view
@@ -55,7 +55,7 @@ and, or, -- * Unfolding- unfoldr, unfoldrN,+ unfoldr, unfoldrN, iterateN, -- * Scans prescanl, prescanl',@@ -417,6 +417,11 @@ unfoldrN :: Int -> (s -> Maybe (a, s)) -> s -> Stream a {-# INLINE unfoldrN #-} unfoldrN = M.unfoldrN++-- | Apply function n-1 times to value. Zeroth element is original value.+iterateN :: Int -> (a -> a) -> a -> Stream a+{-# INLINE iterateN #-}+iterateN = M.iterateN -- Scans -- -----
Data/Vector/Fusion/Stream/Monadic.hs view
@@ -56,6 +56,7 @@ -- * Unfolding unfoldr, unfoldrM, unfoldrN, unfoldrNM,+ iterateN, iterateNM, -- * Scans prescanl, prescanlM, prescanl', prescanlM',@@ -992,6 +993,22 @@ Just (x,s') -> Yield x (s',n-1) Nothing -> Done ) (f s)++-- | Apply monadic function n times to value. Zeroth element is original value.+iterateNM :: Monad m => Int -> (a -> m a) -> a -> Stream m a+{-# INLINE_STREAM iterateNM #-}+iterateNM n f x0 = Stream step (x0,n) (Exact (delay_inline max n 0))+ where+ {-# INLINE_INNER step #-}+ step (x,i) | i <= 0 = return Done+ | i == n = return $ Yield x (x,i-1)+ | otherwise = do a <- f x+ return $ Yield a (a,i-1)++-- | Apply function n times to value. Zeroth element is original value.+iterateN :: Monad m => Int -> (a -> a) -> a -> Stream m a+{-# INLINE_STREAM iterateN #-}+iterateN n f x0 = iterateNM n (return . f) x0 -- Scans -- -----
Data/Vector/Fusion/Util.hs view
@@ -13,7 +13,7 @@ module Data.Vector.Fusion.Util ( Id(..), Box(..), - delay_inline+ delay_inline, delayed_min ) where -- | Identity monad@@ -41,4 +41,8 @@ {-# INLINE [0] delay_inline #-} delay_inline f = f +-- | `min` inlined in phase 0+delayed_min :: Int -> Int -> Int+{-# INLINE [0] delayed_min #-}+delayed_min m n = min m n
Data/Vector/Generic.hs view
@@ -30,16 +30,16 @@ unsafeIndexM, unsafeHeadM, unsafeLastM, -- ** Extracting subvectors (slicing)- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- * Construction -- ** Initialisation- empty, singleton, replicate, generate,+ empty, singleton, replicate, generate, iterateN, -- ** Monadic initialisation- replicateM, create,+ replicateM, generateM, create, -- ** Unfolding unfoldr, unfoldrN,@@ -71,6 +71,9 @@ -- * Elementwise operations + -- ** Indexing+ indexed,+ -- ** Mapping map, imap, concatMap, @@ -112,7 +115,11 @@ -- ** Monadic folds foldM, foldM', fold1M, fold1M',+ foldM_, foldM'_, fold1M_, fold1M'_, + -- ** Monadic sequencing+ sequence, sequence_,+ -- * Prefix sums (scans) prescanl, prescanl', postscanl, postscanl',@@ -170,7 +177,7 @@ import Prelude hiding ( length, null, replicate, (++), concat, head, last,- init, tail, take, drop, reverse,+ init, tail, take, drop, splitAt, reverse, map, concat, concatMap, zipWith, zipWith3, zip, zip3, unzip, unzip3, filter, takeWhile, dropWhile, span, break,@@ -179,13 +186,21 @@ all, any, and, or, sum, product, maximum, minimum, scanl, scanl1, scanr, scanr1, enumFromTo, enumFromThenTo,- mapM, mapM_ )+ mapM, mapM_, sequence, sequence_ ) import Data.Typeable ( Typeable1, gcast1 )-import Data.Data ( Data, DataType, mkNorepType ) #include "vector.h" +import Data.Data ( Data, DataType )+#if MIN_VERSION_base(4,2,0)+import Data.Data ( mkNoRepType )+#else+import Data.Data ( mkNorepType )+mkNoRepType :: String -> DataType+mkNoRepType = mkNorepType+#endif+ -- Length information -- ------------------ @@ -381,7 +396,7 @@ {-# INLINE_STREAM tail #-} tail v = slice 1 (length v - 1) v --- | /O(1)/ Yield at the first @n@ elements without copying. The vector may+-- | /O(1)/ Yield the first @n@ elements without copying. The vector may -- contain less than @n@ elements in which case it is returned unchanged. take :: Vector v a => Int -> v a -> v a {-# INLINE_STREAM take #-}@@ -397,6 +412,20 @@ where n' = max n 0 len = length v +-- | /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.+{-# INLINE_STREAM splitAt #-}+splitAt :: Vector v a => Int -> v a -> (v a, v a)+splitAt n v = ( unsafeSlice 0 m v+ , unsafeSlice m (delay_inline max 0 (len - n')) v+ )+ where+ m = delay_inline min n' len+ n' = max n 0+ len = length v+ -- | /O(1)/ Yield a slice of the vector without copying. The vector must -- contain at least @i+n@ elements but this is not checked. unsafeSlice :: Vector v a => Int -- ^ @i@ starting index@@ -486,6 +515,11 @@ {-# INLINE generate #-} generate n f = unstream (Stream.generate n f) +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Vector v a => Int -> (a -> a) -> a -> v a+{-# INLINE iterateN #-}+iterateN n f x = unstream (Stream.iterateN n f x)+ -- Unfolding -- --------- @@ -595,10 +629,15 @@ -- | /O(n)/ Execute the monadic action the given number of times and store the -- results in a vector. replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a)--- FIXME: specialise for ST and IO? {-# INLINE replicateM #-}-replicateM n m = fromListN n `Monad.liftM` Monad.replicateM n m+replicateM n m = unstreamM (MStream.replicateM n m) +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: (Monad m, Vector v a) => Int -> (Int -> m a) -> m (v a)+{-# INLINE generateM #-}+generateM n f = unstreamM (MStream.generateM n f)+ -- | Execute the monadic action and freeze the resulting vector. -- -- @@@ -852,6 +891,14 @@ {-# INLINE modifyWithStream #-} modifyWithStream p v s = new (New.modifyWithStream p (clone v) s) +-- Indexing+-- --------++-- | /O(n)/ Pair each element in a vector with its index+indexed :: (Vector v a, Vector v (Int,a)) => v a -> v (Int,a)+{-# INLINE indexed #-}+indexed = unstream . Stream.indexed . stream+ -- Mapping -- ------- @@ -879,7 +926,6 @@ -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a -- vector of results mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)--- FIXME: specialise for ST and IO? {-# INLINE mapM #-} mapM f = unstreamM . Stream.mapM f . stream @@ -1437,11 +1483,49 @@ {-# INLINE foldM' #-} foldM' m z = Stream.foldM' m z . stream --- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a {-# INLINE fold1M' #-} fold1M' m = Stream.fold1M' m . stream +discard :: Monad m => m a -> m ()+{-# INLINE discard #-}+discard m = m >> return ()++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()+{-# INLINE foldM_ #-}+foldM_ m z = discard . Stream.foldM m z . stream++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()+{-# INLINE fold1M_ #-}+fold1M_ m = discard . Stream.fold1M m . stream++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ m z = discard . Stream.foldM' m z . stream++-- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ m = discard . Stream.fold1M' m . stream++-- Monadic sequencing+-- ------------------++-- | Evaluate each action and collect the results+sequence :: (Monad m, Vector v a, Vector v (m a)) => v (m a) -> m (v a)+{-# INLINE sequence #-}+sequence = mapM id++-- | Evaluate each action and discard the results+sequence_ :: (Monad m, Vector v (m a)) => v (m a) -> m ()+{-# INLINE sequence_ #-}+sequence_ = mapM_ id+ -- Prefix sums (scans) -- ------------------- @@ -1736,12 +1820,33 @@ #-} -unstreamM :: (Vector v a, Monad m) => MStream m a -> m (v a)+unstreamM :: (Monad m, Vector v a) => MStream m a -> m (v a) {-# INLINE_STREAM unstreamM #-} unstreamM s = do xs <- MStream.toList s return $ unstream $ Stream.unsafeFromList (MStream.size s) xs +unstreamPrimM :: (PrimMonad m, Vector v a) => MStream m a -> m (v a)+{-# INLINE_STREAM unstreamPrimM #-}+unstreamPrimM s = M.munstream s >>= unsafeFreeze++-- FIXME: the next two functions are only necessary for the specialisations+unstreamPrimM_IO :: Vector v a => MStream IO a -> IO (v a)+{-# INLINE unstreamPrimM_IO #-}+unstreamPrimM_IO = unstreamPrimM++unstreamPrimM_ST :: Vector v a => MStream (ST s) a -> ST s (v a)+{-# INLINE unstreamPrimM_ST #-}+unstreamPrimM_ST = unstreamPrimM++{-# RULES++"unstreamM[IO]" unstreamM = unstreamPrimM_IO+"unstreamM[ST]" unstreamM = unstreamPrimM_ST++ #-}++ -- Recycling support -- ----------------- @@ -1794,7 +1899,7 @@ mkType :: String -> DataType {-# INLINE mkType #-}-mkType = mkNorepType+mkType = mkNoRepType dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t) => (forall d. Data d => c (t d)) -> Maybe (c (v a))
Data/Vector/Generic/Mutable.hs view
@@ -21,7 +21,7 @@ length, null, -- ** Extracting subvectors- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- ** Overlapping@@ -30,7 +30,7 @@ -- * Construction -- ** Initialisation- new, unsafeNew, replicate, clone,+ new, unsafeNew, replicate, replicateM, clone, -- ** Growing grow, unsafeGrow,@@ -45,7 +45,7 @@ -- * Modifying vectors -- ** Filling and copying- set, copy, unsafeCopy,+ set, copy, move, unsafeCopy, unsafeMove, -- * Internal operations unstream, unstreamR,@@ -68,7 +68,7 @@ import Control.Monad.Primitive ( PrimMonad, PrimState ) import Prelude hiding ( length, null, replicate, reverse, map, read,- take, drop, init, tail )+ take, drop, splitAt, init, tail ) #include "vector.h" @@ -122,6 +122,12 @@ -> v (PrimState m) a -- ^ source -> m () + -- | Move the contents of a vector. The two vectors may overlap. This method+ -- should not be called directly, use 'unsafeMove' instead.+ basicUnsafeMove :: PrimMonad m => v (PrimState m) a -- ^ target+ -> v (PrimState m) a -- ^ source+ -> m ()+ -- | Grow a vector by the given number of elements. This method should not be -- called directly, use 'unsafeGrow' instead. basicUnsafeGrow :: PrimMonad m => v (PrimState m) a -> Int@@ -163,6 +169,13 @@ basicUnsafeWrite dst i x do_copy (i+1) | otherwise = return ()+ + {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove !dst !src+ | basicOverlaps dst src = do+ srcCopy <- clone src+ basicUnsafeCopy dst srcCopy+ | otherwise = basicUnsafeCopy dst src {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow v by@@ -411,6 +424,16 @@ n' = max n 0 m = length v +{-# INLINE splitAt #-}+splitAt :: MVector v a => Int -> v s a -> (v s a, v s a)+splitAt n v = ( unsafeSlice 0 m v+ , unsafeSlice m (max 0 (len - n')) v+ )+ where+ m = min n' len+ n' = max n 0+ len = length v+ init :: MVector v a => v s a -> v s a {-# INLINE init #-} init v = slice 0 (length v - 1) v@@ -474,6 +497,12 @@ {-# INLINE replicate #-} replicate n x = basicUnsafeReplicate (delay_inline max 0 n) x +-- | 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.+replicateM :: (PrimMonad m, MVector v a) => Int -> m a -> m (v (PrimState m) a)+{-# INLINE replicateM #-}+replicateM n m = munstream (MStream.replicateM n m)+ -- | Create a copy of a mutable vector. clone :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m (v (PrimState m) a) {-# INLINE clone #-}@@ -626,6 +655,20 @@ (length dst == length src) $ unsafeCopy dst src +-- | 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.+move :: (PrimMonad m, MVector v a)+ => v (PrimState m) a -> v (PrimState m) a -> m ()+{-# INLINE move #-}+move dst src = BOUNDS_CHECK(check) "move" "length mismatch"+ (length dst == length src)+ $ unsafeMove dst src+ -- | Copy a vector. The two vectors must have the same length and may not -- overlap. This is not checked. unsafeCopy :: (PrimMonad m, MVector v a) => v (PrimState m) a -- ^ target@@ -638,6 +681,20 @@ (not (dst `overlaps` src)) $ (dst `seq` src `seq` basicUnsafeCopy dst src) +-- | 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.+unsafeMove :: (PrimMonad m, MVector v a) => v (PrimState m) a -- ^ target+ -> v (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove dst src = UNSAFE_CHECK(check) "unsafeMove" "length mismatch"+ (length dst == length src)+ $ (dst `seq` src `seq` basicUnsafeMove dst src) -- Permutations -- ------------
Data/Vector/Mutable.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, BangPatterns #-} -- | -- Module : Data.Vector.Mutable@@ -22,7 +22,7 @@ length, null, -- ** Extracting subvectors- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- ** Overlapping@@ -31,7 +31,7 @@ -- * Construction -- ** Initialisation- new, unsafeNew, replicate, clone,+ new, unsafeNew, replicate, replicateM, clone, -- ** Growing grow, unsafeGrow,@@ -46,18 +46,19 @@ -- * Modifying vectors -- ** Filling and copying- set, copy, unsafeCopy,+ set, copy, move, unsafeCopy, unsafeMove, -- * Deprecated operations newWith, unsafeNewWith ) where +import Control.Monad (when) import qualified Data.Vector.Generic.Mutable as G import Data.Primitive.Array import Control.Monad.Primitive import Prelude hiding ( length, null, replicate, reverse, map, read,- take, drop, init, tail )+ take, drop, splitAt, init, tail ) import Data.Typeable ( Typeable ) @@ -103,10 +104,70 @@ {-# INLINE basicUnsafeWrite #-} basicUnsafeWrite (MVector i n arr) j x = writeArray arr (i+j) x+ + basicUnsafeMove dst@(MVector iDst n arrDst) src@(MVector iSrc _ arrSrc)+ = case n of+ 0 -> return ()+ 1 -> readArray arrSrc iSrc >>= writeArray arrDst iDst+ 2 -> do+ x <- readArray arrSrc iSrc+ y <- readArray arrSrc (iSrc + 1)+ writeArray arrDst iDst x+ writeArray arrDst (iDst + 1) y+ _+ | overlaps dst src+ -> case compare iDst iSrc of+ LT -> moveBackwards arrDst iDst iSrc n+ EQ -> return ()+ GT | (iDst - iSrc) * 2 < n+ -> moveForwardsLargeOverlap arrDst iDst iSrc n+ | otherwise+ -> moveForwardsSmallOverlap arrDst iDst iSrc n+ | otherwise -> G.basicUnsafeCopy dst src {-# INLINE basicClear #-} basicClear v = G.set v uninitialised +{-# INLINE moveBackwards #-}+moveBackwards :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()+moveBackwards !arr !dstOff !srcOff !len =+ INTERNAL_CHECK(check) "moveBackwards" "not a backwards move" (dstOff < srcOff)+ $ loopM len $ \ i -> readArray arr (srcOff + i) >>= writeArray arr (dstOff + i)++{-# INLINE moveForwardsSmallOverlap #-}+-- Performs a move when dstOff > srcOff, optimized for when the overlap of the intervals is small.+moveForwardsSmallOverlap :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()+moveForwardsSmallOverlap !arr !dstOff !srcOff !len =+ INTERNAL_CHECK(check) "moveForwardsSmallOverlap" "not a forward move" (dstOff > srcOff)+ $ do+ tmp <- newArray overlap uninitialised+ loopM overlap $ \ i -> readArray arr (dstOff + i) >>= writeArray tmp i+ loopM nonOverlap $ \ i -> readArray arr (srcOff + i) >>= writeArray arr (dstOff + i)+ loopM overlap $ \ i -> readArray tmp i >>= writeArray arr (dstOff + nonOverlap + i)+ where nonOverlap = dstOff - srcOff; overlap = len - nonOverlap++-- Performs a move when dstOff > srcOff, optimized for when the overlap of the intervals is large.+moveForwardsLargeOverlap :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()+moveForwardsLargeOverlap !arr !dstOff !srcOff !len =+ INTERNAL_CHECK(check) "moveForwardsLargeOverlap" "not a forward move" (dstOff > srcOff)+ $ do+ queue <- newArray nonOverlap uninitialised+ loopM nonOverlap $ \ i -> readArray arr (srcOff + i) >>= writeArray queue i+ let mov !i !qTop = when (i < dstOff + len) $ do+ x <- readArray arr i+ y <- readArray queue qTop+ writeArray arr i y+ writeArray queue qTop x+ mov (i+1) (if qTop + 1 >= nonOverlap then 0 else qTop + 1)+ mov dstOff 0+ where nonOverlap = dstOff - srcOff++{-# INLINE loopM #-}+loopM :: Monad m => Int -> (Int -> m a) -> m ()+loopM !n k = let+ go i = when (i < n) (k i >> go (i+1))+ in go 0+ uninitialised :: a uninitialised = error "Data.Vector.Mutable: uninitialised element" @@ -139,6 +200,10 @@ {-# INLINE drop #-} drop = G.drop +{-# INLINE splitAt #-}+splitAt :: Int -> MVector s a -> (MVector s a, MVector s a)+splitAt = G.splitAt+ init :: MVector s a -> MVector s a {-# INLINE init #-} init = G.init@@ -199,6 +264,12 @@ {-# 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.+replicateM :: PrimMonad m => Int -> m a -> m (MVector (PrimState m) a)+{-# INLINE replicateM #-}+replicateM = G.replicateM+ -- | Create a copy of a mutable vector. clone :: PrimMonad m => MVector (PrimState m) a -> m (MVector (PrimState m) a) {-# INLINE clone #-}@@ -286,6 +357,31 @@ -> 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.+move :: PrimMonad m+ => MVector (PrimState m) a -> MVector (PrimState m) a -> 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.+unsafeMove :: PrimMonad m => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove = G.unsafeMove -- Deprecated functions -- --------------------
Data/Vector/Primitive.hs view
@@ -33,16 +33,16 @@ unsafeIndexM, unsafeHeadM, unsafeLastM, -- ** Extracting subvectors (slicing)- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- * Construction -- ** Initialisation- empty, singleton, replicate, generate,+ empty, singleton, replicate, generate, iterateN, -- ** Monadic initialisation- replicateM, create,+ replicateM, generateM, create, -- ** Unfolding unfoldr, unfoldrN,@@ -111,6 +111,7 @@ -- ** Monadic folds foldM, foldM', fold1M, fold1M',+ foldM_, foldM'_, fold1M_, fold1M'_, -- * Prefix sums (scans) prescanl, prescanl',@@ -145,7 +146,7 @@ import Prelude hiding ( length, null, replicate, (++), concat, head, last,- init, tail, take, drop, reverse,+ init, tail, take, drop, splitAt, reverse, map, concatMap, zipWith, zipWith3, zip, zip3, unzip, unzip3, filter, takeWhile, dropWhile, span, break,@@ -388,6 +389,14 @@ {-# 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.+{-# INLINE splitAt #-}+splitAt :: Prim a => Int -> Vector a -> (Vector a, Vector a)+splitAt = G.splitAt+ -- | /O(1)/ Yield a slice of the vector without copying. The vector must -- contain at least @i+n@ elements but this is not checked. unsafeSlice :: Prim a => Int -- ^ @i@ starting index@@ -445,6 +454,11 @@ {-# INLINE generate #-} generate = G.generate +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Prim a => Int -> (a -> a) -> a -> Vector a+{-# INLINE iterateN #-}+iterateN = G.iterateN+ -- Unfolding -- --------- @@ -535,6 +549,12 @@ {-# INLINE replicateM #-} replicateM = G.replicateM +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: (Monad m, Prim a) => Int -> (Int -> m a) -> m (Vector a)+{-# INLINE generateM #-}+generateM = G.generateM+ -- | Execute the monadic action and freeze the resulting vector. -- -- @@@ -1075,10 +1095,31 @@ {-# INLINE foldM' #-} foldM' = G.foldM' --- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator fold1M' :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m a {-# INLINE fold1M' #-} fold1M' = G.fold1M'++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M_ #-}+fold1M_ = G.fold1M_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_ -- Prefix sums (scans) -- -------------------
Data/Vector/Primitive/Mutable.hs view
@@ -22,7 +22,7 @@ length, null, -- ** Extracting subvectors- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- ** Overlapping@@ -31,7 +31,7 @@ -- * Construction -- ** Initialisation- new, unsafeNew, replicate, clone,+ new, unsafeNew, replicate, replicateM, clone, -- ** Growing grow, unsafeGrow,@@ -46,7 +46,7 @@ -- * Modifying vectors -- ** Filling and copying- set, copy, unsafeCopy,+ set, copy, move, unsafeCopy, unsafeMove, -- * Deprecated operations newWith, unsafeNewWith@@ -59,7 +59,7 @@ import Control.Monad ( liftM ) import Prelude hiding ( length, null, replicate, reverse, map, read,- take, drop, init, tail )+ take, drop, splitAt, init, tail ) import Data.Typeable ( Typeable ) @@ -101,6 +101,12 @@ = memcpyByteArray dst (i * sz) src (j * sz) (n * sz) where sz = sizeOf (undefined :: a)+ + {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MVector i n dst) (MVector j _ src)+ = memmoveByteArray dst (i * sz) src (j * sz) (n * sz)+ where+ sz = sizeOf (undefined :: a) -- Length information -- ------------------@@ -131,6 +137,10 @@ {-# INLINE drop #-} drop = G.drop +splitAt :: Prim a => Int -> MVector s a -> (MVector s a, MVector s a)+{-# INLINE splitAt #-}+splitAt = G.splitAt+ init :: Prim a => MVector s a -> MVector s a {-# INLINE init #-} init = G.init@@ -192,6 +202,12 @@ {-# 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.+replicateM :: (PrimMonad m, Prim a) => Int -> m a -> m (MVector (PrimState m) a)+{-# INLINE replicateM #-}+replicateM = G.replicateM+ -- | Create a copy of a mutable vector. clone :: (PrimMonad m, Prim a) => MVector (PrimState m) a -> m (MVector (PrimState m) a)@@ -283,6 +299,32 @@ -> 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.+move :: (PrimMonad m, Prim a)+ => MVector (PrimState m) a -> MVector (PrimState m) a -> 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.+unsafeMove :: (PrimMonad m, Prim a)+ => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove = G.unsafeMove -- Deprecated functions -- --------------------
Data/Vector/Storable.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, TypeFamilies, Rank2Types #-}+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, TypeFamilies, Rank2Types, ScopedTypeVariables #-} -- | -- Module : Data.Vector.Storable@@ -30,16 +30,16 @@ unsafeIndexM, unsafeHeadM, unsafeLastM, -- ** Extracting subvectors (slicing)- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- * Construction -- ** Initialisation- empty, singleton, replicate, generate,+ empty, singleton, replicate, generate, iterateN, -- ** Monadic initialisation- replicateM, create,+ replicateM, generateM, create, -- ** Unfolding unfoldr, unfoldrN,@@ -108,6 +108,7 @@ -- ** Monadic folds foldM, foldM', fold1M, fold1M',+ foldM_, foldM'_, fold1M_, fold1M'_, -- * Prefix sums (scans) prescanl, prescanl',@@ -123,7 +124,7 @@ toList, fromList, fromListN, -- ** Other vector types- G.convert,+ G.convert, unsafeCast, -- ** Mutable vectors freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,@@ -148,7 +149,7 @@ import Prelude hiding ( length, null, replicate, (++), concat, head, last,- init, tail, take, drop, reverse,+ init, tail, take, drop, splitAt, reverse, map, concatMap, zipWith, zipWith3, zip, zip3, unzip, unzip3, filter, takeWhile, dropWhile, span, break,@@ -397,6 +398,14 @@ {-# 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.+{-# INLINE splitAt #-}+splitAt :: Storable a => Int -> Vector a -> (Vector a, Vector a)+splitAt = G.splitAt+ -- | /O(1)/ Yield a slice of the vector without copying. The vector must -- contain at least @i+n@ elements but this is not checked. unsafeSlice :: Storable a => Int -- ^ @i@ starting index@@ -454,6 +463,11 @@ {-# INLINE generate #-} generate = G.generate +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Storable a => Int -> (a -> a) -> a -> Vector a+{-# INLINE iterateN #-}+iterateN = G.iterateN+ -- Unfolding -- --------- @@ -544,6 +558,12 @@ {-# INLINE replicateM #-} replicateM = G.replicateM +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: (Monad m, Storable a) => Int -> (Int -> m a) -> m (Vector a)+{-# INLINE generateM #-}+generateM = G.generateM+ -- | Execute the monadic action and freeze the resulting vector. -- -- @@@ -1094,11 +1114,32 @@ {-# INLINE foldM' #-} foldM' = G.foldM' --- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator fold1M' :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a {-# INLINE fold1M' #-} fold1M' = G.fold1M' +-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M_ #-}+fold1M_ = G.fold1M_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_+ -- Prefix sums (scans) -- ------------------- @@ -1235,6 +1276,24 @@ fromListN :: Storable a => Int -> [a] -> Vector a {-# INLINE fromListN #-} fromListN = G.fromListN++-- Conversions - Unsafe casts+-- --------------------------++-- | /O(1)/ Unsafely cast a vector from one element type to another.+-- The operation just changes the type of the underlying pointer and does not+-- modify the elements.+--+-- The resulting vector contains as many elements as can fit into the+-- underlying memory block.+--+unsafeCast :: forall a b. (Storable a, Storable b) => Vector a -> Vector b+{-# INLINE unsafeCast #-}+unsafeCast (Vector p n fp)+ = Vector (castPtr p)+ ((n * sizeOf (undefined :: a)) `div` sizeOf (undefined :: b))+ (castForeignPtr fp)+ -- Conversions - Mutable vectors -- -----------------------------
Data/Vector/Storable/Mutable.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, ScopedTypeVariables #-} -- | -- Module : Data.Vector.Storable.Mutable@@ -22,7 +22,7 @@ length, null, -- ** Extracting subvectors- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- ** Overlapping@@ -31,7 +31,7 @@ -- * Construction -- ** Initialisation- new, unsafeNew, replicate, clone,+ new, unsafeNew, replicate, replicateM, clone, -- ** Growing grow, unsafeGrow,@@ -46,8 +46,11 @@ -- * Modifying vectors -- ** Filling and copying- set, copy, unsafeCopy,+ set, copy, move, unsafeCopy, unsafeMove, + -- * Unsafe conversions+ unsafeCast,+ -- * Raw pointers unsafeFromForeignPtr, unsafeToForeignPtr, unsafeWith, @@ -60,14 +63,19 @@ import Foreign.Storable import Foreign.ForeignPtr++#if __GLASGOW_HASKELL__ >= 605+import GHC.ForeignPtr (mallocPlainForeignPtrBytes)+#endif+ import Foreign.Ptr-import Foreign.Marshal.Array ( advancePtr, copyArray )+import Foreign.Marshal.Array ( advancePtr, copyArray, moveArray ) import Foreign.C.Types ( CInt ) import Control.Monad.Primitive import Prelude hiding ( length, null, replicate, reverse, map, read,- take, drop, init, tail )+ take, drop, splitAt, init, tail ) import Data.Typeable ( Typeable ) @@ -100,7 +108,7 @@ basicUnsafeNew n = unsafePrimToPrim $ do- fp <- mallocForeignPtrArray n+ fp <- mallocVector n withForeignPtr fp $ \p -> return $ MVector p n fp {-# INLINE basicUnsafeRead #-}@@ -119,7 +127,26 @@ $ withForeignPtr fp $ \_ -> withForeignPtr fq $ \_ -> copyArray p q n+ + {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MVector p n fp) (MVector q _ fq)+ = unsafePrimToPrim+ $ withForeignPtr fp $ \_ ->+ withForeignPtr fq $ \_ ->+ moveArray p q n +{-# INLINE mallocVector #-}+mallocVector :: Storable a => Int -> IO (ForeignPtr a)+mallocVector =+#if __GLASGOW_HASKELL__ >= 605+ doMalloc undefined+ where+ doMalloc :: Storable b => b -> Int -> IO (ForeignPtr b)+ doMalloc dummy size = mallocPlainForeignPtrBytes (size * sizeOf dummy)+#else+ mallocForeignPtrArray+#endif+ -- Length information -- ------------------ @@ -149,6 +176,10 @@ {-# INLINE drop #-} drop = G.drop +splitAt :: Storable a => Int -> MVector s a -> (MVector s a, MVector s a)+{-# INLINE splitAt #-}+splitAt = G.splitAt+ init :: Storable a => MVector s a -> MVector s a {-# INLINE init #-} init = G.init@@ -210,6 +241,12 @@ {-# 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.+replicateM :: (PrimMonad m, Storable a) => Int -> m a -> m (MVector (PrimState m) a)+{-# INLINE replicateM #-}+replicateM = G.replicateM+ -- | Create a copy of a mutable vector. clone :: (PrimMonad m, Storable a) => MVector (PrimState m) a -> m (MVector (PrimState m) a)@@ -303,6 +340,50 @@ -> 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.+move :: (PrimMonad m, Storable a)+ => MVector (PrimState m) a -> MVector (PrimState m) a -> 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.+unsafeMove :: (PrimMonad m, Storable a)+ => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove = G.unsafeMove++-- Unsafe conversions+-- ------------------++-- | /O(1)/ Unsafely cast a mutable vector from one element type to another.+-- The operation just changes the type of the underlying pointer and does not+-- modify the elements.+--+-- The resulting vector contains as many elements as can fit into the+-- underlying memory block.+--+unsafeCast :: forall a b s.+ (Storable a, Storable b) => MVector s a -> MVector s b+{-# INLINE unsafeCast #-}+unsafeCast (MVector p n fp)+ = MVector (castPtr p)+ ((n * sizeOf (undefined :: a)) `div` sizeOf (undefined :: b))+ (castForeignPtr fp) -- Raw pointers -- ------------
Data/Vector/Unboxed.hs view
@@ -53,16 +53,16 @@ unsafeIndexM, unsafeHeadM, unsafeLastM, -- ** Extracting subvectors (slicing)- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- * Construction -- ** Initialisation- empty, singleton, replicate, generate,+ empty, singleton, replicate, generate, iterateN, -- ** Monadic initialisation- replicateM, create,+ replicateM, generateM, create, -- ** Unfolding unfoldr, unfoldrN,@@ -94,6 +94,9 @@ -- * Elementwise operations + -- ** Indexing+ indexed,+ -- ** Mapping map, imap, concatMap, @@ -135,6 +138,7 @@ -- ** Monadic folds foldM, foldM', fold1M, fold1M',+ foldM_, foldM'_, fold1M_, fold1M'_, -- * Prefix sums (scans) prescanl, prescanl',@@ -159,6 +163,7 @@ import Data.Vector.Unboxed.Base import qualified Data.Vector.Generic as G import qualified Data.Vector.Fusion.Stream as Stream+import Data.Vector.Fusion.Util ( delayed_min ) import Control.Monad.ST ( ST ) import Control.Monad.Primitive@@ -166,7 +171,7 @@ import Prelude hiding ( length, null, replicate, (++), concat, head, last,- init, tail, take, drop, reverse,+ init, tail, take, drop, splitAt, reverse, map, concatMap, zipWith, zipWith3, zip, zip3, unzip, unzip3, filter, takeWhile, dropWhile, span, break,@@ -363,6 +368,14 @@ {-# 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.+{-# INLINE splitAt #-}+splitAt :: Unbox a => Int -> Vector a -> (Vector a, Vector a)+splitAt = G.splitAt+ -- | /O(1)/ Yield a slice of the vector without copying. The vector must -- contain at least @i+n@ elements but this is not checked. unsafeSlice :: Unbox a => Int -- ^ @i@ starting index@@ -420,6 +433,11 @@ {-# INLINE generate #-} generate = G.generate +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Unbox a => Int -> (a -> a) -> a -> Vector a+{-# INLINE iterateN #-}+iterateN = G.iterateN+ -- Unfolding -- --------- @@ -510,6 +528,12 @@ {-# INLINE replicateM #-} replicateM = G.replicateM +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: (Monad m, Unbox a) => Int -> (Int -> m a) -> m (Vector a)+{-# INLINE generateM #-}+generateM = G.generateM+ -- | Execute the monadic action and freeze the resulting vector. -- -- @@@ -700,6 +724,14 @@ {-# INLINE modify #-} modify p = G.modify p +-- Indexing+-- --------++-- | /O(n)/ Pair each element in a vector with its index+indexed :: Unbox a => Vector a -> Vector (Int,a)+{-# INLINE indexed #-}+indexed = G.indexed+ -- Mapping -- ------- @@ -1103,10 +1135,31 @@ {-# INLINE foldM' #-} foldM' = G.foldM' --- | /O(n)/ Monad fold over non-empty vectors with strict accumulator+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator fold1M' :: (Monad m, Unbox a) => (a -> a -> m a) -> Vector a -> m a {-# INLINE fold1M' #-} fold1M' = G.fold1M'++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (Monad m, Unbox b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (Monad m, Unbox a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M_ #-}+fold1M_ = G.fold1M_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (Monad m, Unbox b) => (a -> b -> m a) -> a -> Vector b -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (Monad m, Unbox a) => (a -> a -> m a) -> Vector a -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_ -- Prefix sums (scans) -- -------------------
Data/Vector/Unboxed/Base.hs view
@@ -155,6 +155,7 @@ ; basicClear (con v) = M.basicClear v \ ; basicSet (con v) x = M.basicSet v x \ ; basicUnsafeCopy (con v1) (con v2) = M.basicUnsafeCopy v1 v2 \+; basicUnsafeMove (con v1) (con v2) = M.basicUnsafeMove v1 v2 \ ; basicUnsafeGrow (con v) n = con `liftM` M.basicUnsafeGrow v n } #define primVector(ty,con,mcon) \@@ -295,6 +296,7 @@ basicClear (MV_Bool v) = M.basicClear v basicSet (MV_Bool v) x = M.basicSet v (fromBool x) basicUnsafeCopy (MV_Bool v1) (MV_Bool v2) = M.basicUnsafeCopy v1 v2+ basicUnsafeMove (MV_Bool v1) (MV_Bool v2) = M.basicUnsafeMove v1 v2 basicUnsafeGrow (MV_Bool v) n = MV_Bool `liftM` M.basicUnsafeGrow v n instance G.Vector Vector Bool where@@ -343,6 +345,7 @@ basicClear (MV_Complex v) = M.basicClear v basicSet (MV_Complex v) (x :+ y) = M.basicSet v (x,y) basicUnsafeCopy (MV_Complex v1) (MV_Complex v2) = M.basicUnsafeCopy v1 v2+ basicUnsafeMove (MV_Complex v1) (MV_Complex v2) = M.basicUnsafeMove v1 v2 basicUnsafeGrow (MV_Complex v) n = MV_Complex `liftM` M.basicUnsafeGrow v n instance (RealFloat a, Unbox a) => G.Vector Vector (Complex a) where
Data/Vector/Unboxed/Mutable.hs view
@@ -20,7 +20,7 @@ length, null, -- ** Extracting subvectors- slice, init, tail, take, drop,+ slice, init, tail, take, drop, splitAt, unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, -- ** Overlapping@@ -29,7 +29,7 @@ -- * Construction -- ** Initialisation- new, unsafeNew, replicate, clone,+ new, unsafeNew, replicate, replicateM, clone, -- ** Growing grow, unsafeGrow,@@ -48,7 +48,7 @@ -- * Modifying vectors -- ** Filling and copying- set, copy, unsafeCopy,+ set, copy, move, unsafeCopy, unsafeMove, -- * Deprecated operations newWith, unsafeNewWith@@ -57,10 +57,11 @@ import Data.Vector.Unboxed.Base import qualified Data.Vector.Generic.Mutable as G+import Data.Vector.Fusion.Util ( delayed_min ) import Control.Monad.Primitive import Prelude hiding ( length, null, replicate, reverse, map, read,- take, drop, init, tail,+ take, drop, splitAt, init, tail, zip, zip3, unzip, unzip3 ) #include "vector.h"@@ -94,6 +95,10 @@ {-# INLINE drop #-} drop = G.drop +splitAt :: Unbox a => Int -> MVector s a -> (MVector s a, MVector s a)+{-# INLINE splitAt #-}+splitAt = G.splitAt+ init :: Unbox a => MVector s a -> MVector s a {-# INLINE init #-} init = G.init@@ -155,6 +160,12 @@ {-# 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.+replicateM :: (PrimMonad m, Unbox a) => Int -> m a -> m (MVector (PrimState m) a)+{-# INLINE replicateM #-}+replicateM = G.replicateM+ -- | Create a copy of a mutable vector. clone :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> m (MVector (PrimState m) a)@@ -246,6 +257,32 @@ -> 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.+move :: (PrimMonad m, Unbox a)+ => MVector (PrimState m) a -> MVector (PrimState m) a -> 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.+unsafeMove :: (PrimMonad m, Unbox a)+ => MVector (PrimState m) a -- ^ target+ -> MVector (PrimState m) a -- ^ source+ -> m ()+{-# INLINE unsafeMove #-}+unsafeMove = G.unsafeMove -- Deprecated functions -- --------------------
benchmarks/vector-benchmarks.cabal view
@@ -1,10 +1,10 @@ Name: vector-benchmarks-Version: 0.7.0.1+Version: 0.7.1 License: BSD3 License-File: LICENSE Author: Roman Leshchinskiy <rl@cse.unsw.edu.au> Maintainer: Roman Leshchinskiy <rl@cse.unsw.edu.au>-Copyright: (c) Roman Leshchinskiy 2010+Copyright: (c) Roman Leshchinskiy 2010-2011 Cabal-Version: >= 1.2 Build-Type: Simple @@ -14,7 +14,7 @@ Build-Depends: base >= 2 && < 5, array, criterion >= 0.5 && < 0.6, mwc-random >= 0.5 && < 0.9,- vector == 0.7.0.1+ vector == 0.7.1 if impl(ghc<6.13) Ghc-Options: -finline-if-enough-args -fno-method-sharing
internal/GenUnboxTuple.hs view
@@ -71,7 +71,7 @@ ,nest 2 $ hang (text "where") 2 $ text "len ="- <+> sep (punctuate (text " `min`")+ <+> sep (punctuate (text " `delayed_min`") [text "length" <+> vs | vs <- varss]) ] where@@ -164,6 +164,11 @@ mk_do [q rec <+> vs <> char '1' <+> vs <> char '2' | vs <- varss] empty) + gen_unsafeMove rec+ = (patn "MV" 1 <+> patn "MV" 2,+ mk_do [qM rec <+> vs <> char '1' <+> vs <> char '2' | vs <- varss]+ empty)+ gen_unsafeGrow rec = (pat "MV" <+> var 'm', mk_do [vs <> char '\'' <+> text "<-"@@ -218,6 +223,7 @@ ,("basicClear", gen_clear) ,("basicSet", gen_set) ,("basicUnsafeCopy", gen_unsafeCopy "MV" qM)+ ,("basicUnsafeMove", gen_unsafeMove) ,("basicUnsafeGrow", gen_unsafeGrow)] methods_Vector = [("basicUnsafeFreeze", gen_unsafeFreeze)
internal/unbox-tuple-instances view
@@ -55,6 +55,11 @@ = do M.basicUnsafeCopy as1 as2 M.basicUnsafeCopy bs1 bs2+ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MV_2 n_1 as1 bs1) (MV_2 n_2 as2 bs2)+ = do+ M.basicUnsafeMove as1 as2+ M.basicUnsafeMove bs1 bs2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_2 n_ as bs) m_ = do@@ -102,7 +107,7 @@ MVector s b -> MVector s (a, b) {-# INLINE_STREAM zip #-} zip as bs = MV_2 len (unsafeSlice 0 len as) (unsafeSlice 0 len bs)- where len = length as `min` length bs+ where len = length as `delayed_min` length bs -- | /O(1)/ Unzip 2 vectors unzip :: (Unbox a, Unbox b) => MVector s (a, b) -> (MVector s a, MVector s b)@@ -114,7 +119,7 @@ zip :: (Unbox a, Unbox b) => Vector a -> Vector b -> Vector (a, b) {-# INLINE_STREAM zip #-} zip as bs = V_2 len (unsafeSlice 0 len as) (unsafeSlice 0 len bs)- where len = length as `min` length bs+ where len = length as `delayed_min` length bs {-# RULES "stream/zip [Vector.Unboxed]" forall as bs . G.stream (zip as bs) = Stream.zipWith (,) (G.stream as) (G.stream bs)@@ -195,6 +200,12 @@ M.basicUnsafeCopy as1 as2 M.basicUnsafeCopy bs1 bs2 M.basicUnsafeCopy cs1 cs2+ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MV_3 n_1 as1 bs1 cs1) (MV_3 n_2 as2 bs2 cs2)+ = do+ M.basicUnsafeMove as1 as2+ M.basicUnsafeMove bs1 bs2+ M.basicUnsafeMove cs1 cs2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_3 n_ as bs cs) m_ = do@@ -254,7 +265,8 @@ zip3 as bs cs = MV_3 len (unsafeSlice 0 len as) (unsafeSlice 0 len bs) (unsafeSlice 0 len cs)- where len = length as `min` length bs `min` length cs+ where+ len = length as `delayed_min` length bs `delayed_min` length cs -- | /O(1)/ Unzip 3 vectors unzip3 :: (Unbox a, Unbox b,@@ -273,7 +285,8 @@ zip3 as bs cs = V_3 len (unsafeSlice 0 len as) (unsafeSlice 0 len bs) (unsafeSlice 0 len cs)- where len = length as `min` length bs `min` length cs+ where+ len = length as `delayed_min` length bs `delayed_min` length cs {-# RULES "stream/zip3 [Vector.Unboxed]" forall as bs cs . G.stream (zip3 as bs cs) = Stream.zipWith3 (, ,) (G.stream as) (G.stream bs)@@ -371,6 +384,16 @@ M.basicUnsafeCopy bs1 bs2 M.basicUnsafeCopy cs1 cs2 M.basicUnsafeCopy ds1 ds2+ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MV_4 n_1 as1 bs1 cs1 ds1) (MV_4 n_2 as2+ bs2+ cs2+ ds2)+ = do+ M.basicUnsafeMove as1 as2+ M.basicUnsafeMove bs1 bs2+ M.basicUnsafeMove cs1 cs2+ M.basicUnsafeMove ds1 ds2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_4 n_ as bs cs ds) m_ = do@@ -444,7 +467,10 @@ (unsafeSlice 0 len cs) (unsafeSlice 0 len ds) where- len = length as `min` length bs `min` length cs `min` length ds+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds -- | /O(1)/ Unzip 4 vectors unzip4 :: (Unbox a, Unbox b,@@ -468,7 +494,10 @@ (unsafeSlice 0 len cs) (unsafeSlice 0 len ds) where- len = length as `min` length bs `min` length cs `min` length ds+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds {-# RULES "stream/zip4 [Vector.Unboxed]" forall as bs cs ds . G.stream (zip4 as bs cs ds) = Stream.zipWith4 (, , ,) (G.stream as) (G.stream bs)@@ -592,6 +621,18 @@ M.basicUnsafeCopy cs1 cs2 M.basicUnsafeCopy ds1 ds2 M.basicUnsafeCopy es1 es2+ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MV_5 n_1 as1 bs1 cs1 ds1 es1) (MV_5 n_2 as2+ bs2+ cs2+ ds2+ es2)+ = do+ M.basicUnsafeMove as1 as2+ M.basicUnsafeMove bs1 bs2+ M.basicUnsafeMove cs1 cs2+ M.basicUnsafeMove ds1 ds2+ M.basicUnsafeMove es1 es2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_5 n_ as bs cs ds es) m_ = do@@ -680,10 +721,10 @@ (unsafeSlice 0 len ds) (unsafeSlice 0 len es) where- len = length as `min`- length bs `min`- length cs `min`- length ds `min`+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds `delayed_min` length es -- | /O(1)/ Unzip 5 vectors unzip5 :: (Unbox a,@@ -716,10 +757,10 @@ (unsafeSlice 0 len ds) (unsafeSlice 0 len es) where- len = length as `min`- length bs `min`- length cs `min`- length ds `min`+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds `delayed_min` length es {-# RULES "stream/zip5 [Vector.Unboxed]" forall as bs cs ds es . G.stream (zip5 as@@ -866,6 +907,20 @@ M.basicUnsafeCopy ds1 ds2 M.basicUnsafeCopy es1 es2 M.basicUnsafeCopy fs1 fs2+ {-# INLINE basicUnsafeMove #-}+ basicUnsafeMove (MV_6 n_1 as1 bs1 cs1 ds1 es1 fs1) (MV_6 n_2 as2+ bs2+ cs2+ ds2+ es2+ fs2)+ = do+ M.basicUnsafeMove as1 as2+ M.basicUnsafeMove bs1 bs2+ M.basicUnsafeMove cs1 cs2+ M.basicUnsafeMove ds1 ds2+ M.basicUnsafeMove es1 es2+ M.basicUnsafeMove fs1 fs2 {-# INLINE basicUnsafeGrow #-} basicUnsafeGrow (MV_6 n_ as bs cs ds es fs) m_ = do@@ -966,11 +1021,11 @@ (unsafeSlice 0 len es) (unsafeSlice 0 len fs) where- len = length as `min`- length bs `min`- length cs `min`- length ds `min`- length es `min`+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds `delayed_min`+ length es `delayed_min` length fs -- | /O(1)/ Unzip 6 vectors unzip6 :: (Unbox a,@@ -1008,11 +1063,11 @@ (unsafeSlice 0 len es) (unsafeSlice 0 len fs) where- len = length as `min`- length bs `min`- length cs `min`- length ds `min`- length es `min`+ len = length as `delayed_min`+ length bs `delayed_min`+ length cs `delayed_min`+ length ds `delayed_min`+ length es `delayed_min` length fs {-# RULES "stream/zip6 [Vector.Unboxed]" forall as bs cs ds es fs . G.stream (zip6 as
tests/Main.hs view
@@ -2,9 +2,11 @@ import qualified Tests.Vector import qualified Tests.Stream+import qualified Tests.Move import Test.Framework (defaultMain) main = defaultMain $ Tests.Stream.tests ++ Tests.Vector.tests+ ++ Tests.Move.tests
tests/vector-tests.cabal view
@@ -27,7 +27,7 @@ TypeFamilies, TemplateHaskell - Build-Depends: base >= 4 && < 5, template-haskell, vector == 0.6.0.1,+ Build-Depends: base >= 4 && < 5, template-haskell, vector, random, QuickCheck >= 2, test-framework, test-framework-quickcheck2
vector.cabal view
@@ -1,10 +1,10 @@ Name: vector-Version: 0.7.0.1+Version: 0.7.1 License: BSD3 License-File: LICENSE Author: Roman Leshchinskiy <rl@cse.unsw.edu.au> Maintainer: Roman Leshchinskiy <rl@cse.unsw.edu.au>-Copyright: (c) Roman Leshchinskiy 2008-2010+Copyright: (c) Roman Leshchinskiy 2008-2011 Homepage: http://code.haskell.org/vector Bug-Reports: http://trac.haskell.org/vector Category: Data, Data Structures@@ -37,6 +37,22 @@ requests. . * <http://trac.haskell.org/vector>+ .+ Changes in version 0.7.1+ .+ * New functions: @iterateN@, @splitAt@+ .+ * New monadic operations: @generateM@, @sequence@, @foldM_@ and+ variants+ .+ * New functions for copying potentially overlapping arrays: @move@,+ @unsafeMove@+ .+ * Specialisations of various monadic operations for primitive monads+ .+ * Unsafe casts for Storable vectors+ .+ * Efficiency improvements . Changes in version 0.7.0.1 .