Finish Stream -> Bundle renaming
[darcs-mirrors/vector.git] / Data / Vector / Primitive.hs
index b9fbe11..644cc09 100644 (file)
@@ -25,7 +25,7 @@ module Data.Vector.Primitive (
   length, null,
 
   -- ** Indexing
   length, null,
 
   -- ** Indexing
-  (!), head, last,
+  (!), (!?), head, last,
   unsafeIndex, unsafeHead, unsafeLast,
 
   -- ** Monadic indexing
   unsafeIndex, unsafeHead, unsafeLast,
 
   -- ** Monadic indexing
@@ -33,19 +33,20 @@ module Data.Vector.Primitive (
   unsafeIndexM, unsafeHeadM, unsafeLastM,
 
   -- ** Extracting subvectors (slicing)
   unsafeIndexM, unsafeHeadM, unsafeLastM,
 
   -- ** Extracting subvectors (slicing)
-  slice, init, tail, take, drop,
+  slice, init, tail, take, drop, splitAt,
   unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
   -- * Construction
 
   -- ** Initialisation
   unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
   -- * Construction
 
   -- ** Initialisation
-  empty, singleton, replicate, generate,
+  empty, singleton, replicate, generate, iterateN,
 
   -- ** Monadic initialisation
 
   -- ** Monadic initialisation
-  replicateM, create,
+  replicateM, generateM, create,
 
   -- ** Unfolding
   unfoldr, unfoldrN,
 
   -- ** Unfolding
   unfoldr, unfoldrN,
+  constructN, constructrN,
 
   -- ** Enumeration
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Enumeration
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
@@ -111,6 +112,7 @@ module Data.Vector.Primitive (
 
   -- ** Monadic folds
   foldM, foldM', fold1M, fold1M',
 
   -- ** Monadic folds
   foldM, foldM', fold1M, fold1M',
+  foldM_, foldM'_, fold1M_, fold1M'_,
 
   -- * Prefix sums (scans)
   prescanl, prescanl',
 
   -- * Prefix sums (scans)
   prescanl, prescanl',
@@ -129,15 +131,17 @@ module Data.Vector.Primitive (
   G.convert,
 
   -- ** Mutable vectors
   G.convert,
 
   -- ** Mutable vectors
-  unsafeFreeze, thaw, copy, unsafeCopy
+  freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy
 ) where
 
 import qualified Data.Vector.Generic           as G
 import           Data.Vector.Primitive.Mutable ( MVector(..) )
 ) where
 
 import qualified Data.Vector.Generic           as G
 import           Data.Vector.Primitive.Mutable ( MVector(..) )
-import qualified Data.Vector.Fusion.Stream as Stream
+import qualified Data.Vector.Fusion.Bundle as Bundle
 import           Data.Primitive.ByteArray
 import           Data.Primitive ( Prim, sizeOf )
 
 import           Data.Primitive.ByteArray
 import           Data.Primitive ( Prim, sizeOf )
 
+import Control.DeepSeq ( NFData )
+
 import Control.Monad ( liftM )
 import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 import Control.Monad ( liftM )
 import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
@@ -145,7 +149,7 @@ import Control.Monad.Primitive
 import Prelude hiding ( length, null,
                         replicate, (++), concat,
                         head, last,
 import Prelude hiding ( length, null,
                         replicate, (++), concat,
                         head, last,
-                        init, tail, take, drop, reverse,
+                        init, tail, take, drop, splitAt, reverse,
                         map, concatMap,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
                         filter, takeWhile, dropWhile, span, break,
                         map, concatMap,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
                         filter, takeWhile, dropWhile, span, break,
@@ -160,6 +164,7 @@ import qualified Prelude
 
 import Data.Typeable ( Typeable )
 import Data.Data     ( Data(..) )
 
 import Data.Typeable ( Typeable )
 import Data.Data     ( Data(..) )
+import Text.Read     ( Read(..), readListPrecDefault )
 
 import Data.Monoid   ( Monoid(..) )
 
 
 import Data.Monoid   ( Monoid(..) )
 
@@ -169,8 +174,14 @@ data Vector a = Vector {-# UNPACK #-} !Int
                        {-# UNPACK #-} !ByteArray
   deriving ( Typeable )
 
                        {-# UNPACK #-} !ByteArray
   deriving ( Typeable )
 
+instance NFData (Vector a)
+
 instance (Show a, Prim a) => Show (Vector a) where
 instance (Show a, Prim a) => Show (Vector a) where
-    show = (Prelude.++ " :: Data.Vector.Primitive.Vector") . ("fromList " Prelude.++) . show . toList
+  showsPrec = G.showsPrec
+
+instance (Read a, Prim a) => Read (Vector a) where
+  readPrec = G.readPrec
+  readListPrec = readListPrecDefault
 
 instance (Data a, Prim a) => Data (Vector a) where
   gfoldl       = G.gfoldl
 
 instance (Data a, Prim a) => Data (Vector a) where
   gfoldl       = G.gfoldl
@@ -187,6 +198,10 @@ instance Prim a => G.Vector Vector a where
   basicUnsafeFreeze (MVector i n marr)
     = Vector i n `liftM` unsafeFreezeByteArray marr
 
   basicUnsafeFreeze (MVector i n marr)
     = Vector i n `liftM` unsafeFreezeByteArray marr
 
+  {-# INLINE basicUnsafeThaw #-}
+  basicUnsafeThaw (Vector i n arr)
+    = MVector i n `liftM` unsafeThawByteArray arr
+
   {-# INLINE basicLength #-}
   basicLength (Vector _ n _) = n
 
   {-# INLINE basicLength #-}
   basicLength (Vector _ n _) = n
 
@@ -194,11 +209,11 @@ instance Prim a => G.Vector Vector a where
   basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
 
   {-# INLINE basicUnsafeIndexM #-}
   basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
 
   {-# INLINE basicUnsafeIndexM #-}
-  basicUnsafeIndexM (Vector i _ arr) j = return (indexByteArray arr (i+j))
+  basicUnsafeIndexM (Vector i _ arr) j = return $! indexByteArray arr (i+j)
 
   {-# INLINE basicUnsafeCopy #-}
   basicUnsafeCopy (MVector i n dst) (Vector j _ src)
 
   {-# INLINE basicUnsafeCopy #-}
   basicUnsafeCopy (MVector i n dst) (Vector j _ src)
-    = memcpyByteArray' dst (i * sz) src (j * sz) (n * sz)
+    = copyByteArray dst (i*sz) src (j*sz) (n*sz)
     where
       sz = sizeOf (undefined :: a)
 
     where
       sz = sizeOf (undefined :: a)
 
@@ -208,27 +223,27 @@ instance Prim a => G.Vector Vector a where
 -- See http://trac.haskell.org/vector/ticket/12
 instance (Prim a, Eq a) => Eq (Vector a) where
   {-# INLINE (==) #-}
 -- See http://trac.haskell.org/vector/ticket/12
 instance (Prim a, Eq a) => Eq (Vector a) where
   {-# INLINE (==) #-}
-  xs == ys = Stream.eq (G.stream xs) (G.stream ys)
+  xs == ys = Bundle.eq (G.stream xs) (G.stream ys)
 
   {-# INLINE (/=) #-}
 
   {-# INLINE (/=) #-}
-  xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
+  xs /= ys = not (Bundle.eq (G.stream xs) (G.stream ys))
 
 -- See http://trac.haskell.org/vector/ticket/12
 instance (Prim a, Ord a) => Ord (Vector a) where
   {-# INLINE compare #-}
 
 -- See http://trac.haskell.org/vector/ticket/12
 instance (Prim a, Ord a) => Ord (Vector a) where
   {-# INLINE compare #-}
-  compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
+  compare xs ys = Bundle.cmp (G.stream xs) (G.stream ys)
 
   {-# INLINE (<) #-}
 
   {-# INLINE (<) #-}
-  xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
+  xs < ys = Bundle.cmp (G.stream xs) (G.stream ys) == LT
 
   {-# INLINE (<=) #-}
 
   {-# INLINE (<=) #-}
-  xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
+  xs <= ys = Bundle.cmp (G.stream xs) (G.stream ys) /= GT
 
   {-# INLINE (>) #-}
 
   {-# INLINE (>) #-}
-  xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
+  xs > ys = Bundle.cmp (G.stream xs) (G.stream ys) == GT
 
   {-# INLINE (>=) #-}
 
   {-# INLINE (>=) #-}
-  xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
+  xs >= ys = Bundle.cmp (G.stream xs) (G.stream ys) /= LT
 
 instance Prim a => Monoid (Vector a) where
   {-# INLINE mempty #-}
 
 instance Prim a => Monoid (Vector a) where
   {-# INLINE mempty #-}
@@ -261,6 +276,11 @@ null = G.null
 {-# INLINE (!) #-}
 (!) = (G.!)
 
 {-# INLINE (!) #-}
 (!) = (G.!)
 
+-- | O(1) Safe indexing
+(!?) :: Prim a => Vector a -> Int -> Maybe a
+{-# INLINE (!?) #-}
+(!?) = (G.!?)
+
 -- | /O(1)/ First element
 head :: Prim a => Vector a -> a
 {-# INLINE head #-}
 -- | /O(1)/ First element
 head :: Prim a => Vector a -> a
 {-# INLINE head #-}
@@ -379,6 +399,14 @@ drop :: Prim a => Int -> Vector a -> Vector a
 {-# INLINE drop #-}
 drop = G.drop
 
 {-# INLINE drop #-}
 drop = G.drop
 
+-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.
+--
+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@
+-- but slightly more efficient.
+{-# INLINE splitAt #-}
+splitAt :: Prim a => Int -> Vector a -> (Vector a, Vector a)
+splitAt = G.splitAt
+
 -- | /O(1)/ Yield a slice of the vector without copying. The vector must
 -- contain at least @i+n@ elements but this is not checked.
 unsafeSlice :: Prim a => Int   -- ^ @i@ starting index
 -- | /O(1)/ Yield a slice of the vector without copying. The vector must
 -- contain at least @i+n@ elements but this is not checked.
 unsafeSlice :: Prim a => Int   -- ^ @i@ starting index
@@ -436,6 +464,11 @@ generate :: Prim a => Int -> (Int -> a) -> Vector a
 {-# INLINE generate #-}
 generate = G.generate
 
 {-# INLINE generate #-}
 generate = G.generate
 
+-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
+iterateN :: Prim a => Int -> (a -> a) -> a -> Vector a
+{-# INLINE iterateN #-}
+iterateN = G.iterateN
+
 -- Unfolding
 -- ---------
 
 -- Unfolding
 -- ---------
 
@@ -458,6 +491,25 @@ unfoldrN :: Prim a => Int -> (b -> Maybe (a, b)) -> b -> Vector a
 {-# INLINE unfoldrN #-}
 unfoldrN = G.unfoldrN
 
 {-# INLINE unfoldrN #-}
 unfoldrN = G.unfoldrN
 
+-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the
+-- generator function to the already constructed part of the vector.
+--
+-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>
+--
+constructN :: Prim a => Int -> (Vector a -> a) -> Vector a
+{-# INLINE constructN #-}
+constructN = G.constructN
+
+-- | /O(n)/ Construct a vector with @n@ elements from right to left by
+-- repeatedly applying the generator function to the already constructed part
+-- of the vector.
+--
+-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in f <c,b,a>
+--
+constructrN :: Prim a => Int -> (Vector a -> a) -> Vector a
+{-# INLINE constructrN #-}
+constructrN = G.constructrN
+
 -- Enumeration
 -- -----------
 
 -- Enumeration
 -- -----------
 
@@ -526,14 +578,21 @@ replicateM :: (Monad m, Prim a) => Int -> m a -> m (Vector a)
 {-# INLINE replicateM #-}
 replicateM = G.replicateM
 
 {-# INLINE replicateM #-}
 replicateM = G.replicateM
 
+-- | /O(n)/ Construct a vector of the given length by applying the monadic
+-- action to each index
+generateM :: (Monad m, Prim a) => Int -> (Int -> m a) -> m (Vector a)
+{-# INLINE generateM #-}
+generateM = G.generateM
+
 -- | Execute the monadic action and freeze the resulting vector.
 --
 -- @
 -- | Execute the monadic action and freeze the resulting vector.
 --
 -- @
--- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\' }) = \<'a','b'\>
+-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\'; return v }) = \<'a','b'\>
 -- @
 create :: Prim a => (forall s. ST s (MVector s a)) -> Vector a
 {-# INLINE create #-}
 -- @
 create :: Prim a => (forall s. ST s (MVector s a)) -> Vector a
 {-# INLINE create #-}
-create = G.create
+-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120
+create p = G.create p
 
 -- Restricting memory usage
 -- ------------------------
 
 -- Restricting memory usage
 -- ------------------------
@@ -666,7 +725,7 @@ unsafeBackpermute = G.unsafeBackpermute
 -- @
 modify :: Prim a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
 {-# INLINE modify #-}
 -- @
 modify :: Prim a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
 {-# INLINE modify #-}
-modify = G.modify
+modify p = G.modify p
 
 -- Mapping
 -- -------
 
 -- Mapping
 -- -------
@@ -1065,11 +1124,32 @@ foldM' :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m a
 {-# INLINE foldM' #-}
 foldM' = G.foldM'
 
 {-# INLINE foldM' #-}
 foldM' = G.foldM'
 
--- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
 fold1M' :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m a
 {-# INLINE fold1M' #-}
 fold1M' = G.fold1M'
 
 fold1M' :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m a
 {-# INLINE fold1M' #-}
 fold1M' = G.fold1M'
 
+-- | /O(n)/ Monadic fold that discards the result
+foldM_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM_ #-}
+foldM_ = G.foldM_
+
+-- | /O(n)/ Monadic fold over non-empty vectors that discards the result
+fold1M_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M_ #-}
+fold1M_ = G.fold1M_
+
+-- | /O(n)/ Monadic fold with strict accumulator that discards the result
+foldM'_ :: (Monad m, Prim b) => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM'_ #-}
+foldM'_ = G.foldM'_
+
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
+-- that discards the result
+fold1M'_ :: (Monad m, Prim a) => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M'_ #-}
+fold1M'_ = G.fold1M'_
+
 -- Prefix sums (scans)
 -- -------------------
 
 -- Prefix sums (scans)
 -- -------------------
 
@@ -1216,20 +1296,31 @@ unsafeFreeze :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> m (Vector a)
 {-# INLINE unsafeFreeze #-}
 unsafeFreeze = G.unsafeFreeze
 
 {-# INLINE unsafeFreeze #-}
 unsafeFreeze = G.unsafeFreeze
 
+-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
+-- copying. The immutable vector may not be used after this operation.
+unsafeThaw :: (Prim a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a)
+{-# INLINE unsafeThaw #-}
+unsafeThaw = G.unsafeThaw
+
 -- | /O(n)/ Yield a mutable copy of the immutable vector.
 thaw :: (Prim a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a)
 {-# INLINE thaw #-}
 thaw = G.thaw
 
 -- | /O(n)/ Yield a mutable copy of the immutable vector.
 thaw :: (Prim a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a)
 {-# INLINE thaw #-}
 thaw = G.thaw
 
+-- | /O(n)/ Yield an immutable copy of the mutable vector.
+freeze :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> m (Vector a)
+{-# INLINE freeze #-}
+freeze = G.freeze
+
 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
--- have the same length.
+-- have the same length. This is not checked.
 unsafeCopy
   :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE unsafeCopy #-}
 unsafeCopy = G.unsafeCopy
            
 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
 unsafeCopy
   :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE unsafeCopy #-}
 unsafeCopy = G.unsafeCopy
            
 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
--- have the same length. This is not checked.
+-- have the same length.
 copy :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE copy #-}
 copy = G.copy
 copy :: (Prim a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE copy #-}
 copy = G.copy