1{-# LANGUAGE CPP, Rank2Types, MultiParamTypeClasses, FlexibleContexts, 2 TypeFamilies, ScopedTypeVariables, BangPatterns #-} 3-- | 4-- Module : Data.Vector.Generic 5-- Copyright : (c) Roman Leshchinskiy 2008-2010 6-- License : BSD-style 7-- 8-- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au> 9-- Stability : experimental 10-- Portability : non-portable 11-- 12-- Generic interface to pure vectors. 13-- 14 15module Data.Vector.Generic ( 16 -- * Immutable vectors 17 Vector(..), Mutable, 18 19 -- * Accessors 20 21 -- ** Length information 22 length, null, 23 24 -- ** Indexing 25 (!), (!?), head, last, 26 unsafeIndex, unsafeHead, unsafeLast, 27 28 -- ** Monadic indexing 29 indexM, headM, lastM, 30 unsafeIndexM, unsafeHeadM, unsafeLastM, 31 32 -- ** Extracting subvectors (slicing) 33 slice, init, tail, take, drop, splitAt, 34 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, 35 36 -- * Construction 37 38 -- ** Initialisation 39 empty, singleton, replicate, generate, iterateN, 40 41 -- ** Monadic initialisation 42 replicateM, generateM, iterateNM, create, createT, 43 44 -- ** Unfolding 45 unfoldr, unfoldrN, 46 unfoldrM, unfoldrNM, 47 constructN, constructrN, 48 49 -- ** Enumeration 50 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo, 51 52 -- ** Concatenation 53 cons, snoc, (++), concat, concatNE, 54 55 -- ** Restricting memory usage 56 force, 57 58 -- * Modifying vectors 59 60 -- ** Bulk updates 61 (//), update, update_, 62 unsafeUpd, unsafeUpdate, unsafeUpdate_, 63 64 -- ** Accumulations 65 accum, accumulate, accumulate_, 66 unsafeAccum, unsafeAccumulate, unsafeAccumulate_, 67 68 -- ** Permutations 69 reverse, backpermute, unsafeBackpermute, 70 71 -- ** Safe destructive updates 72 modify, 73 74 -- * Elementwise operations 75 76 -- ** Indexing 77 indexed, 78 79 -- ** Mapping 80 map, imap, concatMap, 81 82 -- ** Monadic mapping 83 mapM, imapM, mapM_, imapM_, forM, forM_, 84 85 -- ** Zipping 86 zipWith, zipWith3, zipWith4, zipWith5, zipWith6, 87 izipWith, izipWith3, izipWith4, izipWith5, izipWith6, 88 zip, zip3, zip4, zip5, zip6, 89 90 -- ** Monadic zipping 91 zipWithM, izipWithM, zipWithM_, izipWithM_, 92 93 -- ** Unzipping 94 unzip, unzip3, unzip4, unzip5, unzip6, 95 96 -- * Working with predicates 97 98 -- ** Filtering 99 filter, ifilter, uniq, 100 mapMaybe, imapMaybe, 101 filterM, 102 takeWhile, dropWhile, 103 104 -- ** Partitioning 105 partition, partitionWith, unstablePartition, span, break, 106 107 -- ** Searching 108 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices, 109 110 -- * Folding 111 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1', 112 ifoldl, ifoldl', ifoldr, ifoldr', 113 114 -- ** Specialised folds 115 all, any, and, or, 116 sum, product, 117 maximum, maximumBy, minimum, minimumBy, 118 minIndex, minIndexBy, maxIndex, maxIndexBy, 119 120 -- ** Monadic folds 121 foldM, ifoldM, foldM', ifoldM', 122 fold1M, fold1M', foldM_, ifoldM_, 123 foldM'_, ifoldM'_, fold1M_, fold1M'_, 124 125 -- ** Monadic sequencing 126 sequence, sequence_, 127 128 -- * Prefix sums (scans) 129 prescanl, prescanl', 130 postscanl, postscanl', 131 scanl, scanl', scanl1, scanl1', 132 iscanl, iscanl', 133 prescanr, prescanr', 134 postscanr, postscanr', 135 scanr, scanr', scanr1, scanr1', 136 iscanr, iscanr', 137 138 -- * Conversions 139 140 -- ** Lists 141 toList, fromList, fromListN, 142 143 -- ** Different vector types 144 convert, 145 146 -- ** Mutable vectors 147 freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy, 148 149 -- * Fusion support 150 151 -- ** Conversion to/from Bundles 152 stream, unstream, streamR, unstreamR, 153 154 -- ** Recycling support 155 new, clone, 156 157 -- * Utilities 158 159 -- ** Comparisons 160 eq, cmp, 161 eqBy, cmpBy, 162 163 -- ** Show and Read 164 showsPrec, readPrec, 165 liftShowsPrec, liftReadsPrec, 166 167 -- ** @Data@ and @Typeable@ 168 gfoldl, gunfold, dataCast, mkVecType, mkVecConstr, mkType 169) where 170 171import Data.Vector.Generic.Base 172 173import qualified Data.Vector.Generic.Mutable as M 174 175import qualified Data.Vector.Generic.New as New 176import Data.Vector.Generic.New ( New ) 177 178import qualified Data.Vector.Fusion.Bundle as Bundle 179import Data.Vector.Fusion.Bundle ( Bundle, MBundle, lift, inplace ) 180import qualified Data.Vector.Fusion.Bundle.Monadic as MBundle 181import Data.Vector.Fusion.Stream.Monadic ( Stream ) 182import qualified Data.Vector.Fusion.Stream.Monadic as S 183import Data.Vector.Fusion.Bundle.Size 184import Data.Vector.Fusion.Util 185 186import Control.Monad.ST ( ST, runST ) 187import Control.Monad.Primitive 188import Prelude hiding ( length, null, 189 replicate, (++), concat, 190 head, last, 191 init, tail, take, drop, splitAt, reverse, 192 map, concat, concatMap, 193 zipWith, zipWith3, zip, zip3, unzip, unzip3, 194 filter, takeWhile, dropWhile, span, break, 195 elem, notElem, 196 foldl, foldl1, foldr, foldr1, 197 all, any, and, or, sum, product, maximum, minimum, 198 scanl, scanl1, scanr, scanr1, 199 enumFromTo, enumFromThenTo, 200 mapM, mapM_, sequence, sequence_, 201 showsPrec ) 202 203import qualified Text.Read as Read 204import qualified Data.List.NonEmpty as NonEmpty 205 206#if __GLASGOW_HASKELL__ >= 707 207import Data.Typeable ( Typeable, gcast1 ) 208#else 209import Data.Typeable ( Typeable1, gcast1 ) 210#endif 211 212#include "vector.h" 213 214import Data.Data ( Data, DataType, Constr, Fixity(Prefix), 215 mkDataType, mkConstr, constrIndex, 216#if MIN_VERSION_base(4,2,0) 217 mkNoRepType ) 218#else 219 mkNorepType ) 220#endif 221import qualified Data.Traversable as T (Traversable(mapM)) 222 223#if !MIN_VERSION_base(4,2,0) 224mkNoRepType :: String -> DataType 225mkNoRepType = mkNorepType 226#endif 227 228-- Length information 229-- ------------------ 230 231-- | /O(1)/ Yield the length of the vector 232length :: Vector v a => v a -> Int 233{-# INLINE length #-} 234length = Bundle.length . stream' 235 236-- | /O(1)/ Test whether a vector is empty 237null :: Vector v a => v a -> Bool 238{-# INLINE null #-} 239null = Bundle.null . stream 240 241-- Indexing 242-- -------- 243 244infixl 9 ! 245-- | O(1) Indexing 246(!) :: Vector v a => v a -> Int -> a 247{-# INLINE_FUSED (!) #-} 248(!) v i = BOUNDS_CHECK(checkIndex) "(!)" i (length v) 249 $ unId (basicUnsafeIndexM v i) 250 251infixl 9 !? 252-- | O(1) Safe indexing 253(!?) :: Vector v a => v a -> Int -> Maybe a 254{-# INLINE_FUSED (!?) #-} 255v !? i | i < 0 || i >= length v = Nothing 256 | otherwise = Just $ unsafeIndex v i 257 258-- | /O(1)/ First element 259head :: Vector v a => v a -> a 260{-# INLINE_FUSED head #-} 261head v = v ! 0 262 263-- | /O(1)/ Last element 264last :: Vector v a => v a -> a 265{-# INLINE_FUSED last #-} 266last v = v ! (length v - 1) 267 268-- | /O(1)/ Unsafe indexing without bounds checking 269unsafeIndex :: Vector v a => v a -> Int -> a 270{-# INLINE_FUSED unsafeIndex #-} 271unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v) 272 $ unId (basicUnsafeIndexM v i) 273 274-- | /O(1)/ First element without checking if the vector is empty 275unsafeHead :: Vector v a => v a -> a 276{-# INLINE_FUSED unsafeHead #-} 277unsafeHead v = unsafeIndex v 0 278 279-- | /O(1)/ Last element without checking if the vector is empty 280unsafeLast :: Vector v a => v a -> a 281{-# INLINE_FUSED unsafeLast #-} 282unsafeLast v = unsafeIndex v (length v - 1) 283 284{-# RULES 285 286"(!)/unstream [Vector]" forall i s. 287 new (New.unstream s) ! i = s Bundle.!! i 288 289"(!?)/unstream [Vector]" forall i s. 290 new (New.unstream s) !? i = s Bundle.!? i 291 292"head/unstream [Vector]" forall s. 293 head (new (New.unstream s)) = Bundle.head s 294 295"last/unstream [Vector]" forall s. 296 last (new (New.unstream s)) = Bundle.last s 297 298"unsafeIndex/unstream [Vector]" forall i s. 299 unsafeIndex (new (New.unstream s)) i = s Bundle.!! i 300 301"unsafeHead/unstream [Vector]" forall s. 302 unsafeHead (new (New.unstream s)) = Bundle.head s 303 304"unsafeLast/unstream [Vector]" forall s. 305 unsafeLast (new (New.unstream s)) = Bundle.last s #-} 306 307 308 309-- Monadic indexing 310-- ---------------- 311 312-- | /O(1)/ Indexing in a monad. 313-- 314-- The monad allows operations to be strict in the vector when necessary. 315-- Suppose vector copying is implemented like this: 316-- 317-- > copy mv v = ... write mv i (v ! i) ... 318-- 319-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@ 320-- would unnecessarily retain a reference to @v@ in each element written. 321-- 322-- With 'indexM', copying can be implemented like this instead: 323-- 324-- > copy mv v = ... do 325-- > x <- indexM v i 326-- > write mv i x 327-- 328-- Here, no references to @v@ are retained because indexing (but /not/ the 329-- elements) is evaluated eagerly. 330-- 331indexM :: (Vector v a, Monad m) => v a -> Int -> m a 332{-# INLINE_FUSED indexM #-} 333indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v) 334 $ basicUnsafeIndexM v i 335 336-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an 337-- explanation of why this is useful. 338headM :: (Vector v a, Monad m) => v a -> m a 339{-# INLINE_FUSED headM #-} 340headM v = indexM v 0 341 342-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an 343-- explanation of why this is useful. 344lastM :: (Vector v a, Monad m) => v a -> m a 345{-# INLINE_FUSED lastM #-} 346lastM v = indexM v (length v - 1) 347 348-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an 349-- explanation of why this is useful. 350unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a 351{-# INLINE_FUSED unsafeIndexM #-} 352unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v) 353 $ basicUnsafeIndexM v i 354 355-- | /O(1)/ First element in a monad without checking for empty vectors. 356-- See 'indexM' for an explanation of why this is useful. 357unsafeHeadM :: (Vector v a, Monad m) => v a -> m a 358{-# INLINE_FUSED unsafeHeadM #-} 359unsafeHeadM v = unsafeIndexM v 0 360 361-- | /O(1)/ Last element in a monad without checking for empty vectors. 362-- See 'indexM' for an explanation of why this is useful. 363unsafeLastM :: (Vector v a, Monad m) => v a -> m a 364{-# INLINE_FUSED unsafeLastM #-} 365unsafeLastM v = unsafeIndexM v (length v - 1) 366 367{-# RULES 368 369"indexM/unstream [Vector]" forall s i. 370 indexM (new (New.unstream s)) i = lift s MBundle.!! i 371 372"headM/unstream [Vector]" forall s. 373 headM (new (New.unstream s)) = MBundle.head (lift s) 374 375"lastM/unstream [Vector]" forall s. 376 lastM (new (New.unstream s)) = MBundle.last (lift s) 377 378"unsafeIndexM/unstream [Vector]" forall s i. 379 unsafeIndexM (new (New.unstream s)) i = lift s MBundle.!! i 380 381"unsafeHeadM/unstream [Vector]" forall s. 382 unsafeHeadM (new (New.unstream s)) = MBundle.head (lift s) 383 384"unsafeLastM/unstream [Vector]" forall s. 385 unsafeLastM (new (New.unstream s)) = MBundle.last (lift s) #-} 386 387 388 389-- Extracting subvectors (slicing) 390-- ------------------------------- 391 392-- | /O(1)/ Yield a slice of the vector without copying it. The vector must 393-- contain at least @i+n@ elements. 394slice :: Vector v a => Int -- ^ @i@ starting index 395 -> Int -- ^ @n@ length 396 -> v a 397 -> v a 398{-# INLINE_FUSED slice #-} 399slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v) 400 $ basicUnsafeSlice i n v 401 402-- | /O(1)/ Yield all but the last element without copying. The vector may not 403-- be empty. 404init :: Vector v a => v a -> v a 405{-# INLINE_FUSED init #-} 406init v = slice 0 (length v - 1) v 407 408-- | /O(1)/ Yield all but the first element without copying. The vector may not 409-- be empty. 410tail :: Vector v a => v a -> v a 411{-# INLINE_FUSED tail #-} 412tail v = slice 1 (length v - 1) v 413 414-- | /O(1)/ Yield the first @n@ elements without copying. The vector may 415-- contain less than @n@ elements in which case it is returned unchanged. 416take :: Vector v a => Int -> v a -> v a 417{-# INLINE_FUSED take #-} 418take n v = unsafeSlice 0 (delay_inline min n' (length v)) v 419 where n' = max n 0 420 421-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may 422-- contain less than @n@ elements in which case an empty vector is returned. 423drop :: Vector v a => Int -> v a -> v a 424{-# INLINE_FUSED drop #-} 425drop n v = unsafeSlice (delay_inline min n' len) 426 (delay_inline max 0 (len - n')) v 427 where n' = max n 0 428 len = length v 429 430-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying. 431-- 432-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@ 433-- but slightly more efficient. 434{-# INLINE_FUSED splitAt #-} 435splitAt :: Vector v a => Int -> v a -> (v a, v a) 436splitAt n v = ( unsafeSlice 0 m v 437 , unsafeSlice m (delay_inline max 0 (len - n')) v 438 ) 439 where 440 m = delay_inline min n' len 441 n' = max n 0 442 len = length v 443 444-- | /O(1)/ Yield a slice of the vector without copying. The vector must 445-- contain at least @i+n@ elements but this is not checked. 446unsafeSlice :: Vector v a => Int -- ^ @i@ starting index 447 -> Int -- ^ @n@ length 448 -> v a 449 -> v a 450{-# INLINE_FUSED unsafeSlice #-} 451unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v) 452 $ basicUnsafeSlice i n v 453 454-- | /O(1)/ Yield all but the last element without copying. The vector may not 455-- be empty but this is not checked. 456unsafeInit :: Vector v a => v a -> v a 457{-# INLINE_FUSED unsafeInit #-} 458unsafeInit v = unsafeSlice 0 (length v - 1) v 459 460-- | /O(1)/ Yield all but the first element without copying. The vector may not 461-- be empty but this is not checked. 462unsafeTail :: Vector v a => v a -> v a 463{-# INLINE_FUSED unsafeTail #-} 464unsafeTail v = unsafeSlice 1 (length v - 1) v 465 466-- | /O(1)/ Yield the first @n@ elements without copying. The vector must 467-- contain at least @n@ elements but this is not checked. 468unsafeTake :: Vector v a => Int -> v a -> v a 469{-# INLINE unsafeTake #-} 470unsafeTake n v = unsafeSlice 0 n v 471 472-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector 473-- must contain at least @n@ elements but this is not checked. 474unsafeDrop :: Vector v a => Int -> v a -> v a 475{-# INLINE unsafeDrop #-} 476unsafeDrop n v = unsafeSlice n (length v - n) v 477 478 479-- Turned off due to: https://github.com/haskell/vector/issues/257 480-- "slice/new [Vector]" forall i n p. 481-- slice i n (new p) = new (New.slice i n p) 482 483{-# RULES 484 485"init/new [Vector]" forall p. 486 init (new p) = new (New.init p) 487 488"tail/new [Vector]" forall p. 489 tail (new p) = new (New.tail p) 490 491"take/new [Vector]" forall n p. 492 take n (new p) = new (New.take n p) 493 494"drop/new [Vector]" forall n p. 495 drop n (new p) = new (New.drop n p) 496 497"unsafeSlice/new [Vector]" forall i n p. 498 unsafeSlice i n (new p) = new (New.unsafeSlice i n p) 499 500"unsafeInit/new [Vector]" forall p. 501 unsafeInit (new p) = new (New.unsafeInit p) 502 503"unsafeTail/new [Vector]" forall p. 504 unsafeTail (new p) = new (New.unsafeTail p) #-} 505 506 507 508-- Initialisation 509-- -------------- 510 511-- | /O(1)/ Empty vector 512empty :: Vector v a => v a 513{-# INLINE empty #-} 514empty = unstream Bundle.empty 515 516-- | /O(1)/ Vector with exactly one element 517singleton :: forall v a. Vector v a => a -> v a 518{-# INLINE singleton #-} 519singleton x = elemseq (undefined :: v a) x 520 $ unstream (Bundle.singleton x) 521 522-- | /O(n)/ Vector of the given length with the same value in each position 523replicate :: forall v a. Vector v a => Int -> a -> v a 524{-# INLINE replicate #-} 525replicate n x = elemseq (undefined :: v a) x 526 $ unstream 527 $ Bundle.replicate n x 528 529-- | /O(n)/ Construct a vector of the given length by applying the function to 530-- each index 531generate :: Vector v a => Int -> (Int -> a) -> v a 532{-# INLINE generate #-} 533generate n f = unstream (Bundle.generate n f) 534 535-- | /O(n)/ Apply function n times to value. Zeroth element is original value. 536iterateN :: Vector v a => Int -> (a -> a) -> a -> v a 537{-# INLINE iterateN #-} 538iterateN n f x = unstream (Bundle.iterateN n f x) 539 540-- Unfolding 541-- --------- 542 543-- | /O(n)/ Construct a vector by repeatedly applying the generator function 544-- to a seed. The generator function yields 'Just' the next element and the 545-- new seed or 'Nothing' if there are no more elements. 546-- 547-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10 548-- > = <10,9,8,7,6,5,4,3,2,1> 549unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a 550{-# INLINE unfoldr #-} 551unfoldr f = unstream . Bundle.unfoldr f 552 553-- | /O(n)/ Construct a vector with at most @n@ elements by repeatedly applying 554-- the generator function to a seed. The generator function yields 'Just' the 555-- next element and the new seed or 'Nothing' if there are no more elements. 556-- 557-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8> 558unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a 559{-# INLINE unfoldrN #-} 560unfoldrN n f = unstream . Bundle.unfoldrN n f 561 562-- | /O(n)/ Construct a vector by repeatedly applying the monadic 563-- generator function to a seed. The generator function yields 'Just' 564-- the next element and the new seed or 'Nothing' if there are no more 565-- elements. 566unfoldrM :: (Monad m, Vector v a) => (b -> m (Maybe (a, b))) -> b -> m (v a) 567{-# INLINE unfoldrM #-} 568unfoldrM f = unstreamM . MBundle.unfoldrM f 569 570-- | /O(n)/ Construct a vector by repeatedly applying the monadic 571-- generator function to a seed. The generator function yields 'Just' 572-- the next element and the new seed or 'Nothing' if there are no more 573-- elements. 574unfoldrNM :: (Monad m, Vector v a) => Int -> (b -> m (Maybe (a, b))) -> b -> m (v a) 575{-# INLINE unfoldrNM #-} 576unfoldrNM n f = unstreamM . MBundle.unfoldrNM n f 577 578-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the 579-- generator function to the already constructed part of the vector. 580-- 581-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in <a,b,c> 582-- 583constructN :: forall v a. Vector v a => Int -> (v a -> a) -> v a 584{-# INLINE constructN #-} 585-- NOTE: We *CANNOT* wrap this in New and then fuse because the elements 586-- might contain references to the immutable vector! 587constructN !n f = runST ( 588 do 589 v <- M.new n 590 v' <- unsafeFreeze v 591 fill v' 0 592 ) 593 where 594 fill :: forall s. v a -> Int -> ST s (v a) 595 fill !v i | i < n = let x = f (unsafeTake i v) 596 in 597 elemseq v x $ 598 do 599 v' <- unsafeThaw v 600 M.unsafeWrite v' i x 601 v'' <- unsafeFreeze v' 602 fill v'' (i+1) 603 604 fill v _ = return v 605 606-- | /O(n)/ Construct a vector with @n@ elements from right to left by 607-- repeatedly applying the generator function to the already constructed part 608-- of the vector. 609-- 610-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in <c,b,a> 611-- 612constructrN :: forall v a. Vector v a => Int -> (v a -> a) -> v a 613{-# INLINE constructrN #-} 614-- NOTE: We *CANNOT* wrap this in New and then fuse because the elements 615-- might contain references to the immutable vector! 616constructrN !n f = runST ( 617 do 618 v <- n `seq` M.new n 619 v' <- unsafeFreeze v 620 fill v' 0 621 ) 622 where 623 fill :: forall s. v a -> Int -> ST s (v a) 624 fill !v i | i < n = let x = f (unsafeSlice (n-i) i v) 625 in 626 elemseq v x $ 627 do 628 v' <- unsafeThaw v 629 M.unsafeWrite v' (n-i-1) x 630 v'' <- unsafeFreeze v' 631 fill v'' (i+1) 632 633 fill v _ = return v 634 635 636-- Enumeration 637-- ----------- 638 639-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@ 640-- etc. This operation is usually more efficient than 'enumFromTo'. 641-- 642-- > enumFromN 5 3 = <5,6,7> 643enumFromN :: (Vector v a, Num a) => a -> Int -> v a 644{-# INLINE enumFromN #-} 645enumFromN x n = enumFromStepN x 1 n 646 647-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@, 648-- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'. 649-- 650-- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4> 651enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a 652{-# INLINE enumFromStepN #-} 653enumFromStepN x y n = elemseq (undefined :: v a) x 654 $ elemseq (undefined :: v a) y 655 $ unstream 656 $ Bundle.enumFromStepN x y n 657 658-- | /O(n)/ Enumerate values from @x@ to @y@. 659-- 660-- /WARNING:/ This operation can be very inefficient. If at all possible, use 661-- 'enumFromN' instead. 662enumFromTo :: (Vector v a, Enum a) => a -> a -> v a 663{-# INLINE enumFromTo #-} 664enumFromTo x y = unstream (Bundle.enumFromTo x y) 665 666-- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@. 667-- 668-- /WARNING:/ This operation can be very inefficient. If at all possible, use 669-- 'enumFromStepN' instead. 670enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a 671{-# INLINE enumFromThenTo #-} 672enumFromThenTo x y z = unstream (Bundle.enumFromThenTo x y z) 673 674-- Concatenation 675-- ------------- 676 677-- | /O(n)/ Prepend an element 678cons :: forall v a. Vector v a => a -> v a -> v a 679{-# INLINE cons #-} 680cons x v = elemseq (undefined :: v a) x 681 $ unstream 682 $ Bundle.cons x 683 $ stream v 684 685-- | /O(n)/ Append an element 686snoc :: forall v a. Vector v a => v a -> a -> v a 687{-# INLINE snoc #-} 688snoc v x = elemseq (undefined :: v a) x 689 $ unstream 690 $ Bundle.snoc (stream v) x 691 692infixr 5 ++ 693-- | /O(m+n)/ Concatenate two vectors 694(++) :: Vector v a => v a -> v a -> v a 695{-# INLINE (++) #-} 696v ++ w = unstream (stream v Bundle.++ stream w) 697 698-- | /O(n)/ Concatenate all vectors in the list 699concat :: Vector v a => [v a] -> v a 700{-# INLINE concat #-} 701concat = unstream . Bundle.fromVectors 702{- 703concat vs = unstream (Bundle.flatten mk step (Exact n) (Bundle.fromList vs)) 704 where 705 n = List.foldl' (\k v -> k + length v) 0 vs 706 707 {-# INLINE_INNER step #-} 708 step (v,i,k) 709 | i < k = case unsafeIndexM v i of 710 Box x -> Bundle.Yield x (v,i+1,k) 711 | otherwise = Bundle.Done 712 713 {-# INLINE mk #-} 714 mk v = let k = length v 715 in 716 k `seq` (v,0,k) 717-} 718 719-- | /O(n)/ Concatenate all vectors in the non-empty list 720concatNE :: Vector v a => NonEmpty.NonEmpty (v a) -> v a 721concatNE = concat . NonEmpty.toList 722 723-- Monadic initialisation 724-- ---------------------- 725 726-- | /O(n)/ Execute the monadic action the given number of times and store the 727-- results in a vector. 728replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a) 729{-# INLINE replicateM #-} 730replicateM n m = unstreamM (MBundle.replicateM n m) 731 732-- | /O(n)/ Construct a vector of the given length by applying the monadic 733-- action to each index 734generateM :: (Monad m, Vector v a) => Int -> (Int -> m a) -> m (v a) 735{-# INLINE generateM #-} 736generateM n f = unstreamM (MBundle.generateM n f) 737 738-- | /O(n)/ Apply monadic function n times to value. Zeroth element is original value. 739iterateNM :: (Monad m, Vector v a) => Int -> (a -> m a) -> a -> m (v a) 740{-# INLINE iterateNM #-} 741iterateNM n f x = unstreamM (MBundle.iterateNM n f x) 742 743-- | Execute the monadic action and freeze the resulting vector. 744-- 745-- @ 746-- create (do { v \<- 'M.new' 2; 'M.write' v 0 \'a\'; 'M.write' v 1 \'b\'; return v }) = \<'a','b'\> 747-- @ 748create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a 749{-# INLINE create #-} 750create p = new (New.create p) 751 752-- | Execute the monadic action and freeze the resulting vectors. 753createT 754 :: (T.Traversable f, Vector v a) 755 => (forall s. ST s (f (Mutable v s a))) -> f (v a) 756{-# INLINE createT #-} 757createT p = runST (p >>= T.mapM unsafeFreeze) 758 759-- Restricting memory usage 760-- ------------------------ 761 762-- | /O(n)/ Yield the argument but force it not to retain any extra memory, 763-- possibly by copying it. 764-- 765-- This is especially useful when dealing with slices. For example: 766-- 767-- > force (slice 0 2 <huge vector>) 768-- 769-- Here, the slice retains a reference to the huge vector. Forcing it creates 770-- a copy of just the elements that belong to the slice and allows the huge 771-- vector to be garbage collected. 772force :: Vector v a => v a -> v a 773-- FIXME: we probably ought to inline this later as the rules still might fire 774-- otherwise 775{-# INLINE_FUSED force #-} 776force v = new (clone v) 777 778-- Bulk updates 779-- ------------ 780 781-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector 782-- element at position @i@ by @a@. 783-- 784-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7> 785-- 786(//) :: Vector v a => v a -- ^ initial vector (of length @m@) 787 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 788 -> v a 789{-# INLINE (//) #-} 790v // us = update_stream v (Bundle.fromList us) 791 792-- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs, 793-- replace the vector element at position @i@ by @a@. 794-- 795-- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7> 796-- 797update :: (Vector v a, Vector v (Int, a)) 798 => v a -- ^ initial vector (of length @m@) 799 -> v (Int, a) -- ^ vector of index/value pairs (of length @n@) 800 -> v a 801{-# INLINE update #-} 802update v w = update_stream v (stream w) 803 804-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the 805-- corresponding value @a@ from the value vector, replace the element of the 806-- initial vector at position @i@ by @a@. 807-- 808-- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7> 809-- 810-- This function is useful for instances of 'Vector' that cannot store pairs. 811-- Otherwise, 'update' is probably more convenient. 812-- 813-- @ 814-- update_ xs is ys = 'update' xs ('zip' is ys) 815-- @ 816update_ :: (Vector v a, Vector v Int) 817 => v a -- ^ initial vector (of length @m@) 818 -> v Int -- ^ index vector (of length @n1@) 819 -> v a -- ^ value vector (of length @n2@) 820 -> v a 821{-# INLINE update_ #-} 822update_ v is w = update_stream v (Bundle.zipWith (,) (stream is) (stream w)) 823 824update_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a 825{-# INLINE update_stream #-} 826update_stream = modifyWithBundle M.update 827 828-- | Same as ('//') but without bounds checking. 829unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a 830{-# INLINE unsafeUpd #-} 831unsafeUpd v us = unsafeUpdate_stream v (Bundle.fromList us) 832 833-- | Same as 'update' but without bounds checking. 834unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a 835{-# INLINE unsafeUpdate #-} 836unsafeUpdate v w = unsafeUpdate_stream v (stream w) 837 838-- | Same as 'update_' but without bounds checking. 839unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a 840{-# INLINE unsafeUpdate_ #-} 841unsafeUpdate_ v is w 842 = unsafeUpdate_stream v (Bundle.zipWith (,) (stream is) (stream w)) 843 844unsafeUpdate_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a 845{-# INLINE unsafeUpdate_stream #-} 846unsafeUpdate_stream = modifyWithBundle M.unsafeUpdate 847 848-- Accumulations 849-- ------------- 850 851-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element 852-- @a@ at position @i@ by @f a b@. 853-- 854-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4> 855accum :: Vector v a 856 => (a -> b -> a) -- ^ accumulating function @f@ 857 -> v a -- ^ initial vector (of length @m@) 858 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@) 859 -> v a 860{-# INLINE accum #-} 861accum f v us = accum_stream f v (Bundle.fromList us) 862 863-- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector 864-- element @a@ at position @i@ by @f a b@. 865-- 866-- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4> 867accumulate :: (Vector v a, Vector v (Int, b)) 868 => (a -> b -> a) -- ^ accumulating function @f@ 869 -> v a -- ^ initial vector (of length @m@) 870 -> v (Int,b) -- ^ vector of index/value pairs (of length @n@) 871 -> v a 872{-# INLINE accumulate #-} 873accumulate f v us = accum_stream f v (stream us) 874 875-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the 876-- corresponding value @b@ from the the value vector, 877-- replace the element of the initial vector at 878-- position @i@ by @f a b@. 879-- 880-- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4> 881-- 882-- This function is useful for instances of 'Vector' that cannot store pairs. 883-- Otherwise, 'accumulate' is probably more convenient: 884-- 885-- @ 886-- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs) 887-- @ 888accumulate_ :: (Vector v a, Vector v Int, Vector v b) 889 => (a -> b -> a) -- ^ accumulating function @f@ 890 -> v a -- ^ initial vector (of length @m@) 891 -> v Int -- ^ index vector (of length @n1@) 892 -> v b -- ^ value vector (of length @n2@) 893 -> v a 894{-# INLINE accumulate_ #-} 895accumulate_ f v is xs = accum_stream f v (Bundle.zipWith (,) (stream is) 896 (stream xs)) 897 898 899accum_stream :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a 900{-# INLINE accum_stream #-} 901accum_stream f = modifyWithBundle (M.accum f) 902 903-- | Same as 'accum' but without bounds checking. 904unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a 905{-# INLINE unsafeAccum #-} 906unsafeAccum f v us = unsafeAccum_stream f v (Bundle.fromList us) 907 908-- | Same as 'accumulate' but without bounds checking. 909unsafeAccumulate :: (Vector v a, Vector v (Int, b)) 910 => (a -> b -> a) -> v a -> v (Int,b) -> v a 911{-# INLINE unsafeAccumulate #-} 912unsafeAccumulate f v us = unsafeAccum_stream f v (stream us) 913 914-- | Same as 'accumulate_' but without bounds checking. 915unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b) 916 => (a -> b -> a) -> v a -> v Int -> v b -> v a 917{-# INLINE unsafeAccumulate_ #-} 918unsafeAccumulate_ f v is xs 919 = unsafeAccum_stream f v (Bundle.zipWith (,) (stream is) (stream xs)) 920 921unsafeAccum_stream 922 :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a 923{-# INLINE unsafeAccum_stream #-} 924unsafeAccum_stream f = modifyWithBundle (M.unsafeAccum f) 925 926-- Permutations 927-- ------------ 928 929-- | /O(n)/ Reverse a vector 930reverse :: (Vector v a) => v a -> v a 931{-# INLINE reverse #-} 932-- FIXME: make this fuse better, add support for recycling 933reverse = unstream . streamR 934 935-- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the 936-- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is 937-- often much more efficient. 938-- 939-- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a> 940backpermute :: (Vector v a, Vector v Int) 941 => v a -- ^ @xs@ value vector 942 -> v Int -- ^ @is@ index vector (of length @n@) 943 -> v a 944{-# INLINE backpermute #-} 945-- This somewhat non-intuitive definition ensures that the resulting vector 946-- does not retain references to the original one even if it is lazy in its 947-- elements. This would not be the case if we simply used map (v!) 948backpermute v is = seq v 949 $ seq n 950 $ unstream 951 $ Bundle.unbox 952 $ Bundle.map index 953 $ stream is 954 where 955 n = length v 956 957 {-# INLINE index #-} 958 -- NOTE: we do it this way to avoid triggering LiberateCase on n in 959 -- polymorphic code 960 index i = BOUNDS_CHECK(checkIndex) "backpermute" i n 961 $ basicUnsafeIndexM v i 962 963-- | Same as 'backpermute' but without bounds checking. 964unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a 965{-# INLINE unsafeBackpermute #-} 966unsafeBackpermute v is = seq v 967 $ seq n 968 $ unstream 969 $ Bundle.unbox 970 $ Bundle.map index 971 $ stream is 972 where 973 n = length v 974 975 {-# INLINE index #-} 976 -- NOTE: we do it this way to avoid triggering LiberateCase on n in 977 -- polymorphic code 978 index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n 979 $ basicUnsafeIndexM v i 980 981-- Safe destructive updates 982-- ------------------------ 983 984-- | Apply a destructive operation to a vector. The operation will be 985-- performed in place if it is safe to do so and will modify a copy of the 986-- vector otherwise. 987-- 988-- @ 989-- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\> 990-- @ 991modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a 992{-# INLINE modify #-} 993modify p = new . New.modify p . clone 994 995-- We have to make sure that this is strict in the stream but we can't seq on 996-- it while fusion is happening. Hence this ugliness. 997modifyWithBundle :: Vector v a 998 => (forall s. Mutable v s a -> Bundle u b -> ST s ()) 999 -> v a -> Bundle u b -> v a 1000{-# INLINE modifyWithBundle #-} 1001modifyWithBundle p v s = new (New.modifyWithBundle p (clone v) s) 1002 1003-- Indexing 1004-- -------- 1005 1006-- | /O(n)/ Pair each element in a vector with its index 1007indexed :: (Vector v a, Vector v (Int,a)) => v a -> v (Int,a) 1008{-# INLINE indexed #-} 1009indexed = unstream . Bundle.indexed . stream 1010 1011-- Mapping 1012-- ------- 1013 1014-- | /O(n)/ Map a function over a vector 1015map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b 1016{-# INLINE map #-} 1017map f = unstream . inplace (S.map f) id . stream 1018 1019-- | /O(n)/ Apply a function to every element of a vector and its index 1020imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b 1021{-# INLINE imap #-} 1022imap f = unstream . inplace (S.map (uncurry f) . S.indexed) id 1023 . stream 1024 1025-- | Map a function over a vector and concatenate the results. 1026concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b 1027{-# INLINE concatMap #-} 1028-- NOTE: We can't fuse concatMap anyway so don't pretend we do. 1029-- This seems to be slightly slower 1030-- concatMap f = concat . Bundle.toList . Bundle.map f . stream 1031 1032-- Slowest 1033-- concatMap f = unstream . Bundle.concatMap (stream . f) . stream 1034 1035-- Used to be fastest 1036{- 1037concatMap f = unstream 1038 . Bundle.flatten mk step Unknown 1039 . stream 1040 where 1041 {-# INLINE_INNER step #-} 1042 step (v,i,k) 1043 | i < k = case unsafeIndexM v i of 1044 Box x -> Bundle.Yield x (v,i+1,k) 1045 | otherwise = Bundle.Done 1046 1047 {-# INLINE mk #-} 1048 mk x = let v = f x 1049 k = length v 1050 in 1051 k `seq` (v,0,k) 1052-} 1053 1054-- This seems to be fastest now 1055concatMap f = unstream 1056 . Bundle.concatVectors 1057 . Bundle.map f 1058 . stream 1059 1060-- Monadic mapping 1061-- --------------- 1062 1063-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a 1064-- vector of results 1065mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b) 1066{-# INLINE mapM #-} 1067mapM f = unstreamM . Bundle.mapM f . stream 1068 1069-- | /O(n)/ Apply the monadic action to every element of a vector and its 1070-- index, yielding a vector of results 1071imapM :: (Monad m, Vector v a, Vector v b) 1072 => (Int -> a -> m b) -> v a -> m (v b) 1073imapM f = unstreamM . Bundle.mapM (uncurry f) . Bundle.indexed . stream 1074 1075-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the 1076-- results 1077mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m () 1078{-# INLINE mapM_ #-} 1079mapM_ f = Bundle.mapM_ f . stream 1080 1081-- | /O(n)/ Apply the monadic action to every element of a vector and its 1082-- index, ignoring the results 1083imapM_ :: (Monad m, Vector v a) => (Int -> a -> m b) -> v a -> m () 1084{-# INLINE imapM_ #-} 1085imapM_ f = Bundle.mapM_ (uncurry f) . Bundle.indexed . stream 1086 1087-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a 1088-- vector of results. Equivalent to @flip 'mapM'@. 1089forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b) 1090{-# INLINE forM #-} 1091forM as f = mapM f as 1092 1093-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the 1094-- results. Equivalent to @flip 'mapM_'@. 1095forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m () 1096{-# INLINE forM_ #-} 1097forM_ as f = mapM_ f as 1098 1099-- Zipping 1100-- ------- 1101 1102-- | /O(min(m,n))/ Zip two vectors with the given function. 1103zipWith :: (Vector v a, Vector v b, Vector v c) 1104 => (a -> b -> c) -> v a -> v b -> v c 1105{-# INLINE zipWith #-} 1106zipWith f = \xs ys -> unstream (Bundle.zipWith f (stream xs) (stream ys)) 1107 1108-- | Zip three vectors with the given function. 1109zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d) 1110 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d 1111{-# INLINE zipWith3 #-} 1112zipWith3 f = \as bs cs -> unstream (Bundle.zipWith3 f (stream as) 1113 (stream bs) 1114 (stream cs)) 1115 1116zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e) 1117 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e 1118{-# INLINE zipWith4 #-} 1119zipWith4 f = \as bs cs ds -> 1120 unstream (Bundle.zipWith4 f (stream as) 1121 (stream bs) 1122 (stream cs) 1123 (stream ds)) 1124 1125zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1126 Vector v f) 1127 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e 1128 -> v f 1129{-# INLINE zipWith5 #-} 1130zipWith5 f = \as bs cs ds es -> 1131 unstream (Bundle.zipWith5 f (stream as) 1132 (stream bs) 1133 (stream cs) 1134 (stream ds) 1135 (stream es)) 1136 1137zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1138 Vector v f, Vector v g) 1139 => (a -> b -> c -> d -> e -> f -> g) 1140 -> v a -> v b -> v c -> v d -> v e -> v f -> v g 1141{-# INLINE zipWith6 #-} 1142zipWith6 f = \as bs cs ds es fs -> 1143 unstream (Bundle.zipWith6 f (stream as) 1144 (stream bs) 1145 (stream cs) 1146 (stream ds) 1147 (stream es) 1148 (stream fs)) 1149 1150-- | /O(min(m,n))/ Zip two vectors with a function that also takes the 1151-- elements' indices. 1152izipWith :: (Vector v a, Vector v b, Vector v c) 1153 => (Int -> a -> b -> c) -> v a -> v b -> v c 1154{-# INLINE izipWith #-} 1155izipWith f = \xs ys -> 1156 unstream (Bundle.zipWith (uncurry f) (Bundle.indexed (stream xs)) 1157 (stream ys)) 1158 1159izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d) 1160 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d 1161{-# INLINE izipWith3 #-} 1162izipWith3 f = \as bs cs -> 1163 unstream (Bundle.zipWith3 (uncurry f) (Bundle.indexed (stream as)) 1164 (stream bs) 1165 (stream cs)) 1166 1167izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e) 1168 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e 1169{-# INLINE izipWith4 #-} 1170izipWith4 f = \as bs cs ds -> 1171 unstream (Bundle.zipWith4 (uncurry f) (Bundle.indexed (stream as)) 1172 (stream bs) 1173 (stream cs) 1174 (stream ds)) 1175 1176izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1177 Vector v f) 1178 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d 1179 -> v e -> v f 1180{-# INLINE izipWith5 #-} 1181izipWith5 f = \as bs cs ds es -> 1182 unstream (Bundle.zipWith5 (uncurry f) (Bundle.indexed (stream as)) 1183 (stream bs) 1184 (stream cs) 1185 (stream ds) 1186 (stream es)) 1187 1188izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1189 Vector v f, Vector v g) 1190 => (Int -> a -> b -> c -> d -> e -> f -> g) 1191 -> v a -> v b -> v c -> v d -> v e -> v f -> v g 1192{-# INLINE izipWith6 #-} 1193izipWith6 f = \as bs cs ds es fs -> 1194 unstream (Bundle.zipWith6 (uncurry f) (Bundle.indexed (stream as)) 1195 (stream bs) 1196 (stream cs) 1197 (stream ds) 1198 (stream es) 1199 (stream fs)) 1200 1201-- | /O(min(m,n))/ Zip two vectors 1202zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b) 1203{-# INLINE zip #-} 1204zip = zipWith (,) 1205 1206zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c)) 1207 => v a -> v b -> v c -> v (a, b, c) 1208{-# INLINE zip3 #-} 1209zip3 = zipWith3 (,,) 1210 1211zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d)) 1212 => v a -> v b -> v c -> v d -> v (a, b, c, d) 1213{-# INLINE zip4 #-} 1214zip4 = zipWith4 (,,,) 1215 1216zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1217 Vector v (a, b, c, d, e)) 1218 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e) 1219{-# INLINE zip5 #-} 1220zip5 = zipWith5 (,,,,) 1221 1222zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1223 Vector v f, Vector v (a, b, c, d, e, f)) 1224 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f) 1225{-# INLINE zip6 #-} 1226zip6 = zipWith6 (,,,,,) 1227 1228-- Monadic zipping 1229-- --------------- 1230 1231-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a 1232-- vector of results 1233zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c) 1234 => (a -> b -> m c) -> v a -> v b -> m (v c) 1235-- FIXME: specialise for ST and IO? 1236{-# INLINE zipWithM #-} 1237zipWithM f = \as bs -> unstreamM $ Bundle.zipWithM f (stream as) (stream bs) 1238 1239-- | /O(min(m,n))/ Zip the two vectors with a monadic action that also takes 1240-- the element index and yield a vector of results 1241izipWithM :: (Monad m, Vector v a, Vector v b, Vector v c) 1242 => (Int -> a -> b -> m c) -> v a -> v b -> m (v c) 1243{-# INLINE izipWithM #-} 1244izipWithM m as bs = unstreamM . Bundle.zipWithM (uncurry m) 1245 (Bundle.indexed (stream as)) 1246 $ stream bs 1247 1248-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the 1249-- results 1250zipWithM_ :: (Monad m, Vector v a, Vector v b) 1251 => (a -> b -> m c) -> v a -> v b -> m () 1252{-# INLINE zipWithM_ #-} 1253zipWithM_ f = \as bs -> Bundle.zipWithM_ f (stream as) (stream bs) 1254 1255-- | /O(min(m,n))/ Zip the two vectors with a monadic action that also takes 1256-- the element index and ignore the results 1257izipWithM_ :: (Monad m, Vector v a, Vector v b) 1258 => (Int -> a -> b -> m c) -> v a -> v b -> m () 1259{-# INLINE izipWithM_ #-} 1260izipWithM_ m as bs = Bundle.zipWithM_ (uncurry m) 1261 (Bundle.indexed (stream as)) 1262 $ stream bs 1263 1264-- Unzipping 1265-- --------- 1266 1267-- | /O(min(m,n))/ Unzip a vector of pairs. 1268unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b) 1269{-# INLINE unzip #-} 1270unzip xs = (map fst xs, map snd xs) 1271 1272unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c)) 1273 => v (a, b, c) -> (v a, v b, v c) 1274{-# INLINE unzip3 #-} 1275unzip3 xs = (map (\(a, _, _) -> a) xs, 1276 map (\(_, b, _) -> b) xs, 1277 map (\(_, _, c) -> c) xs) 1278 1279unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, 1280 Vector v (a, b, c, d)) 1281 => v (a, b, c, d) -> (v a, v b, v c, v d) 1282{-# INLINE unzip4 #-} 1283unzip4 xs = (map (\(a, _, _, _) -> a) xs, 1284 map (\(_, b, _, _) -> b) xs, 1285 map (\(_, _, c, _) -> c) xs, 1286 map (\(_, _, _, d) -> d) xs) 1287 1288unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1289 Vector v (a, b, c, d, e)) 1290 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e) 1291{-# INLINE unzip5 #-} 1292unzip5 xs = (map (\(a, _, _, _, _) -> a) xs, 1293 map (\(_, b, _, _, _) -> b) xs, 1294 map (\(_, _, c, _, _) -> c) xs, 1295 map (\(_, _, _, d, _) -> d) xs, 1296 map (\(_, _, _, _, e) -> e) xs) 1297 1298unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e, 1299 Vector v f, Vector v (a, b, c, d, e, f)) 1300 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f) 1301{-# INLINE unzip6 #-} 1302unzip6 xs = (map (\(a, _, _, _, _, _) -> a) xs, 1303 map (\(_, b, _, _, _, _) -> b) xs, 1304 map (\(_, _, c, _, _, _) -> c) xs, 1305 map (\(_, _, _, d, _, _) -> d) xs, 1306 map (\(_, _, _, _, e, _) -> e) xs, 1307 map (\(_, _, _, _, _, f) -> f) xs) 1308 1309-- Filtering 1310-- --------- 1311 1312-- | /O(n)/ Drop elements that do not satisfy the predicate 1313filter :: Vector v a => (a -> Bool) -> v a -> v a 1314{-# INLINE filter #-} 1315filter f = unstream . inplace (S.filter f) toMax . stream 1316 1317-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to 1318-- values and their indices 1319ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a 1320{-# INLINE ifilter #-} 1321ifilter f = unstream 1322 . inplace (S.map snd . S.filter (uncurry f) . S.indexed) toMax 1323 . stream 1324 1325-- | /O(n)/ Drop repeated adjacent elements. 1326uniq :: (Vector v a, Eq a) => v a -> v a 1327{-# INLINE uniq #-} 1328uniq = unstream . inplace S.uniq toMax . stream 1329 1330-- | /O(n)/ Drop elements when predicate returns Nothing 1331mapMaybe :: (Vector v a, Vector v b) => (a -> Maybe b) -> v a -> v b 1332{-# INLINE mapMaybe #-} 1333mapMaybe f = unstream . inplace (S.mapMaybe f) toMax . stream 1334 1335-- | /O(n)/ Drop elements when predicate, applied to index and value, returns Nothing 1336imapMaybe :: (Vector v a, Vector v b) => (Int -> a -> Maybe b) -> v a -> v b 1337{-# INLINE imapMaybe #-} 1338imapMaybe f = unstream 1339 . inplace (S.mapMaybe (uncurry f) . S.indexed) toMax 1340 . stream 1341 1342 1343-- | /O(n)/ Drop elements that do not satisfy the monadic predicate 1344filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a) 1345{-# INLINE filterM #-} 1346filterM f = unstreamM . Bundle.filterM f . stream 1347 1348-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate 1349-- without copying. 1350takeWhile :: Vector v a => (a -> Bool) -> v a -> v a 1351{-# INLINE takeWhile #-} 1352takeWhile f = unstream . Bundle.takeWhile f . stream 1353 1354-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate 1355-- without copying. 1356dropWhile :: Vector v a => (a -> Bool) -> v a -> v a 1357{-# INLINE dropWhile #-} 1358dropWhile f = unstream . Bundle.dropWhile f . stream 1359 1360-- Parititioning 1361-- ------------- 1362 1363-- | /O(n)/ Split the vector in two parts, the first one containing those 1364-- elements that satisfy the predicate and the second one those that don't. The 1365-- relative order of the elements is preserved at the cost of a sometimes 1366-- reduced performance compared to 'unstablePartition'. 1367partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a) 1368{-# INLINE partition #-} 1369partition f = partition_stream f . stream 1370 1371-- FIXME: Make this inplace-fusible (look at how stable_partition is 1372-- implemented in C++) 1373 1374partition_stream :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a) 1375{-# INLINE_FUSED partition_stream #-} 1376partition_stream f s = s `seq` runST ( 1377 do 1378 (mv1,mv2) <- M.partitionBundle f s 1379 v1 <- unsafeFreeze mv1 1380 v2 <- unsafeFreeze mv2 1381 return (v1,v2)) 1382 1383partitionWith :: (Vector v a, Vector v b, Vector v c) => (a -> Either b c) -> v a -> (v b, v c) 1384{-# INLINE partitionWith #-} 1385partitionWith f = partition_with_stream f . stream 1386 1387partition_with_stream :: (Vector v a, Vector v b, Vector v c) => (a -> Either b c) -> Bundle u a -> (v b, v c) 1388{-# INLINE_FUSED partition_with_stream #-} 1389partition_with_stream f s = s `seq` runST ( 1390 do 1391 (mv1,mv2) <- M.partitionWithBundle f s 1392 v1 <- unsafeFreeze mv1 1393 v2 <- unsafeFreeze mv2 1394 return (v1,v2)) 1395 1396-- | /O(n)/ Split the vector in two parts, the first one containing those 1397-- elements that satisfy the predicate and the second one those that don't. 1398-- The order of the elements is not preserved but the operation is often 1399-- faster than 'partition'. 1400unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a) 1401{-# INLINE unstablePartition #-} 1402unstablePartition f = unstablePartition_stream f . stream 1403 1404unstablePartition_stream 1405 :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a) 1406{-# INLINE_FUSED unstablePartition_stream #-} 1407unstablePartition_stream f s = s `seq` runST ( 1408 do 1409 (mv1,mv2) <- M.unstablePartitionBundle f s 1410 v1 <- unsafeFreeze mv1 1411 v2 <- unsafeFreeze mv2 1412 return (v1,v2)) 1413 1414unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a) 1415{-# INLINE_FUSED unstablePartition_new #-} 1416unstablePartition_new f (New.New p) = runST ( 1417 do 1418 mv <- p 1419 i <- M.unstablePartition f mv 1420 v <- unsafeFreeze mv 1421 return (unsafeTake i v, unsafeDrop i v)) 1422 1423{-# RULES 1424 1425"unstablePartition" forall f p. 1426 unstablePartition_stream f (stream (new p)) 1427 = unstablePartition_new f p #-} 1428 1429 1430 1431 1432-- FIXME: make span and break fusible 1433 1434-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy 1435-- the predicate and the rest without copying. 1436span :: Vector v a => (a -> Bool) -> v a -> (v a, v a) 1437{-# INLINE span #-} 1438span f = break (not . f) 1439 1440-- | /O(n)/ Split the vector into the longest prefix of elements that do not 1441-- satisfy the predicate and the rest without copying. 1442break :: Vector v a => (a -> Bool) -> v a -> (v a, v a) 1443{-# INLINE break #-} 1444break f xs = case findIndex f xs of 1445 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs) 1446 Nothing -> (xs, empty) 1447 1448 1449-- Searching 1450-- --------- 1451 1452infix 4 `elem` 1453-- | /O(n)/ Check if the vector contains an element 1454elem :: (Vector v a, Eq a) => a -> v a -> Bool 1455{-# INLINE elem #-} 1456elem x = Bundle.elem x . stream 1457 1458infix 4 `notElem` 1459-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem') 1460notElem :: (Vector v a, Eq a) => a -> v a -> Bool 1461{-# INLINE notElem #-} 1462notElem x = Bundle.notElem x . stream 1463 1464-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing' 1465-- if no such element exists. 1466find :: Vector v a => (a -> Bool) -> v a -> Maybe a 1467{-# INLINE find #-} 1468find f = Bundle.find f . stream 1469 1470-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate 1471-- or 'Nothing' if no such element exists. 1472findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int 1473{-# INLINE findIndex #-} 1474findIndex f = Bundle.findIndex f . stream 1475 1476-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending 1477-- order. 1478findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int 1479{-# INLINE findIndices #-} 1480findIndices f = unstream 1481 . inplace (S.map fst . S.filter (f . snd) . S.indexed) toMax 1482 . stream 1483 1484-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or 1485-- 'Nothing' if the vector does not contain the element. This is a specialised 1486-- version of 'findIndex'. 1487elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int 1488{-# INLINE elemIndex #-} 1489elemIndex x = findIndex (x==) 1490 1491-- | /O(n)/ Yield the indices of all occurences of the given element in 1492-- ascending order. This is a specialised version of 'findIndices'. 1493elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int 1494{-# INLINE elemIndices #-} 1495elemIndices x = findIndices (x==) 1496 1497-- Folding 1498-- ------- 1499 1500-- | /O(n)/ Left fold 1501foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a 1502{-# INLINE foldl #-} 1503foldl f z = Bundle.foldl f z . stream 1504 1505-- | /O(n)/ Left fold on non-empty vectors 1506foldl1 :: Vector v a => (a -> a -> a) -> v a -> a 1507{-# INLINE foldl1 #-} 1508foldl1 f = Bundle.foldl1 f . stream 1509 1510-- | /O(n)/ Left fold with strict accumulator 1511foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a 1512{-# INLINE foldl' #-} 1513foldl' f z = Bundle.foldl' f z . stream 1514 1515-- | /O(n)/ Left fold on non-empty vectors with strict accumulator 1516foldl1' :: Vector v a => (a -> a -> a) -> v a -> a 1517{-# INLINE foldl1' #-} 1518foldl1' f = Bundle.foldl1' f . stream 1519 1520-- | /O(n)/ Right fold 1521foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b 1522{-# INLINE foldr #-} 1523foldr f z = Bundle.foldr f z . stream 1524 1525-- | /O(n)/ Right fold on non-empty vectors 1526foldr1 :: Vector v a => (a -> a -> a) -> v a -> a 1527{-# INLINE foldr1 #-} 1528foldr1 f = Bundle.foldr1 f . stream 1529 1530-- | /O(n)/ Right fold with a strict accumulator 1531foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b 1532{-# INLINE foldr' #-} 1533foldr' f z = Bundle.foldl' (flip f) z . streamR 1534 1535-- | /O(n)/ Right fold on non-empty vectors with strict accumulator 1536foldr1' :: Vector v a => (a -> a -> a) -> v a -> a 1537{-# INLINE foldr1' #-} 1538foldr1' f = Bundle.foldl1' (flip f) . streamR 1539 1540-- | /O(n)/ Left fold (function applied to each element and its index) 1541ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a 1542{-# INLINE ifoldl #-} 1543ifoldl f z = Bundle.foldl (uncurry . f) z . Bundle.indexed . stream 1544 1545-- | /O(n)/ Left fold with strict accumulator (function applied to each element 1546-- and its index) 1547ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a 1548{-# INLINE ifoldl' #-} 1549ifoldl' f z = Bundle.foldl' (uncurry . f) z . Bundle.indexed . stream 1550 1551-- | /O(n)/ Right fold (function applied to each element and its index) 1552ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b 1553{-# INLINE ifoldr #-} 1554ifoldr f z = Bundle.foldr (uncurry f) z . Bundle.indexed . stream 1555 1556-- | /O(n)/ Right fold with strict accumulator (function applied to each 1557-- element and its index) 1558ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b 1559{-# INLINE ifoldr' #-} 1560ifoldr' f z xs = Bundle.foldl' (flip (uncurry f)) z 1561 $ Bundle.indexedR (length xs) $ streamR xs 1562 1563-- Specialised folds 1564-- ----------------- 1565 1566-- | /O(n)/ Check if all elements satisfy the predicate. 1567all :: Vector v a => (a -> Bool) -> v a -> Bool 1568{-# INLINE all #-} 1569all f = Bundle.and . Bundle.map f . stream 1570 1571-- | /O(n)/ Check if any element satisfies the predicate. 1572any :: Vector v a => (a -> Bool) -> v a -> Bool 1573{-# INLINE any #-} 1574any f = Bundle.or . Bundle.map f . stream 1575 1576-- | /O(n)/ Check if all elements are 'True' 1577and :: Vector v Bool => v Bool -> Bool 1578{-# INLINE and #-} 1579and = Bundle.and . stream 1580 1581-- | /O(n)/ Check if any element is 'True' 1582or :: Vector v Bool => v Bool -> Bool 1583{-# INLINE or #-} 1584or = Bundle.or . stream 1585 1586-- | /O(n)/ Compute the sum of the elements 1587sum :: (Vector v a, Num a) => v a -> a 1588{-# INLINE sum #-} 1589sum = Bundle.foldl' (+) 0 . stream 1590 1591-- | /O(n)/ Compute the produce of the elements 1592product :: (Vector v a, Num a) => v a -> a 1593{-# INLINE product #-} 1594product = Bundle.foldl' (*) 1 . stream 1595 1596-- | /O(n)/ Yield the maximum element of the vector. The vector may not be 1597-- empty. 1598maximum :: (Vector v a, Ord a) => v a -> a 1599{-# INLINE maximum #-} 1600maximum = Bundle.foldl1' max . stream 1601 1602-- | /O(n)/ Yield the maximum element of the vector according to the given 1603-- comparison function. The vector may not be empty. 1604maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a 1605{-# INLINE maximumBy #-} 1606maximumBy cmpr = Bundle.foldl1' maxBy . stream 1607 where 1608 {-# INLINE maxBy #-} 1609 maxBy x y = case cmpr x y of 1610 LT -> y 1611 _ -> x 1612 1613-- | /O(n)/ Yield the minimum element of the vector. The vector may not be 1614-- empty. 1615minimum :: (Vector v a, Ord a) => v a -> a 1616{-# INLINE minimum #-} 1617minimum = Bundle.foldl1' min . stream 1618 1619-- | /O(n)/ Yield the minimum element of the vector according to the given 1620-- comparison function. The vector may not be empty. 1621minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a 1622{-# INLINE minimumBy #-} 1623minimumBy cmpr = Bundle.foldl1' minBy . stream 1624 where 1625 {-# INLINE minBy #-} 1626 minBy x y = case cmpr x y of 1627 GT -> y 1628 _ -> x 1629 1630-- | /O(n)/ Yield the index of the maximum element of the vector. The vector 1631-- may not be empty. 1632maxIndex :: (Vector v a, Ord a) => v a -> Int 1633{-# INLINE maxIndex #-} 1634maxIndex = maxIndexBy compare 1635 1636-- | /O(n)/ Yield the index of the maximum element of the vector according to 1637-- the given comparison function. The vector may not be empty. 1638maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int 1639{-# INLINE maxIndexBy #-} 1640maxIndexBy cmpr = fst . Bundle.foldl1' imax . Bundle.indexed . stream 1641 where 1642 imax (i,x) (j,y) = i `seq` j `seq` 1643 case cmpr x y of 1644 LT -> (j,y) 1645 _ -> (i,x) 1646 1647-- | /O(n)/ Yield the index of the minimum element of the vector. The vector 1648-- may not be empty. 1649minIndex :: (Vector v a, Ord a) => v a -> Int 1650{-# INLINE minIndex #-} 1651minIndex = minIndexBy compare 1652 1653-- | /O(n)/ Yield the index of the minimum element of the vector according to 1654-- the given comparison function. The vector may not be empty. 1655minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int 1656{-# INLINE minIndexBy #-} 1657minIndexBy cmpr = fst . Bundle.foldl1' imin . Bundle.indexed . stream 1658 where 1659 imin (i,x) (j,y) = i `seq` j `seq` 1660 case cmpr x y of 1661 GT -> (j,y) 1662 _ -> (i,x) 1663 1664-- Monadic folds 1665-- ------------- 1666 1667-- | /O(n)/ Monadic fold 1668foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a 1669{-# INLINE foldM #-} 1670foldM m z = Bundle.foldM m z . stream 1671 1672-- | /O(n)/ Monadic fold (action applied to each element and its index) 1673ifoldM :: (Monad m, Vector v b) => (a -> Int -> b -> m a) -> a -> v b -> m a 1674{-# INLINE ifoldM #-} 1675ifoldM m z = Bundle.foldM (uncurry . m) z . Bundle.indexed . stream 1676 1677-- | /O(n)/ Monadic fold over non-empty vectors 1678fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a 1679{-# INLINE fold1M #-} 1680fold1M m = Bundle.fold1M m . stream 1681 1682-- | /O(n)/ Monadic fold with strict accumulator 1683foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a 1684{-# INLINE foldM' #-} 1685foldM' m z = Bundle.foldM' m z . stream 1686 1687-- | /O(n)/ Monadic fold with strict accumulator (action applied to each 1688-- element and its index) 1689ifoldM' :: (Monad m, Vector v b) => (a -> Int -> b -> m a) -> a -> v b -> m a 1690{-# INLINE ifoldM' #-} 1691ifoldM' m z = Bundle.foldM' (uncurry . m) z . Bundle.indexed . stream 1692 1693-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator 1694fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a 1695{-# INLINE fold1M' #-} 1696fold1M' m = Bundle.fold1M' m . stream 1697 1698discard :: Monad m => m a -> m () 1699{-# INLINE discard #-} 1700discard m = m >> return () 1701 1702-- | /O(n)/ Monadic fold that discards the result 1703foldM_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m () 1704{-# INLINE foldM_ #-} 1705foldM_ m z = discard . Bundle.foldM m z . stream 1706 1707-- | /O(n)/ Monadic fold that discards the result (action applied to 1708-- each element and its index) 1709ifoldM_ :: (Monad m, Vector v b) => (a -> Int -> b -> m a) -> a -> v b -> m () 1710{-# INLINE ifoldM_ #-} 1711ifoldM_ m z = discard . Bundle.foldM (uncurry . m) z . Bundle.indexed . stream 1712 1713-- | /O(n)/ Monadic fold over non-empty vectors that discards the result 1714fold1M_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m () 1715{-# INLINE fold1M_ #-} 1716fold1M_ m = discard . Bundle.fold1M m . stream 1717 1718-- | /O(n)/ Monadic fold with strict accumulator that discards the result 1719foldM'_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m () 1720{-# INLINE foldM'_ #-} 1721foldM'_ m z = discard . Bundle.foldM' m z . stream 1722 1723-- | /O(n)/ Monadic fold with strict accumulator that discards the result 1724-- (action applied to each element and its index) 1725ifoldM'_ :: (Monad m, Vector v b) => (a -> Int -> b -> m a) -> a -> v b -> m () 1726{-# INLINE ifoldM'_ #-} 1727ifoldM'_ m z = discard . Bundle.foldM' (uncurry . m) z . Bundle.indexed . stream 1728 1729-- | /O(n)/ Monad fold over non-empty vectors with strict accumulator 1730-- that discards the result 1731fold1M'_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m () 1732{-# INLINE fold1M'_ #-} 1733fold1M'_ m = discard . Bundle.fold1M' m . stream 1734 1735-- Monadic sequencing 1736-- ------------------ 1737 1738-- | Evaluate each action and collect the results 1739sequence :: (Monad m, Vector v a, Vector v (m a)) => v (m a) -> m (v a) 1740{-# INLINE sequence #-} 1741sequence = mapM id 1742 1743-- | Evaluate each action and discard the results 1744sequence_ :: (Monad m, Vector v (m a)) => v (m a) -> m () 1745{-# INLINE sequence_ #-} 1746sequence_ = mapM_ id 1747 1748-- Prefix sums (scans) 1749-- ------------------- 1750 1751-- | /O(n)/ Prescan 1752-- 1753-- @ 1754-- prescanl f z = 'init' . 'scanl' f z 1755-- @ 1756-- 1757-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@ 1758-- 1759prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1760{-# INLINE prescanl #-} 1761prescanl f z = unstream . inplace (S.prescanl f z) id . stream 1762 1763-- | /O(n)/ Prescan with strict accumulator 1764prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1765{-# INLINE prescanl' #-} 1766prescanl' f z = unstream . inplace (S.prescanl' f z) id . stream 1767 1768-- | /O(n)/ Scan 1769-- 1770-- @ 1771-- postscanl f z = 'tail' . 'scanl' f z 1772-- @ 1773-- 1774-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@ 1775-- 1776postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1777{-# INLINE postscanl #-} 1778postscanl f z = unstream . inplace (S.postscanl f z) id . stream 1779 1780-- | /O(n)/ Scan with strict accumulator 1781postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1782{-# INLINE postscanl' #-} 1783postscanl' f z = unstream . inplace (S.postscanl' f z) id . stream 1784 1785-- | /O(n)/ Haskell-style scan 1786-- 1787-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)> 1788-- > where y1 = z 1789-- > yi = f y(i-1) x(i-1) 1790-- 1791-- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@ 1792-- 1793scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1794{-# INLINE scanl #-} 1795scanl f z = unstream . Bundle.scanl f z . stream 1796 1797-- | /O(n)/ Haskell-style scan with strict accumulator 1798scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a 1799{-# INLINE scanl' #-} 1800scanl' f z = unstream . Bundle.scanl' f z . stream 1801 1802-- | /O(n)/ Scan over a vector with its index 1803iscanl :: (Vector v a, Vector v b) => (Int -> a -> b -> a) -> a -> v b -> v a 1804{-# INLINE iscanl #-} 1805iscanl f z = 1806 unstream 1807 . inplace (S.scanl (\a (i, b) -> f i a b) z . S.indexed) (+1) 1808 . stream 1809 1810-- | /O(n)/ Scan over a vector (strictly) with its index 1811iscanl' :: (Vector v a, Vector v b) => (Int -> a -> b -> a) -> a -> v b -> v a 1812{-# INLINE iscanl' #-} 1813iscanl' f z = 1814 unstream 1815 . inplace (S.scanl' (\a (i, b) -> f i a b) z . S.indexed) (+1) 1816 . stream 1817 1818 1819-- | /O(n)/ Scan over a non-empty vector 1820-- 1821-- > scanl f <x1,...,xn> = <y1,...,yn> 1822-- > where y1 = x1 1823-- > yi = f y(i-1) xi 1824-- 1825scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a 1826{-# INLINE scanl1 #-} 1827scanl1 f = unstream . inplace (S.scanl1 f) id . stream 1828 1829-- | /O(n)/ Scan over a non-empty vector with a strict accumulator 1830scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a 1831{-# INLINE scanl1' #-} 1832scanl1' f = unstream . inplace (S.scanl1' f) id . stream 1833 1834-- | /O(n)/ Right-to-left prescan 1835-- 1836-- @ 1837-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse' 1838-- @ 1839-- 1840prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1841{-# INLINE prescanr #-} 1842prescanr f z = unstreamR . inplace (S.prescanl (flip f) z) id . streamR 1843 1844-- | /O(n)/ Right-to-left prescan with strict accumulator 1845prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1846{-# INLINE prescanr' #-} 1847prescanr' f z = unstreamR . inplace (S.prescanl' (flip f) z) id . streamR 1848 1849-- | /O(n)/ Right-to-left scan 1850postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1851{-# INLINE postscanr #-} 1852postscanr f z = unstreamR . inplace (S.postscanl (flip f) z) id . streamR 1853 1854-- | /O(n)/ Right-to-left scan with strict accumulator 1855postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1856{-# INLINE postscanr' #-} 1857postscanr' f z = unstreamR . inplace (S.postscanl' (flip f) z) id . streamR 1858 1859-- | /O(n)/ Right-to-left Haskell-style scan 1860scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1861{-# INLINE scanr #-} 1862scanr f z = unstreamR . Bundle.scanl (flip f) z . streamR 1863 1864-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator 1865scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b 1866{-# INLINE scanr' #-} 1867scanr' f z = unstreamR . Bundle.scanl' (flip f) z . streamR 1868 1869-- | /O(n)/ Right-to-left scan over a vector with its index 1870iscanr :: (Vector v a, Vector v b) => (Int -> a -> b -> b) -> b -> v a -> v b 1871{-# INLINE iscanr #-} 1872iscanr f z v = 1873 unstreamR 1874 . inplace (S.scanl (flip $ uncurry f) z . S.indexedR n) (+1) 1875 . streamR 1876 $ v 1877 where n = length v 1878 1879-- | /O(n)/ Right-to-left scan over a vector (strictly) with its index 1880iscanr' :: (Vector v a, Vector v b) => (Int -> a -> b -> b) -> b -> v a -> v b 1881{-# INLINE iscanr' #-} 1882iscanr' f z v = 1883 unstreamR 1884 . inplace (S.scanl' (flip $ uncurry f) z . S.indexedR n) (+1) 1885 . streamR 1886 $ v 1887 where n = length v 1888 1889-- | /O(n)/ Right-to-left scan over a non-empty vector 1890scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a 1891{-# INLINE scanr1 #-} 1892scanr1 f = unstreamR . inplace (S.scanl1 (flip f)) id . streamR 1893 1894-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict 1895-- accumulator 1896scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a 1897{-# INLINE scanr1' #-} 1898scanr1' f = unstreamR . inplace (S.scanl1' (flip f)) id . streamR 1899 1900-- Conversions - Lists 1901-- ------------------------ 1902 1903-- | /O(n)/ Convert a vector to a list 1904toList :: Vector v a => v a -> [a] 1905{-# INLINE toList #-} 1906toList = Bundle.toList . stream 1907 1908-- | /O(n)/ Convert a list to a vector 1909fromList :: Vector v a => [a] -> v a 1910{-# INLINE fromList #-} 1911fromList = unstream . Bundle.fromList 1912 1913-- | /O(n)/ Convert the first @n@ elements of a list to a vector 1914-- 1915-- @ 1916-- fromListN n xs = 'fromList' ('take' n xs) 1917-- @ 1918fromListN :: Vector v a => Int -> [a] -> v a 1919{-# INLINE fromListN #-} 1920fromListN n = unstream . Bundle.fromListN n 1921 1922-- Conversions - Immutable vectors 1923-- ------------------------------- 1924 1925-- | /O(n)/ Convert different vector types 1926convert :: (Vector v a, Vector w a) => v a -> w a 1927{-# INLINE convert #-} 1928convert = unstream . Bundle.reVector . stream 1929 1930-- Conversions - Mutable vectors 1931-- ----------------------------- 1932 1933-- | /O(1)/ Unsafe convert a mutable vector to an immutable one without 1934-- copying. The mutable vector may not be used after this operation. 1935unsafeFreeze 1936 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a) 1937{-# INLINE unsafeFreeze #-} 1938unsafeFreeze = basicUnsafeFreeze 1939 1940-- | /O(n)/ Yield an immutable copy of the mutable vector. 1941freeze :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a) 1942{-# INLINE freeze #-} 1943freeze mv = unsafeFreeze =<< M.clone mv 1944 1945-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without 1946-- copying. The immutable vector may not be used after this operation. 1947unsafeThaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a) 1948{-# INLINE_FUSED unsafeThaw #-} 1949unsafeThaw = basicUnsafeThaw 1950 1951-- | /O(n)/ Yield a mutable copy of the immutable vector. 1952thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a) 1953{-# INLINE_FUSED thaw #-} 1954thaw v = do 1955 mv <- M.unsafeNew (length v) 1956 unsafeCopy mv v 1957 return mv 1958 1959{-# RULES 1960 1961"unsafeThaw/new [Vector]" forall p. 1962 unsafeThaw (new p) = New.runPrim p 1963 1964"thaw/new [Vector]" forall p. 1965 thaw (new p) = New.runPrim p #-} 1966 1967 1968 1969{- 1970-- | /O(n)/ Yield a mutable vector containing copies of each vector in the 1971-- list. 1972thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a) 1973{-# INLINE_FUSED thawMany #-} 1974-- FIXME: add rule for (stream (new (New.create (thawMany vs)))) 1975-- NOTE: We don't try to consume the list lazily as this wouldn't significantly 1976-- change the space requirements anyway. 1977thawMany vs = do 1978 mv <- M.new n 1979 thaw_loop mv vs 1980 return mv 1981 where 1982 n = List.foldl' (\k v -> k + length v) 0 vs 1983 1984 thaw_loop mv [] = mv `seq` return () 1985 thaw_loop mv (v:vs) 1986 = do 1987 let n = length v 1988 unsafeCopy (M.unsafeTake n mv) v 1989 thaw_loop (M.unsafeDrop n mv) vs 1990-} 1991 1992-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must 1993-- have the same length. 1994copy 1995 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m () 1996{-# INLINE copy #-} 1997copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch" 1998 (M.length dst == length src) 1999 $ unsafeCopy dst src 2000 2001-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must 2002-- have the same length. This is not checked. 2003unsafeCopy 2004 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m () 2005{-# INLINE unsafeCopy #-} 2006unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch" 2007 (M.length dst == length src) 2008 $ (dst `seq` src `seq` basicUnsafeCopy dst src) 2009 2010-- Conversions to/from Bundles 2011-- --------------------------- 2012 2013-- | /O(1)/ Convert a vector to a 'Bundle' 2014stream :: Vector v a => v a -> Bundle v a 2015{-# INLINE_FUSED stream #-} 2016stream v = stream' v 2017 2018-- Same as 'stream', but can be used to avoid having a cycle in the dependency 2019-- graph of functions, which forces GHC to create a loop breaker. 2020stream' :: Vector v a => v a -> Bundle v a 2021{-# INLINE stream' #-} 2022stream' v = Bundle.fromVector v 2023 2024{- 2025stream v = v `seq` n `seq` (Bundle.unfoldr get 0 `Bundle.sized` Exact n) 2026 where 2027 n = length v 2028 2029 -- NOTE: the False case comes first in Core so making it the recursive one 2030 -- makes the code easier to read 2031 {-# INLINE get #-} 2032 get i | i >= n = Nothing 2033 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1) 2034-} 2035 2036-- | /O(n)/ Construct a vector from a 'Bundle' 2037unstream :: Vector v a => Bundle v a -> v a 2038{-# INLINE unstream #-} 2039unstream s = new (New.unstream s) 2040 2041{-# RULES 2042 2043"stream/unstream [Vector]" forall s. 2044 stream (new (New.unstream s)) = s 2045 2046"New.unstream/stream [Vector]" forall v. 2047 New.unstream (stream v) = clone v 2048 2049"clone/new [Vector]" forall p. 2050 clone (new p) = p 2051 2052"inplace [Vector]" 2053 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m. 2054 New.unstream (inplace f g (stream (new m))) = New.transform f g m 2055 2056"uninplace [Vector]" 2057 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m. 2058 stream (new (New.transform f g m)) = inplace f g (stream (new m)) #-} 2059 2060 2061 2062-- | /O(1)/ Convert a vector to a 'Bundle', proceeding from right to left 2063streamR :: Vector v a => v a -> Bundle u a 2064{-# INLINE_FUSED streamR #-} 2065streamR v = v `seq` n `seq` (Bundle.unfoldr get n `Bundle.sized` Exact n) 2066 where 2067 n = length v 2068 2069 {-# INLINE get #-} 2070 get 0 = Nothing 2071 get i = let i' = i-1 2072 in 2073 case basicUnsafeIndexM v i' of Box x -> Just (x, i') 2074 2075-- | /O(n)/ Construct a vector from a 'Bundle', proceeding from right to left 2076unstreamR :: Vector v a => Bundle v a -> v a 2077{-# INLINE unstreamR #-} 2078unstreamR s = new (New.unstreamR s) 2079 2080{-# RULES 2081 2082"streamR/unstreamR [Vector]" forall s. 2083 streamR (new (New.unstreamR s)) = s 2084 2085"New.unstreamR/streamR/new [Vector]" forall p. 2086 New.unstreamR (streamR (new p)) = p 2087 2088"New.unstream/streamR/new [Vector]" forall p. 2089 New.unstream (streamR (new p)) = New.modify M.reverse p 2090 2091"New.unstreamR/stream/new [Vector]" forall p. 2092 New.unstreamR (stream (new p)) = New.modify M.reverse p 2093 2094"inplace right [Vector]" 2095 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m. 2096 New.unstreamR (inplace f g (streamR (new m))) = New.transformR f g m 2097 2098"uninplace right [Vector]" 2099 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m. 2100 streamR (new (New.transformR f g m)) = inplace f g (streamR (new m)) #-} 2101 2102 2103 2104unstreamM :: (Monad m, Vector v a) => MBundle m u a -> m (v a) 2105{-# INLINE_FUSED unstreamM #-} 2106unstreamM s = do 2107 xs <- MBundle.toList s 2108 return $ unstream $ Bundle.unsafeFromList (MBundle.size s) xs 2109 2110unstreamPrimM :: (PrimMonad m, Vector v a) => MBundle m u a -> m (v a) 2111{-# INLINE_FUSED unstreamPrimM #-} 2112unstreamPrimM s = M.munstream s >>= unsafeFreeze 2113 2114-- FIXME: the next two functions are only necessary for the specialisations 2115unstreamPrimM_IO :: Vector v a => MBundle IO u a -> IO (v a) 2116{-# INLINE unstreamPrimM_IO #-} 2117unstreamPrimM_IO = unstreamPrimM 2118 2119unstreamPrimM_ST :: Vector v a => MBundle (ST s) u a -> ST s (v a) 2120{-# INLINE unstreamPrimM_ST #-} 2121unstreamPrimM_ST = unstreamPrimM 2122 2123{-# RULES 2124 2125"unstreamM[IO]" unstreamM = unstreamPrimM_IO 2126"unstreamM[ST]" unstreamM = unstreamPrimM_ST #-} 2127 2128 2129 2130 2131-- Recycling support 2132-- ----------------- 2133 2134-- | Construct a vector from a monadic initialiser. 2135new :: Vector v a => New v a -> v a 2136{-# INLINE_FUSED new #-} 2137new m = m `seq` runST (unsafeFreeze =<< New.run m) 2138 2139-- | Convert a vector to an initialiser which, when run, produces a copy of 2140-- the vector. 2141clone :: Vector v a => v a -> New v a 2142{-# INLINE_FUSED clone #-} 2143clone v = v `seq` New.create ( 2144 do 2145 mv <- M.new (length v) 2146 unsafeCopy mv v 2147 return mv) 2148 2149-- Comparisons 2150-- ----------- 2151 2152-- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also 2153-- instances of 'Eq' and it is usually more appropriate to use those. This 2154-- function is primarily intended for implementing 'Eq' instances for new 2155-- vector types. 2156eq :: (Vector v a, Eq a) => v a -> v a -> Bool 2157{-# INLINE eq #-} 2158xs `eq` ys = stream xs == stream ys 2159 2160-- | /O(n)/ 2161eqBy :: (Vector v a, Vector v b) => (a -> b -> Bool) -> v a -> v b -> Bool 2162{-# INLINE eqBy #-} 2163eqBy e xs ys = Bundle.eqBy e (stream xs) (stream ys) 2164 2165-- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are 2166-- also instances of 'Ord' and it is usually more appropriate to use those. This 2167-- function is primarily intended for implementing 'Ord' instances for new 2168-- vector types. 2169cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering 2170{-# INLINE cmp #-} 2171cmp xs ys = compare (stream xs) (stream ys) 2172 2173-- | /O(n)/ 2174cmpBy :: (Vector v a, Vector v b) => (a -> b -> Ordering) -> v a -> v b -> Ordering 2175cmpBy c xs ys = Bundle.cmpBy c (stream xs) (stream ys) 2176 2177-- Show 2178-- ---- 2179 2180-- | Generic definition of 'Prelude.showsPrec' 2181showsPrec :: (Vector v a, Show a) => Int -> v a -> ShowS 2182{-# INLINE showsPrec #-} 2183showsPrec _ = shows . toList 2184 2185liftShowsPrec :: (Vector v a) => (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> v a -> ShowS 2186{-# INLINE liftShowsPrec #-} 2187liftShowsPrec _ s _ = s . toList 2188 2189-- | Generic definition of 'Text.Read.readPrec' 2190readPrec :: (Vector v a, Read a) => Read.ReadPrec (v a) 2191{-# INLINE readPrec #-} 2192readPrec = do 2193 xs <- Read.readPrec 2194 return (fromList xs) 2195 2196-- | /Note:/ uses 'ReadS' 2197liftReadsPrec :: (Vector v a) => (Int -> Read.ReadS a) -> ReadS [a] -> Int -> Read.ReadS (v a) 2198liftReadsPrec _ r _ s = [ (fromList v, s') | (v, s') <- r s ] 2199 2200-- Data and Typeable 2201-- ----------------- 2202 2203-- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a 2204-- list. 2205gfoldl :: (Vector v a, Data a) 2206 => (forall d b. Data d => c (d -> b) -> d -> c b) 2207 -> (forall g. g -> c g) 2208 -> v a 2209 -> c (v a) 2210{-# INLINE gfoldl #-} 2211gfoldl f z v = z fromList `f` toList v 2212 2213mkVecConstr :: String -> Constr 2214{-# INLINE mkVecConstr #-} 2215mkVecConstr name = mkConstr (mkVecType name) "fromList" [] Prefix 2216 2217mkVecType :: String -> DataType 2218{-# INLINE mkVecType #-} 2219mkVecType name = mkDataType name [mkVecConstr name] 2220 2221mkType :: String -> DataType 2222{-# INLINE mkType #-} 2223mkType = mkNoRepType 2224 2225gunfold :: (Vector v a, Data a) 2226 => (forall b r. Data b => c (b -> r) -> c r) 2227 -> (forall r. r -> c r) 2228 -> Constr -> c (v a) 2229gunfold k z c = case constrIndex c of 2230 1 -> k (z fromList) 2231 _ -> error "gunfold" 2232 2233#if __GLASGOW_HASKELL__ >= 707 2234dataCast :: (Vector v a, Data a, Typeable v, Typeable t) 2235#else 2236dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t) 2237#endif 2238 => (forall d. Data d => c (t d)) -> Maybe (c (v a)) 2239{-# INLINE dataCast #-} 2240dataCast f = gcast1 f 2241