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