1{-# LANGUAGE CPP, DeriveDataTypeable, FlexibleInstances, MultiParamTypeClasses, TypeFamilies, ScopedTypeVariables, Rank2Types #-} 2 3 4-- | 5-- Module : Data.Vector.Primitive 6-- Copyright : (c) Roman Leshchinskiy 2008-2010 7-- License : BSD-style 8-- 9-- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au> 10-- Stability : experimental 11-- Portability : non-portable 12-- 13-- Unboxed vectors of primitive types. The use of this module is not 14-- recommended except in very special cases. Adaptive unboxed vectors defined 15-- in "Data.Vector.Unboxed" are significantly more flexible at no performance 16-- cost. 17-- 18 19module Data.Vector.Primitive ( 20 -- * Primitive vectors 21 Vector(..), MVector(..), Prim, 22 23 -- * Accessors 24 25 -- ** Length information 26 length, null, 27 28 -- ** Indexing 29 (!), (!?), head, last, 30 unsafeIndex, unsafeHead, unsafeLast, 31 32 -- ** Monadic indexing 33 indexM, headM, lastM, 34 unsafeIndexM, unsafeHeadM, unsafeLastM, 35 36 -- ** Extracting subvectors (slicing) 37 slice, init, tail, take, drop, splitAt, 38 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, 39 40 -- * Construction 41 42 -- ** Initialisation 43 empty, singleton, replicate, generate, iterateN, 44 45 -- ** Monadic initialisation 46 replicateM, generateM, iterateNM, create, createT, 47 48 -- ** Unfolding 49 unfoldr, unfoldrN, 50 unfoldrM, unfoldrNM, 51 constructN, constructrN, 52 53 -- ** Enumeration 54 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo, 55 56 -- ** Concatenation 57 cons, snoc, (++), concat, 58 59 -- ** Restricting memory usage 60 force, 61 62 -- * Modifying vectors 63 64 -- ** Bulk updates 65 (//), update_, 66 unsafeUpd, unsafeUpdate_, 67 68 -- ** Accumulations 69 accum, accumulate_, 70 unsafeAccum, unsafeAccumulate_, 71 72 -- ** Permutations 73 reverse, backpermute, unsafeBackpermute, 74 75 -- ** Safe destructive updates 76 modify, 77 78 -- * Elementwise operations 79 80 -- ** Mapping 81 map, imap, concatMap, 82 83 -- ** Monadic mapping 84 mapM, mapM_, forM, forM_, 85 86 -- ** Zipping 87 zipWith, zipWith3, zipWith4, zipWith5, zipWith6, 88 izipWith, izipWith3, izipWith4, izipWith5, izipWith6, 89 90 -- ** Monadic zipping 91 zipWithM, zipWithM_, 92 93 -- * Working with predicates 94 95 -- ** Filtering 96 filter, ifilter, uniq, 97 mapMaybe, imapMaybe, 98 filterM, 99 takeWhile, dropWhile, 100 101 -- ** Partitioning 102 partition, unstablePartition, partitionWith, span, break, 103 104 -- ** Searching 105 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices, 106 107 -- * Folding 108 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1', 109 ifoldl, ifoldl', ifoldr, ifoldr', 110 111 -- ** Specialised folds 112 all, any, 113 sum, product, 114 maximum, maximumBy, minimum, minimumBy, 115 minIndex, minIndexBy, maxIndex, maxIndexBy, 116 117 -- ** Monadic folds 118 foldM, foldM', fold1M, fold1M', 119 foldM_, foldM'_, fold1M_, fold1M'_, 120 121 -- * Prefix sums (scans) 122 prescanl, prescanl', 123 postscanl, postscanl', 124 scanl, scanl', scanl1, scanl1', 125 prescanr, prescanr', 126 postscanr, postscanr', 127 scanr, scanr', scanr1, scanr1', 128 129 -- * Conversions 130 131 -- ** Lists 132 toList, fromList, fromListN, 133 134 -- ** Other vector types 135 G.convert, 136 137 -- ** Mutable vectors 138 freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy 139) where 140 141import qualified Data.Vector.Generic as G 142import Data.Vector.Primitive.Mutable ( MVector(..) ) 143import qualified Data.Vector.Fusion.Bundle as Bundle 144import Data.Primitive.ByteArray 145import Data.Primitive ( Prim, sizeOf ) 146 147import Control.DeepSeq ( NFData(rnf) 148#if MIN_VERSION_deepseq(1,4,3) 149 , NFData1(liftRnf) 150#endif 151 ) 152 153import Control.Monad ( liftM ) 154import Control.Monad.ST ( ST ) 155import Control.Monad.Primitive 156 157import Prelude hiding ( length, null, 158 replicate, (++), concat, 159 head, last, 160 init, tail, take, drop, splitAt, reverse, 161 map, concatMap, 162 zipWith, zipWith3, zip, zip3, unzip, unzip3, 163 filter, takeWhile, dropWhile, span, break, 164 elem, notElem, 165 foldl, foldl1, foldr, foldr1, 166 all, any, sum, product, minimum, maximum, 167 scanl, scanl1, scanr, scanr1, 168 enumFromTo, enumFromThenTo, 169 mapM, mapM_ ) 170 171import Data.Typeable ( Typeable ) 172import Data.Data ( Data(..) ) 173import Text.Read ( Read(..), readListPrecDefault ) 174import Data.Semigroup ( Semigroup(..) ) 175 176#if !MIN_VERSION_base(4,8,0) 177import Data.Monoid ( Monoid(..) ) 178import Data.Traversable ( Traversable ) 179#endif 180 181#if __GLASGOW_HASKELL__ >= 708 182import qualified GHC.Exts as Exts 183#endif 184 185 186-- | Unboxed vectors of primitive types 187data Vector a = Vector {-# UNPACK #-} !Int 188 {-# UNPACK #-} !Int 189 {-# UNPACK #-} !ByteArray -- ^ offset, length, underlying byte array 190 deriving ( Typeable ) 191 192instance NFData (Vector a) where 193 rnf (Vector _ _ _) = () 194 195#if MIN_VERSION_deepseq(1,4,3) 196-- | @since 0.12.1.0 197instance NFData1 Vector where 198 liftRnf _ (Vector _ _ _) = () 199#endif 200 201instance (Show a, Prim a) => Show (Vector a) where 202 showsPrec = G.showsPrec 203 204instance (Read a, Prim a) => Read (Vector a) where 205 readPrec = G.readPrec 206 readListPrec = readListPrecDefault 207 208instance (Data a, Prim a) => Data (Vector a) where 209 gfoldl = G.gfoldl 210 toConstr _ = G.mkVecConstr "Data.Vector.Primitive.Vector" 211 gunfold = G.gunfold 212 dataTypeOf _ = G.mkVecType "Data.Vector.Primitive.Vector" 213 dataCast1 = G.dataCast 214 215 216type instance G.Mutable Vector = MVector 217 218instance Prim a => G.Vector Vector a where 219 {-# INLINE basicUnsafeFreeze #-} 220 basicUnsafeFreeze (MVector i n marr) 221 = Vector i n `liftM` unsafeFreezeByteArray marr 222 223 {-# INLINE basicUnsafeThaw #-} 224 basicUnsafeThaw (Vector i n arr) 225 = MVector i n `liftM` unsafeThawByteArray arr 226 227 {-# INLINE basicLength #-} 228 basicLength (Vector _ n _) = n 229 230 {-# INLINE basicUnsafeSlice #-} 231 basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr 232 233 {-# INLINE basicUnsafeIndexM #-} 234 basicUnsafeIndexM (Vector i _ arr) j = return $! indexByteArray arr (i+j) 235 236 {-# INLINE basicUnsafeCopy #-} 237 basicUnsafeCopy (MVector i n dst) (Vector j _ src) 238 = copyByteArray dst (i*sz) src (j*sz) (n*sz) 239 where 240 sz = sizeOf (undefined :: a) 241 242 {-# INLINE elemseq #-} 243 elemseq _ = seq 244 245-- See http://trac.haskell.org/vector/ticket/12 246instance (Prim a, Eq a) => Eq (Vector a) where 247 {-# INLINE (==) #-} 248 xs == ys = Bundle.eq (G.stream xs) (G.stream ys) 249 250 {-# INLINE (/=) #-} 251 xs /= ys = not (Bundle.eq (G.stream xs) (G.stream ys)) 252 253-- See http://trac.haskell.org/vector/ticket/12 254instance (Prim a, Ord a) => Ord (Vector a) where 255 {-# INLINE compare #-} 256 compare xs ys = Bundle.cmp (G.stream xs) (G.stream ys) 257 258 {-# INLINE (<) #-} 259 xs < ys = Bundle.cmp (G.stream xs) (G.stream ys) == LT 260 261 {-# INLINE (<=) #-} 262 xs <= ys = Bundle.cmp (G.stream xs) (G.stream ys) /= GT 263 264 {-# INLINE (>) #-} 265 xs > ys = Bundle.cmp (G.stream xs) (G.stream ys) == GT 266 267 {-# INLINE (>=) #-} 268 xs >= ys = Bundle.cmp (G.stream xs) (G.stream ys) /= LT 269 270instance Prim a => Semigroup (Vector a) where 271 {-# INLINE (<>) #-} 272 (<>) = (++) 273 274 {-# INLINE sconcat #-} 275 sconcat = G.concatNE 276 277instance Prim a => Monoid (Vector a) where 278 {-# INLINE mempty #-} 279 mempty = empty 280 281 {-# INLINE mappend #-} 282 mappend = (++) 283 284 {-# INLINE mconcat #-} 285 mconcat = concat 286 287#if __GLASGOW_HASKELL__ >= 708 288 289instance Prim a => Exts.IsList (Vector a) where 290 type Item (Vector a) = a 291 fromList = fromList 292 fromListN = fromListN 293 toList = toList 294 295#endif 296-- Length 297-- ------ 298 299-- | /O(1)/ Yield the length of the vector 300length :: Prim a => Vector a -> Int 301{-# INLINE length #-} 302length = G.length 303 304-- | /O(1)/ Test whether a vector is empty 305null :: Prim a => Vector a -> Bool 306{-# INLINE null #-} 307null = G.null 308 309-- Indexing 310-- -------- 311 312-- | O(1) Indexing 313(!) :: Prim a => Vector a -> Int -> a 314{-# INLINE (!) #-} 315(!) = (G.!) 316 317-- | O(1) Safe indexing 318(!?) :: Prim a => Vector a -> Int -> Maybe a 319{-# INLINE (!?) #-} 320(!?) = (G.!?) 321 322-- | /O(1)/ First element 323head :: Prim a => Vector a -> a 324{-# INLINE head #-} 325head = G.head 326 327-- | /O(1)/ Last element 328last :: Prim a => Vector a -> a 329{-# INLINE last #-} 330last = G.last 331 332-- | /O(1)/ Unsafe indexing without bounds checking 333unsafeIndex :: Prim a => Vector a -> Int -> a 334{-# INLINE unsafeIndex #-} 335unsafeIndex = G.unsafeIndex 336 337-- | /O(1)/ First element without checking if the vector is empty 338unsafeHead :: Prim a => Vector a -> a 339{-# INLINE unsafeHead #-} 340unsafeHead = G.unsafeHead 341 342-- | /O(1)/ Last element without checking if the vector is empty 343unsafeLast :: Prim a => Vector a -> a 344{-# INLINE unsafeLast #-} 345unsafeLast = G.unsafeLast 346 347-- Monadic indexing 348-- ---------------- 349 350-- | /O(1)/ Indexing in a monad. 351-- 352-- The monad allows operations to be strict in the vector when necessary. 353-- Suppose vector copying is implemented like this: 354-- 355-- > copy mv v = ... write mv i (v ! i) ... 356-- 357-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@ 358-- would unnecessarily retain a reference to @v@ in each element written. 359-- 360-- With 'indexM', copying can be implemented like this instead: 361-- 362-- > copy mv v = ... do 363-- > x <- indexM v i 364-- > write mv i x 365-- 366-- Here, no references to @v@ are retained because indexing (but /not/ the 367-- elements) is evaluated eagerly. 368-- 369indexM :: (Prim a, Monad m) => Vector a -> Int -> m a 370{-# INLINE indexM #-} 371indexM = G.indexM 372 373-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an 374-- explanation of why this is useful. 375headM :: (Prim a, Monad m) => Vector a -> m a 376{-# INLINE headM #-} 377headM = G.headM 378 379-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an 380-- explanation of why this is useful. 381lastM :: (Prim a, Monad m) => Vector a -> m a 382{-# INLINE lastM #-} 383lastM = G.lastM 384 385-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an 386-- explanation of why this is useful. 387unsafeIndexM :: (Prim a, Monad m) => Vector a -> Int -> m a 388{-# INLINE unsafeIndexM #-} 389unsafeIndexM = G.unsafeIndexM 390 391-- | /O(1)/ First element in a monad without checking for empty vectors. 392-- See 'indexM' for an explanation of why this is useful. 393unsafeHeadM :: (Prim a, Monad m) => Vector a -> m a 394{-# INLINE unsafeHeadM #-} 395unsafeHeadM = G.unsafeHeadM 396 397-- | /O(1)/ Last element in a monad without checking for empty vectors. 398-- See 'indexM' for an explanation of why this is useful. 399unsafeLastM :: (Prim a, Monad m) => Vector a -> m a 400{-# INLINE unsafeLastM #-} 401unsafeLastM = G.unsafeLastM 402 403-- Extracting subvectors (slicing) 404-- ------------------------------- 405 406-- | /O(1)/ Yield a slice of the vector without copying it. The vector must 407-- contain at least @i+n@ elements. 408slice :: Prim a 409 => Int -- ^ @i@ starting index 410 -> Int -- ^ @n@ length 411 -> Vector a 412 -> Vector a 413{-# INLINE slice #-} 414slice = G.slice 415 416-- | /O(1)/ Yield all but the last element without copying. The vector may not 417-- be empty. 418init :: Prim a => Vector a -> Vector a 419{-# INLINE init #-} 420init = G.init 421 422-- | /O(1)/ Yield all but the first element without copying. The vector may not 423-- be empty. 424tail :: Prim a => Vector a -> Vector a 425{-# INLINE tail #-} 426tail = G.tail 427 428-- | /O(1)/ Yield at the first @n@ elements without copying. The vector may 429-- contain less than @n@ elements in which case it is returned unchanged. 430take :: Prim a => Int -> Vector a -> Vector a 431{-# INLINE take #-} 432take = G.take 433 434-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may 435-- contain less than @n@ elements in which case an empty vector is returned. 436drop :: Prim a => Int -> Vector a -> Vector a 437{-# INLINE drop #-} 438drop = G.drop 439 440-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying. 441-- 442-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@ 443-- but slightly more efficient. 444{-# INLINE splitAt #-} 445splitAt :: Prim a => Int -> Vector a -> (Vector a, Vector a) 446splitAt = G.splitAt 447 448-- | /O(1)/ Yield a slice of the vector without copying. The vector must 449-- contain at least @i+n@ elements but this is not checked. 450unsafeSlice :: Prim a => Int -- ^ @i@ starting index 451 -> Int -- ^ @n@ length 452 -> Vector a 453 -> Vector a 454{-# INLINE unsafeSlice #-} 455unsafeSlice = G.unsafeSlice 456 457-- | /O(1)/ Yield all but the last element without copying. The vector may not 458-- be empty but this is not checked. 459unsafeInit :: Prim a => Vector a -> Vector a 460{-# INLINE unsafeInit #-} 461unsafeInit = G.unsafeInit 462 463-- | /O(1)/ Yield all but the first element without copying. The vector may not 464-- be empty but this is not checked. 465unsafeTail :: Prim a => Vector a -> Vector a 466{-# INLINE unsafeTail #-} 467unsafeTail = G.unsafeTail 468 469-- | /O(1)/ Yield the first @n@ elements without copying. The vector must 470-- contain at least @n@ elements but this is not checked. 471unsafeTake :: Prim a => Int -> Vector a -> Vector a 472{-# INLINE unsafeTake #-} 473unsafeTake = G.unsafeTake 474 475-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector 476-- must contain at least @n@ elements but this is not checked. 477unsafeDrop :: Prim a => Int -> Vector a -> Vector a 478{-# INLINE unsafeDrop #-} 479unsafeDrop = G.unsafeDrop 480 481-- Initialisation 482-- -------------- 483 484-- | /O(1)/ Empty vector 485empty :: Prim a => Vector a 486{-# INLINE empty #-} 487empty = G.empty 488 489-- | /O(1)/ Vector with exactly one element 490singleton :: Prim a => a -> Vector a 491{-# INLINE singleton #-} 492singleton = G.singleton 493 494-- | /O(n)/ Vector of the given length with the same value in each position 495replicate :: Prim a => Int -> a -> Vector a 496{-# INLINE replicate #-} 497replicate = G.replicate 498 499-- | /O(n)/ Construct a vector of the given length by applying the function to 500-- each index 501generate :: Prim a => Int -> (Int -> a) -> Vector a 502{-# INLINE generate #-} 503generate = G.generate 504 505-- | /O(n)/ Apply function n times to value. Zeroth element is original value. 506iterateN :: Prim a => Int -> (a -> a) -> a -> Vector a 507{-# INLINE iterateN #-} 508iterateN = G.iterateN 509 510-- Unfolding 511-- --------- 512 513-- | /O(n)/ Construct a vector by repeatedly applying the generator function 514-- to a seed. The generator function yields 'Just' the next element and the 515-- new seed or 'Nothing' if there are no more elements. 516-- 517-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10 518-- > = <10,9,8,7,6,5,4,3,2,1> 519unfoldr :: Prim a => (b -> Maybe (a, b)) -> b -> Vector a 520{-# INLINE unfoldr #-} 521unfoldr = G.unfoldr 522 523-- | /O(n)/ Construct a vector with at most @n@ elements by repeatedly applying 524-- the generator function to a seed. The generator function yields 'Just' the 525-- next element and the new seed or 'Nothing' if there are no more elements. 526-- 527-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8> 528unfoldrN :: Prim a => Int -> (b -> Maybe (a, b)) -> b -> Vector a 529{-# INLINE unfoldrN #-} 530unfoldrN = G.unfoldrN 531 532-- | /O(n)/ Construct a vector by repeatedly applying the monadic 533-- generator function to a seed. The generator function yields 'Just' 534-- the next element and the new seed or 'Nothing' if there are no more 535-- elements. 536unfoldrM :: (Monad m, Prim a) => (b -> m (Maybe (a, b))) -> b -> m (Vector a) 537{-# INLINE unfoldrM #-} 538unfoldrM = G.unfoldrM 539 540-- | /O(n)/ Construct a vector by repeatedly applying the monadic 541-- generator function to a seed. The generator function yields 'Just' 542-- the next element and the new seed or 'Nothing' if there are no more 543-- elements. 544unfoldrNM :: (Monad m, Prim a) => Int -> (b -> m (Maybe (a, b))) -> b -> m (Vector a) 545{-# INLINE unfoldrNM #-} 546unfoldrNM = G.unfoldrNM 547 548-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the 549-- generator function to the already constructed part of the vector. 550-- 551-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in <a,b,c> 552-- 553constructN :: Prim a => Int -> (Vector a -> a) -> Vector a 554{-# INLINE constructN #-} 555constructN = G.constructN 556 557-- | /O(n)/ Construct a vector with @n@ elements from right to left by 558-- repeatedly applying the generator function to the already constructed part 559-- of the vector. 560-- 561-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in <c,b,a> 562-- 563constructrN :: Prim a => Int -> (Vector a -> a) -> Vector a 564{-# INLINE constructrN #-} 565constructrN = G.constructrN 566 567-- Enumeration 568-- ----------- 569 570-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@ 571-- etc. This operation is usually more efficient than 'enumFromTo'. 572-- 573-- > enumFromN 5 3 = <5,6,7> 574enumFromN :: (Prim a, Num a) => a -> Int -> Vector a 575{-# INLINE enumFromN #-} 576enumFromN = G.enumFromN 577 578-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@, 579-- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'. 580-- 581-- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4> 582enumFromStepN :: (Prim a, Num a) => a -> a -> Int -> Vector a 583{-# INLINE enumFromStepN #-} 584enumFromStepN = G.enumFromStepN 585 586-- | /O(n)/ Enumerate values from @x@ to @y@. 587-- 588-- /WARNING:/ This operation can be very inefficient. If at all possible, use 589-- 'enumFromN' instead. 590enumFromTo :: (Prim a, Enum a) => a -> a -> Vector a 591{-# INLINE enumFromTo #-} 592enumFromTo = G.enumFromTo 593 594-- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@. 595-- 596-- /WARNING:/ This operation can be very inefficient. If at all possible, use 597-- 'enumFromStepN' instead. 598enumFromThenTo :: (Prim a, Enum a) => a -> a -> a -> Vector a 599{-# INLINE enumFromThenTo #-} 600enumFromThenTo = G.enumFromThenTo 601 602-- Concatenation 603-- ------------- 604 605-- | /O(n)/ Prepend an element 606cons :: Prim a => a -> Vector a -> Vector a 607{-# INLINE cons #-} 608cons = G.cons 609 610-- | /O(n)/ Append an element 611snoc :: Prim a => Vector a -> a -> Vector a 612{-# INLINE snoc #-} 613snoc = G.snoc 614 615infixr 5 ++ 616-- | /O(m+n)/ Concatenate two vectors 617(++) :: Prim a => Vector a -> Vector a -> Vector a 618{-# INLINE (++) #-} 619(++) = (G.++) 620 621-- | /O(n)/ Concatenate all vectors in the list 622concat :: Prim a => [Vector a] -> Vector a 623{-# INLINE concat #-} 624concat = G.concat 625 626-- Monadic initialisation 627-- ---------------------- 628 629-- | /O(n)/ Execute the monadic action the given number of times and store the 630-- results in a vector. 631replicateM :: (Monad m, Prim a) => Int -> m a -> m (Vector a) 632{-# INLINE replicateM #-} 633replicateM = G.replicateM 634 635-- | /O(n)/ Construct a vector of the given length by applying the monadic 636-- action to each index 637generateM :: (Monad m, Prim a) => Int -> (Int -> m a) -> m (Vector a) 638{-# INLINE generateM #-} 639generateM = G.generateM 640 641-- | /O(n)/ Apply monadic function n times to value. Zeroth element is original value. 642iterateNM :: (Monad m, Prim a) => Int -> (a -> m a) -> a -> m (Vector a) 643{-# INLINE iterateNM #-} 644iterateNM = G.iterateNM 645 646-- | Execute the monadic action and freeze the resulting vector. 647-- 648-- @ 649-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\'; return v }) = \<'a','b'\> 650-- @ 651create :: Prim a => (forall s. ST s (MVector s a)) -> Vector a 652{-# INLINE create #-} 653-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120 654create p = G.create p 655 656-- | Execute the monadic action and freeze the resulting vectors. 657createT :: (Traversable f, Prim a) => (forall s. ST s (f (MVector s a))) -> f (Vector a) 658{-# INLINE createT #-} 659createT p = G.createT p 660 661-- Restricting memory usage 662-- ------------------------ 663 664-- | /O(n)/ Yield the argument but force it not to retain any extra memory, 665-- possibly by copying it. 666-- 667-- This is especially useful when dealing with slices. For example: 668-- 669-- > force (slice 0 2 <huge vector>) 670-- 671-- Here, the slice retains a reference to the huge vector. Forcing it creates 672-- a copy of just the elements that belong to the slice and allows the huge 673-- vector to be garbage collected. 674force :: Prim a => Vector a -> Vector a 675{-# INLINE force #-} 676force = G.force 677 678-- Bulk updates 679-- ------------ 680 681-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector 682-- element at position @i@ by @a@. 683-- 684-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7> 685-- 686(//) :: Prim a => Vector a -- ^ initial vector (of length @m@) 687 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 688 -> Vector a 689{-# INLINE (//) #-} 690(//) = (G.//) 691 692-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the 693-- corresponding value @a@ from the value vector, replace the element of the 694-- initial vector at position @i@ by @a@. 695-- 696-- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7> 697-- 698update_ :: Prim a 699 => Vector a -- ^ initial vector (of length @m@) 700 -> Vector Int -- ^ index vector (of length @n1@) 701 -> Vector a -- ^ value vector (of length @n2@) 702 -> Vector a 703{-# INLINE update_ #-} 704update_ = G.update_ 705 706-- | Same as ('//') but without bounds checking. 707unsafeUpd :: Prim a => Vector a -> [(Int, a)] -> Vector a 708{-# INLINE unsafeUpd #-} 709unsafeUpd = G.unsafeUpd 710 711-- | Same as 'update_' but without bounds checking. 712unsafeUpdate_ :: Prim a => Vector a -> Vector Int -> Vector a -> Vector a 713{-# INLINE unsafeUpdate_ #-} 714unsafeUpdate_ = G.unsafeUpdate_ 715 716-- Accumulations 717-- ------------- 718 719-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element 720-- @a@ at position @i@ by @f a b@. 721-- 722-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4> 723accum :: Prim a 724 => (a -> b -> a) -- ^ accumulating function @f@ 725 -> Vector a -- ^ initial vector (of length @m@) 726 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@) 727 -> Vector a 728{-# INLINE accum #-} 729accum = G.accum 730 731-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the 732-- corresponding value @b@ from the the value vector, 733-- replace the element of the initial vector at 734-- position @i@ by @f a b@. 735-- 736-- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4> 737-- 738accumulate_ :: (Prim a, Prim b) 739 => (a -> b -> a) -- ^ accumulating function @f@ 740 -> Vector a -- ^ initial vector (of length @m@) 741 -> Vector Int -- ^ index vector (of length @n1@) 742 -> Vector b -- ^ value vector (of length @n2@) 743 -> Vector a 744{-# INLINE accumulate_ #-} 745accumulate_ = G.accumulate_ 746 747-- | Same as 'accum' but without bounds checking. 748unsafeAccum :: Prim a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a 749{-# INLINE unsafeAccum #-} 750unsafeAccum = G.unsafeAccum 751 752-- | Same as 'accumulate_' but without bounds checking. 753unsafeAccumulate_ :: (Prim a, Prim b) => 754 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a 755{-# INLINE unsafeAccumulate_ #-} 756unsafeAccumulate_ = G.unsafeAccumulate_ 757 758-- Permutations 759-- ------------ 760 761-- | /O(n)/ Reverse a vector 762reverse :: Prim a => Vector a -> Vector a 763{-# INLINE reverse #-} 764reverse = G.reverse 765 766-- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the 767-- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is 768-- often much more efficient. 769-- 770-- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a> 771backpermute :: Prim a => Vector a -> Vector Int -> Vector a 772{-# INLINE backpermute #-} 773backpermute = G.backpermute 774 775-- | Same as 'backpermute' but without bounds checking. 776unsafeBackpermute :: Prim a => Vector a -> Vector Int -> Vector a 777{-# INLINE unsafeBackpermute #-} 778unsafeBackpermute = G.unsafeBackpermute 779 780-- Safe destructive updates 781-- ------------------------ 782 783-- | Apply a destructive operation to a vector. The operation will be 784-- performed in place if it is safe to do so and will modify a copy of the 785-- vector otherwise. 786-- 787-- @ 788-- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\> 789-- @ 790modify :: Prim a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a 791{-# INLINE modify #-} 792modify p = G.modify p 793 794-- Mapping 795-- ------- 796 797-- | /O(n)/ Map a function over a vector 798map :: (Prim a, Prim b) => (a -> b) -> Vector a -> Vector b 799{-# INLINE map #-} 800map = G.map 801 802-- | /O(n)/ Apply a function to every element of a vector and its index 803imap :: (Prim a, Prim b) => (Int -> a -> b) -> Vector a -> Vector b 804{-# INLINE imap #-} 805imap = G.imap 806 807-- | Map a function over a vector and concatenate the results. 808concatMap :: (Prim a, Prim b) => (a -> Vector b) -> Vector a -> Vector b 809{-# INLINE concatMap #-} 810concatMap = G.concatMap 811 812-- Monadic mapping 813-- --------------- 814 815-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a 816-- vector of results 817mapM :: (Monad m, Prim a, Prim b) => (a -> m b) -> Vector a -> m (Vector b) 818{-# INLINE mapM #-} 819mapM = G.mapM 820 821-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the 822-- results 823mapM_ :: (Monad m, Prim a) => (a -> m b) -> Vector a -> m () 824{-# INLINE mapM_ #-} 825mapM_ = G.mapM_ 826 827-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a 828-- vector of results. Equivalent to @flip 'mapM'@. 829forM :: (Monad m, Prim a, Prim b) => Vector a -> (a -> m b) -> m (Vector b) 830{-# INLINE forM #-} 831forM = G.forM 832 833-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the 834-- results. Equivalent to @flip 'mapM_'@. 835forM_ :: (Monad m, Prim a) => Vector a -> (a -> m b) -> m () 836{-# INLINE forM_ #-} 837forM_ = G.forM_ 838 839-- Zipping 840-- ------- 841 842-- | /O(min(m,n))/ Zip two vectors with the given function. 843zipWith :: (Prim a, Prim b, Prim c) 844 => (a -> b -> c) -> Vector a -> Vector b -> Vector c 845{-# INLINE zipWith #-} 846zipWith = G.zipWith 847 848-- | Zip three vectors with the given function. 849zipWith3 :: (Prim a, Prim b, Prim c, Prim d) 850 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d 851{-# INLINE zipWith3 #-} 852zipWith3 = G.zipWith3 853 854zipWith4 :: (Prim a, Prim b, Prim c, Prim d, Prim e) 855 => (a -> b -> c -> d -> e) 856 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 857{-# INLINE zipWith4 #-} 858zipWith4 = G.zipWith4 859 860zipWith5 :: (Prim a, Prim b, Prim c, Prim d, Prim e, 861 Prim f) 862 => (a -> b -> c -> d -> e -> f) 863 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 864 -> Vector f 865{-# INLINE zipWith5 #-} 866zipWith5 = G.zipWith5 867 868zipWith6 :: (Prim a, Prim b, Prim c, Prim d, Prim e, 869 Prim f, Prim g) 870 => (a -> b -> c -> d -> e -> f -> g) 871 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 872 -> Vector f -> Vector g 873{-# INLINE zipWith6 #-} 874zipWith6 = G.zipWith6 875 876-- | /O(min(m,n))/ Zip two vectors with a function that also takes the 877-- elements' indices. 878izipWith :: (Prim a, Prim b, Prim c) 879 => (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c 880{-# INLINE izipWith #-} 881izipWith = G.izipWith 882 883-- | Zip three vectors and their indices with the given function. 884izipWith3 :: (Prim a, Prim b, Prim c, Prim d) 885 => (Int -> a -> b -> c -> d) 886 -> Vector a -> Vector b -> Vector c -> Vector d 887{-# INLINE izipWith3 #-} 888izipWith3 = G.izipWith3 889 890izipWith4 :: (Prim a, Prim b, Prim c, Prim d, Prim e) 891 => (Int -> a -> b -> c -> d -> e) 892 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 893{-# INLINE izipWith4 #-} 894izipWith4 = G.izipWith4 895 896izipWith5 :: (Prim a, Prim b, Prim c, Prim d, Prim e, 897 Prim f) 898 => (Int -> a -> b -> c -> d -> e -> f) 899 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 900 -> Vector f 901{-# INLINE izipWith5 #-} 902izipWith5 = G.izipWith5 903 904izipWith6 :: (Prim a, Prim b, Prim c, Prim d, Prim e, 905 Prim f, Prim g) 906 => (Int -> a -> b -> c -> d -> e -> f -> g) 907 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e 908 -> Vector f -> Vector g 909{-# INLINE izipWith6 #-} 910izipWith6 = G.izipWith6 911 912-- Monadic zipping 913-- --------------- 914 915-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a 916-- vector of results 917zipWithM :: (Monad m, Prim a, Prim b, Prim c) 918 => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c) 919{-# INLINE zipWithM #-} 920zipWithM = G.zipWithM 921 922-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the 923-- results 924zipWithM_ :: (Monad m, Prim a, Prim b) 925 => (a -> b -> m c) -> Vector a -> Vector b -> m () 926{-# INLINE zipWithM_ #-} 927zipWithM_ = G.zipWithM_ 928 929-- Filtering 930-- --------- 931 932-- | /O(n)/ Drop elements that do not satisfy the predicate 933filter :: Prim a => (a -> Bool) -> Vector a -> Vector a 934{-# INLINE filter #-} 935filter = G.filter 936 937-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to 938-- values and their indices 939ifilter :: Prim a => (Int -> a -> Bool) -> Vector a -> Vector a 940{-# INLINE ifilter #-} 941ifilter = G.ifilter 942 943-- | /O(n)/ Drop repeated adjacent elements. 944uniq :: (Prim a, Eq a) => Vector a -> Vector a 945{-# INLINE uniq #-} 946uniq = G.uniq 947 948-- | /O(n)/ Drop elements when predicate returns Nothing 949mapMaybe :: (Prim a, Prim b) => (a -> Maybe b) -> Vector a -> Vector b 950{-# INLINE mapMaybe #-} 951mapMaybe = G.mapMaybe 952 953-- | /O(n)/ Drop elements when predicate, applied to index and value, returns Nothing 954imapMaybe :: (Prim a, Prim b) => (Int -> a -> Maybe b) -> Vector a -> Vector b 955{-# INLINE imapMaybe #-} 956imapMaybe = G.imapMaybe 957 958-- | /O(n)/ Drop elements that do not satisfy the monadic predicate 959filterM :: (Monad m, Prim a) => (a -> m Bool) -> Vector a -> m (Vector a) 960{-# INLINE filterM #-} 961filterM = G.filterM 962 963-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate 964-- without copying. 965takeWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a 966{-# INLINE takeWhile #-} 967takeWhile = G.takeWhile 968 969-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate 970-- without copying. 971dropWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a 972{-# INLINE dropWhile #-} 973dropWhile = G.dropWhile 974 975-- Parititioning 976-- ------------- 977 978-- | /O(n)/ Split the vector in two parts, the first one containing those 979-- elements that satisfy the predicate and the second one those that don't. The 980-- relative order of the elements is preserved at the cost of a sometimes 981-- reduced performance compared to 'unstablePartition'. 982partition :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) 983{-# INLINE partition #-} 984partition = G.partition 985 986-- | /O(n)/ Split the vector in two parts, the first one containing those 987-- elements that satisfy the predicate and the second one those that don't. 988-- The order of the elements is not preserved but the operation is often 989-- faster than 'partition'. 990unstablePartition :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) 991{-# INLINE unstablePartition #-} 992unstablePartition = G.unstablePartition 993 994-- | /O(n)/ Split the vector in two parts, the first one containing the 995-- @Right@ elements and the second containing the @Left@ elements. 996-- The relative order of the elements is preserved. 997-- 998-- @since 0.12.1.0 999partitionWith :: (Prim a, Prim b, Prim c) => (a -> Either b c) -> Vector a -> (Vector b, Vector c) 1000{-# INLINE partitionWith #-} 1001partitionWith = G.partitionWith 1002 1003-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy 1004-- the predicate and the rest without copying. 1005span :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) 1006{-# INLINE span #-} 1007span = G.span 1008 1009-- | /O(n)/ Split the vector into the longest prefix of elements that do not 1010-- satisfy the predicate and the rest without copying. 1011break :: Prim a => (a -> Bool) -> Vector a -> (Vector a, Vector a) 1012{-# INLINE break #-} 1013break = G.break 1014 1015-- Searching 1016-- --------- 1017 1018infix 4 `elem` 1019-- | /O(n)/ Check if the vector contains an element 1020elem :: (Prim a, Eq a) => a -> Vector a -> Bool 1021{-# INLINE elem #-} 1022elem = G.elem 1023 1024infix 4 `notElem` 1025-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem') 1026notElem :: (Prim a, Eq a) => a -> Vector a -> Bool 1027{-# INLINE notElem #-} 1028notElem = G.notElem 1029 1030-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing' 1031-- if no such element exists. 1032find :: Prim a => (a -> Bool) -> Vector a -> Maybe a 1033{-# INLINE find #-} 1034find = G.find 1035 1036-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate 1037-- or 'Nothing' if no such element exists. 1038findIndex :: Prim a => (a -> Bool) -> Vector a -> Maybe Int 1039{-# INLINE findIndex #-} 1040findIndex = G.findIndex 1041 1042-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending 1043-- order. 1044findIndices :: Prim a => (a -> Bool) -> Vector a -> Vector Int 1045{-# INLINE findIndices #-} 1046findIndices = G.findIndices 1047 1048-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or 1049-- 'Nothing' if the vector does not contain the element. This is a specialised 1050-- version of 'findIndex'. 1051elemIndex :: (Prim a, Eq a) => a -> Vector a -> Maybe Int 1052{-# INLINE elemIndex #-} 1053elemIndex = G.elemIndex 1054 1055-- | /O(n)/ Yield the indices of all occurences of the given element in 1056-- ascending order. This is a specialised version of 'findIndices'. 1057elemIndices :: (Prim a, Eq a) => a -> Vector a -> Vector Int 1058{-# INLINE elemIndices #-} 1059elemIndices = G.elemIndices 1060 1061-- Folding 1062-- ------- 1063 1064-- | /O(n)/ Left fold 1065foldl :: Prim b => (a -> b -> a) -> a -> Vector b -> a 1066{-# INLINE foldl #-} 1067foldl = G.foldl 1068 1069-- | /O(n)/ Left fold on non-empty vectors 1070foldl1 :: Prim a => (a -> a -> a) -> Vector a -> a 1071{-# INLINE foldl1 #-} 1072foldl1 = G.foldl1 1073 1074-- | /O(n)/ Left fold with strict accumulator 1075foldl' :: Prim b => (a -> b -> a) -> a -> Vector b -> a 1076{-# INLINE foldl' #-} 1077foldl' = G.foldl' 1078 1079-- | /O(n)/ Left fold on non-empty vectors with strict accumulator 1080foldl1' :: Prim a => (a -> a -> a) -> Vector a -> a 1081{-# INLINE foldl1' #-} 1082foldl1' = G.foldl1' 1083 1084-- | /O(n)/ Right fold 1085foldr :: Prim a => (a -> b -> b) -> b -> Vector a -> b 1086{-# INLINE foldr #-} 1087foldr = G.foldr 1088 1089-- | /O(n)/ Right fold on non-empty vectors 1090foldr1 :: Prim a => (a -> a -> a) -> Vector a -> a 1091{-# INLINE foldr1 #-} 1092foldr1 = G.foldr1 1093 1094-- | /O(n)/ Right fold with a strict accumulator 1095foldr' :: Prim a => (a -> b -> b) -> b -> Vector a -> b 1096{-# INLINE foldr' #-} 1097foldr' = G.foldr' 1098 1099-- | /O(n)/ Right fold on non-empty vectors with strict accumulator 1100foldr1' :: Prim a => (a -> a -> a) -> Vector a -> a 1101{-# INLINE foldr1' #-} 1102foldr1' = G.foldr1' 1103 1104-- | /O(n)/ Left fold (function applied to each element and its index) 1105ifoldl :: Prim b => (a -> Int -> b -> a) -> a -> Vector b -> a 1106{-# INLINE ifoldl #-} 1107ifoldl = G.ifoldl 1108 1109-- | /O(n)/ Left fold with strict accumulator (function applied to each element 1110-- and its index) 1111ifoldl' :: Prim b => (a -> Int -> b -> a) -> a -> Vector b -> a 1112{-# INLINE ifoldl' #-} 1113ifoldl' = G.ifoldl' 1114 1115-- | /O(n)/ Right fold (function applied to each element and its index) 1116ifoldr :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b 1117{-# INLINE ifoldr #-} 1118ifoldr = G.ifoldr 1119 1120-- | /O(n)/ Right fold with strict accumulator (function applied to each 1121-- element and its index) 1122ifoldr' :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b 1123{-# INLINE ifoldr' #-} 1124ifoldr' = G.ifoldr' 1125 1126-- Specialised folds 1127-- ----------------- 1128 1129-- | /O(n)/ Check if all elements satisfy the predicate. 1130all :: Prim a => (a -> Bool) -> Vector a -> Bool 1131{-# INLINE all #-} 1132all = G.all 1133 1134-- | /O(n)/ Check if any element satisfies the predicate. 1135any :: Prim a => (a -> Bool) -> Vector a -> Bool 1136{-# INLINE any #-} 1137any = G.any 1138 1139-- | /O(n)/ Compute the sum of the elements 1140sum :: (Prim a, Num a) => Vector a -> a 1141{-# INLINE sum #-} 1142sum = G.sum 1143 1144-- | /O(n)/ Compute the produce of the elements 1145product :: (Prim a, Num a) => Vector a -> a 1146{-# INLINE product #-} 1147product = G.product 1148 1149-- | /O(n)/ Yield the maximum element of the vector. The vector may not be 1150-- empty. 1151maximum :: (Prim a, Ord a) => Vector a -> a 1152{-# INLINE maximum #-} 1153maximum = G.maximum 1154 1155-- | /O(n)/ Yield the maximum element of the vector according to the given 1156-- comparison function. The vector may not be empty. 1157maximumBy :: Prim a => (a -> a -> Ordering) -> Vector a -> a 1158{-# INLINE maximumBy #-} 1159maximumBy = G.maximumBy 1160 1161-- | /O(n)/ Yield the minimum element of the vector. The vector may not be 1162-- empty. 1163minimum :: (Prim a, Ord a) => Vector a -> a 1164{-# INLINE minimum #-} 1165minimum = G.minimum 1166 1167-- | /O(n)/ Yield the minimum element of the vector according to the given 1168-- comparison function. The vector may not be empty. 1169minimumBy :: Prim a => (a -> a -> Ordering) -> Vector a -> a 1170{-# INLINE minimumBy #-} 1171minimumBy = G.minimumBy 1172 1173-- | /O(n)/ Yield the index of the maximum element of the vector. The vector 1174-- may not be empty. 1175maxIndex :: (Prim a, Ord a) => Vector a -> Int 1176{-# INLINE maxIndex #-} 1177maxIndex = G.maxIndex 1178 1179-- | /O(n)/ Yield the index of the maximum element of the vector according to 1180-- the given comparison function. The vector may not be empty. 1181maxIndexBy :: Prim a => (a -> a -> Ordering) -> Vector a -> Int 1182{-# INLINE maxIndexBy #-} 1183maxIndexBy = G.maxIndexBy 1184 1185-- | /O(n)/ Yield the index of the minimum element of the vector. The vector 1186-- may not be empty. 1187minIndex :: (Prim a, Ord a) => Vector a -> Int 1188{-# INLINE minIndex #-} 1189minIndex = G.minIndex 1190 1191-- | /O(n)/ Yield the index of the minimum element of the vector according to 1192-- the given comparison function. The vector may not be empty. 1193minIndexBy :: Prim a => (a -> a -> Ordering) -> Vector a -> Int 1194{-# INLINE minIndexBy #-} 1195minIndexBy = G.minIndexBy 1196 1197-- Monadic folds 1198-- ------------- 1199 1200-- | /O(n)/ Monadic fold 1201foldM :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m a 1202{-# INLINE foldM #-} 1203foldM = G.foldM 1204 1205-- | /O(n)/ Monadic fold over non-empty vectors 1206fold1M :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m a 1207{-# INLINE fold1M #-} 1208fold1M = G.fold1M 1209 1210-- | /O(n)/ Monadic fold with strict accumulator 1211foldM' :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m a 1212{-# INLINE foldM' #-} 1213foldM' = G.foldM' 1214 1215-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator 1216fold1M' :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m a 1217{-# INLINE fold1M' #-} 1218fold1M' = G.fold1M' 1219 1220-- | /O(n)/ Monadic fold that discards the result 1221foldM_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m () 1222{-# INLINE foldM_ #-} 1223foldM_ = G.foldM_ 1224 1225-- | /O(n)/ Monadic fold over non-empty vectors that discards the result 1226fold1M_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m () 1227{-# INLINE fold1M_ #-} 1228fold1M_ = G.fold1M_ 1229 1230-- | /O(n)/ Monadic fold with strict accumulator that discards the result 1231foldM'_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m () 1232{-# INLINE foldM'_ #-} 1233foldM'_ = G.foldM'_ 1234 1235-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator 1236-- that discards the result 1237fold1M'_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m () 1238{-# INLINE fold1M'_ #-} 1239fold1M'_ = G.fold1M'_ 1240 1241-- Prefix sums (scans) 1242-- ------------------- 1243 1244-- | /O(n)/ Prescan 1245-- 1246-- @ 1247-- prescanl f z = 'init' . 'scanl' f z 1248-- @ 1249-- 1250-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@ 1251-- 1252prescanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1253{-# INLINE prescanl #-} 1254prescanl = G.prescanl 1255 1256-- | /O(n)/ Prescan with strict accumulator 1257prescanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1258{-# INLINE prescanl' #-} 1259prescanl' = G.prescanl' 1260 1261-- | /O(n)/ Scan 1262-- 1263-- @ 1264-- postscanl f z = 'tail' . 'scanl' f z 1265-- @ 1266-- 1267-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@ 1268-- 1269postscanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1270{-# INLINE postscanl #-} 1271postscanl = G.postscanl 1272 1273-- | /O(n)/ Scan with strict accumulator 1274postscanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1275{-# INLINE postscanl' #-} 1276postscanl' = G.postscanl' 1277 1278-- | /O(n)/ Haskell-style scan 1279-- 1280-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)> 1281-- > where y1 = z 1282-- > yi = f y(i-1) x(i-1) 1283-- 1284-- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@ 1285-- 1286scanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1287{-# INLINE scanl #-} 1288scanl = G.scanl 1289 1290-- | /O(n)/ Haskell-style scan with strict accumulator 1291scanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a 1292{-# INLINE scanl' #-} 1293scanl' = G.scanl' 1294 1295-- | /O(n)/ Scan over a non-empty vector 1296-- 1297-- > scanl f <x1,...,xn> = <y1,...,yn> 1298-- > where y1 = x1 1299-- > yi = f y(i-1) xi 1300-- 1301scanl1 :: Prim a => (a -> a -> a) -> Vector a -> Vector a 1302{-# INLINE scanl1 #-} 1303scanl1 = G.scanl1 1304 1305-- | /O(n)/ Scan over a non-empty vector with a strict accumulator 1306scanl1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a 1307{-# INLINE scanl1' #-} 1308scanl1' = G.scanl1' 1309 1310-- | /O(n)/ Right-to-left prescan 1311-- 1312-- @ 1313-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse' 1314-- @ 1315-- 1316prescanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1317{-# INLINE prescanr #-} 1318prescanr = G.prescanr 1319 1320-- | /O(n)/ Right-to-left prescan with strict accumulator 1321prescanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1322{-# INLINE prescanr' #-} 1323prescanr' = G.prescanr' 1324 1325-- | /O(n)/ Right-to-left scan 1326postscanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1327{-# INLINE postscanr #-} 1328postscanr = G.postscanr 1329 1330-- | /O(n)/ Right-to-left scan with strict accumulator 1331postscanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1332{-# INLINE postscanr' #-} 1333postscanr' = G.postscanr' 1334 1335-- | /O(n)/ Right-to-left Haskell-style scan 1336scanr :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1337{-# INLINE scanr #-} 1338scanr = G.scanr 1339 1340-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator 1341scanr' :: (Prim a, Prim b) => (a -> b -> b) -> b -> Vector a -> Vector b 1342{-# INLINE scanr' #-} 1343scanr' = G.scanr' 1344 1345-- | /O(n)/ Right-to-left scan over a non-empty vector 1346scanr1 :: Prim a => (a -> a -> a) -> Vector a -> Vector a 1347{-# INLINE scanr1 #-} 1348scanr1 = G.scanr1 1349 1350-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict 1351-- accumulator 1352scanr1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a 1353{-# INLINE scanr1' #-} 1354scanr1' = G.scanr1' 1355 1356-- Conversions - Lists 1357-- ------------------------ 1358 1359-- | /O(n)/ Convert a vector to a list 1360toList :: Prim a => Vector a -> [a] 1361{-# INLINE toList #-} 1362toList = G.toList 1363 1364-- | /O(n)/ Convert a list to a vector 1365fromList :: Prim a => [a] -> Vector a 1366{-# INLINE fromList #-} 1367fromList = G.fromList 1368 1369-- | /O(n)/ Convert the first @n@ elements of a list to a vector 1370-- 1371-- @ 1372-- fromListN n xs = 'fromList' ('take' n xs) 1373-- @ 1374fromListN :: Prim a => Int -> [a] -> Vector a 1375{-# INLINE fromListN #-} 1376fromListN = G.fromListN 1377 1378-- Conversions - Mutable vectors 1379-- ----------------------------- 1380 1381-- | /O(1)/ Unsafe convert a mutable vector to an immutable one without 1382-- copying. The mutable vector may not be used after this operation. 1383unsafeFreeze :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> m (Vector a) 1384{-# INLINE unsafeFreeze #-} 1385unsafeFreeze = G.unsafeFreeze 1386 1387-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without 1388-- copying. The immutable vector may not be used after this operation. 1389unsafeThaw :: (Prim a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a) 1390{-# INLINE unsafeThaw #-} 1391unsafeThaw = G.unsafeThaw 1392 1393-- | /O(n)/ Yield a mutable copy of the immutable vector. 1394thaw :: (Prim a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a) 1395{-# INLINE thaw #-} 1396thaw = G.thaw 1397 1398-- | /O(n)/ Yield an immutable copy of the mutable vector. 1399freeze :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> m (Vector a) 1400{-# INLINE freeze #-} 1401freeze = G.freeze 1402 1403-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must 1404-- have the same length. This is not checked. 1405unsafeCopy 1406 :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m () 1407{-# INLINE unsafeCopy #-} 1408unsafeCopy = G.unsafeCopy 1409 1410-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must 1411-- have the same length. 1412copy :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m () 1413{-# INLINE copy #-} 1414copy = G.copy 1415