Add constructN and constructrN
[darcs-mirrors/vector.git] / Data / Vector.hs
index eae0f0f..6b3cc98 100644 (file)
@@ -46,13 +46,14 @@ module Data.Vector (
   -- * Construction
 
   -- ** Initialisation
-  empty, singleton, replicate, generate,
+  empty, singleton, replicate, generate, iterateN,
 
   -- ** Monadic initialisation
-  replicateM, create,
+  replicateM, generateM, create,
 
   -- ** Unfolding
   unfoldr, unfoldrN,
+  constructN, constructrN,
 
   -- ** Enumeration
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
@@ -125,6 +126,10 @@ module Data.Vector (
 
   -- ** Monadic folds
   foldM, foldM', fold1M, fold1M',
+  foldM_, foldM'_, fold1M_, fold1M'_,
+
+  -- ** Monadic sequencing
+  sequence, sequence_,
 
   -- * Prefix sums (scans)
   prescanl, prescanl',
@@ -151,7 +156,7 @@ import           Data.Vector.Mutable  ( MVector(..) )
 import           Data.Primitive.Array
 import qualified Data.Vector.Fusion.Stream as Stream
 
-import Control.Monad ( liftM )
+import Control.Monad ( liftM, ap )
 import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 
@@ -167,7 +172,7 @@ import Prelude hiding ( length, null,
                         all, any, and, or, sum, product, minimum, maximum,
                         scanl, scanl1, scanr, scanr1,
                         enumFromTo, enumFromThenTo,
-                        mapM, mapM_ )
+                        mapM, mapM_, sequence, sequence_ )
 
 import qualified Prelude
 
@@ -175,6 +180,9 @@ import Data.Typeable ( Typeable )
 import Data.Data     ( Data(..) )
 
 import Data.Monoid   ( Monoid(..) )
+import qualified Control.Applicative as Applicative
+import qualified Data.Foldable as Foldable
+import qualified Data.Traversable as Traversable
 
 -- | Boxed vectors, supporting efficient slicing.
 data Vector a = Vector {-# UNPACK #-} !Int
@@ -212,6 +220,10 @@ instance G.Vector Vector a where
   {-# INLINE basicUnsafeIndexM #-}
   basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
 
+  {-# INLINE basicUnsafeCopy #-}
+  basicUnsafeCopy (MVector i n dst) (Vector j _ src)
+    = copyArray src j dst i n
+
 -- See http://trac.haskell.org/vector/ticket/12
 instance Eq a => Eq (Vector a) where
   {-# INLINE (==) #-}
@@ -247,6 +259,54 @@ instance Monoid (Vector a) where
   {-# INLINE mconcat #-}
   mconcat = concat
 
+instance Functor Vector where
+  {-# INLINE fmap #-}
+  fmap = map
+
+instance Monad Vector where
+  {-# INLINE return #-}
+  return = singleton
+
+  {-# INLINE (>>=) #-}
+  (>>=) = flip concatMap
+
+instance Applicative.Applicative Vector where
+  {-# INLINE pure #-}
+  pure = singleton
+
+  {-# INLINE (<*>) #-}
+  (<*>) = ap
+
+instance Applicative.Alternative Vector where
+  {-# INLINE empty #-}
+  empty = empty
+
+  {-# INLINE (<|>) #-}
+  (<|>) = (++)
+
+instance Foldable.Foldable Vector where
+  {-# INLINE foldr #-}
+  foldr = foldr
+
+  {-# INLINE foldl #-}
+  foldl = foldl
+  
+  {-# INLINE foldr1 #-}
+  foldr1 = foldr1
+
+  {-# INLINE foldl1 #-}
+  foldl1 = foldl1
+
+instance Traversable.Traversable Vector where
+  {-# INLINE traverse #-}
+  traverse f xs = fromList Applicative.<$> Traversable.traverse f (toList xs)
+
+  {-# INLINE mapM #-}
+  mapM = mapM
+
+  {-# INLINE sequence #-}
+  sequence = sequence
+
 -- Length information
 -- ------------------
 
@@ -455,6 +515,11 @@ generate :: Int -> (Int -> a) -> Vector a
 {-# INLINE generate #-}
 generate = G.generate
 
+-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
+iterateN :: Int -> (a -> a) -> a -> Vector a
+{-# INLINE iterateN #-}
+iterateN = G.iterateN
+
 -- Unfolding
 -- ---------
 
@@ -477,6 +542,25 @@ unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a
 {-# 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 :: 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 :: Int -> (Vector a -> a) -> Vector a
+{-# INLINE constructrN #-}
+constructrN = G.constructrN
+
 -- Enumeration
 -- -----------
 
@@ -545,6 +629,12 @@ replicateM :: Monad m => Int -> m a -> m (Vector a)
 {-# INLINE replicateM #-}
 replicateM = G.replicateM
 
+-- | /O(n)/ Construct a vector of the given length by applying the monadic
+-- action to each index
+generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)
+{-# INLINE generateM #-}
+generateM = G.generateM
+
 -- | Execute the monadic action and freeze the resulting vector.
 --
 -- @
@@ -1186,6 +1276,40 @@ fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
 {-# INLINE fold1M' #-}
 fold1M' = G.fold1M'
 
+-- | /O(n)/ Monadic fold that discards the result
+foldM_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM_ #-}
+foldM_ = G.foldM_
+
+-- | /O(n)/ Monadic fold over non-empty vectors that discards the result
+fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M_ #-}
+fold1M_ = G.fold1M_
+
+-- | /O(n)/ Monadic fold with strict accumulator that discards the result
+foldM'_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM'_ #-}
+foldM'_ = G.foldM'_
+
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
+-- that discards the result
+fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M'_ #-}
+fold1M'_ = G.fold1M'_
+
+-- Monadic sequencing
+-- ------------------
+
+-- | Evaluate each action and collect the results
+sequence :: Monad m => Vector (m a) -> m (Vector a)
+{-# INLINE sequence #-}
+sequence = G.sequence
+
+-- | Evaluate each action and discard the results
+sequence_ :: Monad m => Vector (m a) -> m ()
+{-# INLINE sequence_ #-}
+sequence_ = G.sequence_
+
 -- Prefix sums (scans)
 -- -------------------