Add enumFromN, enumFromStepN
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
index 788dc93..e077204 100644 (file)
@@ -29,12 +29,15 @@ module Data.Vector.Generic (
 
   -- * Subvectors
   slice, init, tail, take, drop,
-  unsafeSlice, unsafeInit, unsafeTail,
+  unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
   -- * Permutations
   accum, accumulate, accumulate_,
   (//), update, update_,
   backpermute, reverse,
+  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
+  unsafeUpd, unsafeUpdate, unsafeUpdate_,
+  unsafeBackpermute,
 
   -- * Mapping
   map, imap, concatMap,
@@ -50,14 +53,14 @@ module Data.Vector.Generic (
 
   -- * Filtering
   filter, ifilter, takeWhile, dropWhile,
-  unstablePartition, span, break,
+  partition, unstablePartition, span, break,
 
   -- * Searching
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
  
   -- * Specialised folds
   all, any, and, or,
@@ -72,22 +75,21 @@ module Data.Vector.Generic (
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
+  prescanr, prescanr',
+  postscanr, postscanr',
+  scanr, scanr', scanr1, scanr1',
 
   -- * Enumeration
-  enumFromTo, enumFromThenTo,
+  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- * Conversion to/from lists
   toList, fromList,
 
   -- * Conversion to/from Streams
-  stream, unstream,
+  stream, unstream, streamR, unstreamR,
 
   -- * MVector-based initialisation
-  new,
-
-  -- * Unsafe operations
-  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
-  unsafeUpd, unsafeUpdate, unsafeUpdate_
+  new
 ) where
 
 import           Data.Vector.Generic.Mutable ( MVector )
@@ -114,7 +116,7 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         all, any, and, or, sum, product, maximum, minimum,
-                        scanl, scanl1,
+                        scanl, scanl1, scanr, scanr1,
                         enumFromTo, enumFromThenTo )
 
 #include "vector.h"
@@ -221,6 +223,48 @@ unstream s = new (New.unstream s)
 
  #-}
 
+-- | Convert a vector to a 'Stream'
+streamR :: Vector v a => v a -> Stream a
+{-# INLINE_STREAM streamR #-}
+streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
+  where
+    n = length v
+
+    -- NOTE: the False case comes first in Core so making it the recursive one
+    -- makes the code easier to read
+    {-# INLINE get #-}
+    get 0 = Nothing
+    get i = let i' = i-1
+            in
+            case basicUnsafeIndexM v i' of Box x -> Just (x, i')
+
+-- | Create a vector from a 'Stream'
+unstreamR :: Vector v a => Stream a -> v a
+{-# INLINE unstreamR #-}
+unstreamR s = new (New.unstreamR s)
+
+{-# RULES
+
+"streamR/unstreamR [Vector]" forall v s.
+  streamR (new' v (New.unstreamR s)) = s
+
+"New.unstreamR/streamR/new [Vector]" forall v p.
+  New.unstreamR (streamR (new' v p)) = p
+
+ #-}
+
+{-# RULES
+
+"inplace [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
+  New.unstreamR (inplace f (streamR (new' v m))) = New.transformR f m
+
+"uninplace [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
+  streamR (new' v (New.transformR f m)) = inplace f (streamR (new' v m))
+
+ #-}
+
 -- Length
 -- ------
 
@@ -428,13 +472,13 @@ tail v = slice 1 (length v - 1) v
 -- | Yield the first @n@ elements without copying.
 take :: Vector v a => Int -> v a -> v a
 {-# INLINE_STREAM take #-}
-take n v = slice 0 (min n' (length v)) v
+take n v = unsafeSlice 0 (min n' (length v)) v
   where n' = max n 0
 
 -- | Yield all but the first @n@ elements without copying.
 drop :: Vector v a => Int -> v a -> v a
 {-# INLINE_STREAM drop #-}
-drop n v = slice (min n' len) (max 0 (len - n')) v
+drop n v = unsafeSlice (min n' len) (max 0 (len - n')) v
   where n' = max n 0
         len = length v
 
@@ -456,6 +500,14 @@ unsafeTail :: Vector v a => v a -> v a
 {-# INLINE_STREAM unsafeTail #-}
 unsafeTail v = unsafeSlice 1 (length v - 1) v
 
+unsafeTake :: Vector v a => Int -> v a -> v a
+{-# INLINE unsafeTake #-}
+unsafeTake n v = unsafeSlice 0 n v
+
+unsafeDrop :: Vector v a => Int -> v a -> v a
+{-# INLINE unsafeDrop #-}
+unsafeDrop n v = unsafeSlice n (length v - n) v
+
 {-# RULES
 
 "slice/new [Vector]" forall i n v p.
@@ -573,6 +625,14 @@ backpermute v is = seq v
                  $ Stream.map (indexM v)
                  $ stream is
 
+unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
+{-# INLINE unsafeBackpermute #-}
+unsafeBackpermute v is = seq v
+                       $ unstream
+                       $ Stream.unbox
+                       $ Stream.map (unsafeIndexM v)
+                       $ stream is
+
 reverse :: (Vector v a) => v a -> v a
 {-# INLINE reverse #-}
 reverse = new . New.reverse . New.unstream . stream
@@ -803,8 +863,29 @@ dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
 dropWhile f = unstream . Stream.dropWhile f . stream
 
 -- | Split the vector in two parts, the first one containing those elements
+-- that satisfy the predicate and the second one those that don't. The
+-- relative order of the elements is preserved at the cost of a (sometimes)
+-- reduced performance compared to 'unstablePartition'.
+partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
+{-# INLINE partition #-}
+partition f = partition_stream f . stream
+
+-- FIXME: Make this inplace-fusible (look at how stable_partition is
+-- implemented in C++)
+
+partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
+{-# INLINE_STREAM partition_stream #-}
+partition_stream f s = s `seq` runST (
+  do
+    (mv1,mv2) <- M.partitionStream f s
+    v1 <- unsafeFreeze mv1
+    v2 <- unsafeFreeze mv2
+    return (v1,v2))
+
+-- | Split the vector in two parts, the first one containing those elements
 -- that satisfy the predicate and the second one those that don't. The order
--- of the elements is not preserved.
+-- of the elements is not preserved but the operation is often faster than
+-- 'partition'.
 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE unstablePartition #-}
 unstablePartition f = unstablePartition_stream f . stream
@@ -826,7 +907,7 @@ unstablePartition_new f (New.New p) = runST (
     mv <- p
     i <- M.unstablePartition f mv
     v <- unsafeFreeze mv
-    return (take i v, drop i v))
+    return (unsafeTake i v, unsafeDrop i v))
 
 {-# RULES
 
@@ -885,9 +966,8 @@ findIndex f = Stream.findIndex f . stream
 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
 {-# INLINE findIndices #-}
 findIndices f = unstream
-              . Stream.map fst
-              . Stream.filter (f . snd)
-              . Stream.indexed
+              . inplace (MStream.map fst . MStream.filter (f . snd)
+                                         . MStream.indexed)
               . stream
 
 -- | Yield 'Just' the index of the first occurence of the given element or
@@ -934,6 +1014,16 @@ foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1 #-}
 foldr1 f = Stream.foldr1 f . stream
 
+-- | Right fold with a strict accumulator
+foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
+{-# INLINE foldr' #-}
+foldr' f z = Stream.foldl' (flip f) z . streamR
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
+{-# INLINE foldr1' #-}
+foldr1' f = Stream.foldl1' (flip f) . streamR
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl #-}
@@ -950,6 +1040,13 @@ ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr #-}
 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
+               $ Stream.indexedR (length xs) $ streamR xs
+
 -- Specialised folds
 -- -----------------
 
@@ -1078,13 +1175,78 @@ scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanl1' #-}
 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
 
+
+-- | Prefix right-to-left scan
+prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE prescanr #-}
+prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
+
+-- | Prefix right-to-left scan with strict accumulator
+prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE prescanr' #-}
+prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
+
+-- | Suffix right-to-left scan
+postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE postscanr #-}
+postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
+
+-- | Suffix right-to-left scan with strict accumulator
+postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE postscanr' #-}
+postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
+
+-- | Haskell-style right-to-left scan
+scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE scanr #-}
+scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
+
+-- | Haskell-style right-to-left scan with strict accumulator
+scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE scanr' #-}
+scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
+
+-- | Right-to-left scan over a non-empty vector
+scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
+{-# INLINE scanr1 #-}
+scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
+
+-- | Right-to-left scan over a non-empty vector with a strict accumulator
+scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
+{-# INLINE scanr1' #-}
+scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
+
 -- Enumeration
 -- -----------
 
+-- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
+-- This operation is usually more efficient than 'enumFromTo'.
+enumFromN :: (Vector v a, Num a) => a -> Int -> v a
+{-# INLINE enumFromN #-}
+enumFromN x n = enumFromStepN x 1 n
+
+-- | Yield a vector of the given length containing the values @x@, @x+y@,
+-- @x+y+y@ etc. This operations is usually more efficient than
+-- 'enumFromThenTo'.
+enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
+{-# INLINE enumFromStepN #-}
+enumFromStepN x y n = elemseq (undefined :: v a) x
+                    $ elemseq (undefined :: v a) y
+                    $ unstream
+                    $ Stream.enumFromStepN  x y n
+
+-- | Enumerate values from @x@ to @y@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromN' instead.
 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
 {-# INLINE enumFromTo #-}
 enumFromTo x y = unstream (Stream.enumFromTo x y)
 
+-- | Enumerate values from @x@ to @y@ with a specific step @z@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromStepN' instead.
 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
 {-# INLINE enumFromThenTo #-}
 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)