Fix INLINE pragmas
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
index e90ce8a..0d9f6cb 100644 (file)
@@ -2,7 +2,7 @@
              TypeFamilies, ScopedTypeVariables #-}
 -- |
 -- Module      : Data.Vector.Generic
--- Copyright   : (c) Roman Leshchinskiy 2008-2009
+-- Copyright   : (c) Roman Leshchinskiy 2008-2010
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
@@ -20,7 +20,7 @@ module Data.Vector.Generic (
   length, null,
 
   -- * Construction
-  empty, singleton, cons, snoc, replicate, generate, (++), copy,
+  empty, singleton, cons, snoc, replicate, generate, (++), force,
 
   -- * Accessing individual elements
   (!), head, last, indexM, headM, lastM,
@@ -53,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,
@@ -69,26 +69,41 @@ module Data.Vector.Generic (
   minIndex, minIndexBy, maxIndex, maxIndexBy,
 
   -- * Unfolding
-  unfoldr,
+  unfoldr, unfoldrN,
 
   -- * Scans
   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,
+  toList, fromList, fromListN,
+
+  -- * Monadic operations
+  replicateM, mapM, mapM_, forM, forM_, zipWithM, zipWithM_, filterM,
+  foldM, foldM', fold1M, fold1M',
+
+  -- * Destructive operations
+  create, modify, copy, unsafeCopy,
 
   -- * Conversion to/from Streams
   stream, unstream, streamR, unstreamR,
 
-  -- * MVector-based initialisation
-  new
+  -- * Recycling support
+  new, clone,
+
+  -- * Utilities for defining Data instances
+  gfoldl, dataCast, mkType
 ) where
 
+import           Data.Vector.Generic.Base
+
 import           Data.Vector.Generic.Mutable ( MVector )
 import qualified Data.Vector.Generic.Mutable as M
 
@@ -101,8 +116,9 @@ import qualified Data.Vector.Fusion.Stream.Monadic as MStream
 import           Data.Vector.Fusion.Stream.Size
 import           Data.Vector.Fusion.Util
 
-import Control.Monad.ST ( runST )
+import Control.Monad.ST ( ST, runST )
 import Control.Monad.Primitive
+import qualified Control.Monad as Monad
 import Prelude hiding ( length, null,
                         replicate, (++),
                         head, last,
@@ -113,72 +129,30 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         all, any, and, or, sum, product, maximum, minimum,
-                        scanl, scanl1,
-                        enumFromTo, enumFromThenTo )
+                        scanl, scanl1, scanr, scanr1,
+                        enumFromTo, enumFromThenTo,
+                        mapM, mapM_ )
 
-#include "vector.h"
-
-type family Mutable (v :: * -> *) :: * -> * -> *
+import Data.Typeable ( Typeable1, gcast1 )
+import Data.Data ( Data, DataType, mkNorepType )
 
--- | Class of immutable vectors.
---
-class MVector (Mutable v) a => Vector v a where
-  -- | Unsafely convert a mutable vector to its immutable version
-  -- without copying. The mutable vector may not be used after
-  -- this operation.
-  unsafeFreeze :: PrimMonad m => Mutable v (PrimState m) a -> m (v a)
-
-  -- | Length of the vector (not fusible!)
-  basicLength      :: v a -> Int
-
-  -- | Yield a part of the vector without copying it. No range checks!
-  basicUnsafeSlice  :: Int -> Int -> v a -> v a
-
-  -- | Yield the element at the given position in a monad. The monad allows us
-  -- to be strict in the vector if we want. Suppose we had
-  --
-  -- > unsafeIndex :: v a -> Int -> a
-  --
-  -- instead. Now, if we wanted to copy a vector, we'd do something like
-  --
-  -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex v i) ...
-  --
-  -- For lazy vectors, the indexing would not be evaluated which means that we
-  -- would retain a reference to the original vector in each element we write.
-  -- This is not what we want!
-  --
-  -- With 'basicUnsafeIndexM', we can do
-  --
-  -- > copy mv v ... = ... case basicUnsafeIndexM v i of
-  -- >                       Box x -> unsafeWrite mv i x ...
-  --
-  -- which does not have this problem because indexing (but not the returned
-  -- element!) is evaluated immediately.
-  --
-  basicUnsafeIndexM  :: Monad m => v a -> Int -> m a
-
-  elemseq :: v a -> a -> b -> b
-
-  {-# INLINE elemseq #-}
-  elemseq _ = \_ x -> x
+#include "vector.h"
 
 -- Fusion
 -- ------
 
 -- | Construct a pure vector from a monadic initialiser 
-new :: Vector v a => New a -> v a
-{-# INLINE new #-}
-new m = new' undefined m
+new :: Vector v a => New a -> v a
+{-# INLINE_STREAM new #-}
+new m = m `seq` runST (unsafeFreeze =<< New.run m)
 
--- | Same as 'new' but with a dummy argument necessary for correctly typing
--- the rule @uninplace@.
---
--- See http://hackage.haskell.org/trac/ghc/ticket/2600
-new' :: Vector v a => v a -> New a -> v a
-{-# INLINE_STREAM new' #-}
-new' _ m = m `seq` runST (do
-                            mv <- New.run m
-                            unsafeFreeze mv)
+clone :: Vector v a => v a -> New v a
+{-# INLINE_STREAM clone #-}
+clone v = v `seq` New.create (
+  do
+    mv <- M.new (length v)
+    unsafeCopy mv v
+    return mv)
 
 -- | Convert a vector to a 'Stream'
 stream :: Vector v a => v a -> Stream a
@@ -200,23 +174,22 @@ unstream s = new (New.unstream s)
 
 {-# RULES
 
-"stream/unstream [Vector]" forall s.
-  stream (new' v (New.unstream s)) = s
+"stream/unstream [Vector]" forall s.
+  stream (new (New.unstream s)) = s
 
-"New.unstream/stream/new [Vector]" forall v p.
-  New.unstream (stream (new' v p)) = p
+"New.unstream/stream [Vector]" forall v.
+  New.unstream (stream v) = clone v
 
- #-}
-
-{-# RULES
+"clone/new [Vector]" forall p.
+  clone (new p) = p
 
 "inplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
-  New.unstream (inplace f (stream (new' v m))) = New.transform f m
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  New.unstream (inplace f (stream (new m))) = New.transform f m
 
 "uninplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
-  stream (new' v (New.transform f m)) = inplace f (stream (new' v m))
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  stream (new (New.transform f m)) = inplace f (stream (new m))
 
  #-}
 
@@ -227,8 +200,6 @@ 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
@@ -242,23 +213,19 @@ unstreamR s = new (New.unstreamR s)
 
 {-# RULES
 
-"streamR/unstreamR [Vector]" forall s.
-  streamR (new' v (New.unstreamR s)) = s
+"streamR/unstreamR [Vector]" forall s.
+  streamR (new (New.unstreamR s)) = s
 
-"New.unstreamR/streamR/new [Vector]" forall p.
-  New.unstreamR (streamR (new' v p)) = p
+"New.unstreamR/streamR/new [Vector]" forall p.
+  New.unstreamR (streamR (new p)) = p
 
- #-}
-
-{-# RULES
+"inplace right [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
 
-"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))
+"uninplace right [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  streamR (new (New.transformR f m)) = inplace f (streamR (new m))
 
  #-}
 
@@ -271,14 +238,21 @@ length v = basicLength v
 
 {-# RULES
 
-"length/unstream [Vector]" forall s.
-  length (new' v (New.unstream s)) = Stream.length s
+"length/unstream [Vector]" forall s.
+  length (new (New.unstream s)) = Stream.length s
 
   #-}
 
 null :: Vector v a => v a -> Bool
-{-# INLINE null #-}
-null v = length v == 0
+{-# INLINE_STREAM null #-}
+null v = basicLength v == 0
+
+{-# RULES
+
+"null/unstream [Vector]" forall s.
+  null (new (New.unstream s)) = Stream.null s
+
+  #-}
 
 -- Construction
 -- ------------
@@ -329,16 +303,9 @@ infixr 5 ++
 v ++ w = unstream (stream v Stream.++ stream w)
 
 -- | Create a copy of a vector. Useful when dealing with slices.
-copy :: Vector v a => v a -> v a
-{-# INLINE_STREAM copy #-}
-copy = unstream . stream
-
-{-# RULES
-
-"copy/unstream [Vector]" forall v s.
-  copy (new' v (New.unstream s)) = new' v (New.unstream s)
-
- #-}
+force :: Vector v a => v a -> v a
+{-# INLINE_STREAM force #-}
+force v = new (clone v)
 
 -- Accessing individual elements
 -- -----------------------------
@@ -379,23 +346,23 @@ unsafeLast v = unsafeIndex v (length v - 1)
 
 {-# RULES
 
-"(!)/unstream [Vector]" forall i s.
-  new' v (New.unstream s) ! i = s Stream.!! i
+"(!)/unstream [Vector]" forall i s.
+  new (New.unstream s) ! i = s Stream.!! i
 
-"head/unstream [Vector]" forall s.
-  head (new' v (New.unstream s)) = Stream.head s
+"head/unstream [Vector]" forall s.
+  head (new (New.unstream s)) = Stream.head s
 
-"last/unstream [Vector]" forall s.
-  last (new' v (New.unstream s)) = Stream.last s
+"last/unstream [Vector]" forall s.
+  last (new (New.unstream s)) = Stream.last s
 
-"unsafeIndex/unstream [Vector]" forall i s.
-  unsafeIndex (new' v (New.unstream s)) i = s Stream.!! i
+"unsafeIndex/unstream [Vector]" forall i s.
+  unsafeIndex (new (New.unstream s)) i = s Stream.!! i
 
-"unsafeHead/unstream [Vector]" forall s.
-  unsafeHead (new' v (New.unstream s)) = Stream.head s
+"unsafeHead/unstream [Vector]" forall s.
+  unsafeHead (new (New.unstream s)) = Stream.head s
 
-"unsafeLast/unstream [Vector]" forall s.
-  unsafeLast (new' v (New.unstream s)) = Stream.last s
+"unsafeLast/unstream [Vector]" forall s.
+  unsafeLast (new (New.unstream s)) = Stream.last s
 
  #-}
 
@@ -445,8 +412,6 @@ unsafeLastM v = unsafeIndexM v (length v - 1)
 -- Subarrays
 -- ---------
 
--- FIXME: slicing doesn't work with the inplace stuff at the moment
-
 -- | Yield a part of the vector without copying it.
 slice :: Vector v a => Int   -- ^ starting index
                     -> Int   -- ^ length
@@ -469,13 +434,14 @@ 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 (delay_inline 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 (delay_inline min n' len)
+                       (delay_inline max 0 (len - n')) v
   where n' = max n 0
         len = length v
 
@@ -507,29 +473,29 @@ unsafeDrop n v = unsafeSlice n (length v - n) v
 
 {-# RULES
 
-"slice/new [Vector]" forall i n p.
-  slice i n (new' v p) = new' v (New.slice i n p)
+"slice/new [Vector]" forall i n p.
+  slice i n (new p) = new (New.slice i n p)
 
-"init/new [Vector]" forall p.
-  init (new' v p) = new' v (New.init p)
+"init/new [Vector]" forall p.
+  init (new p) = new (New.init p)
 
-"tail/new [Vector]" forall p.
-  tail (new' v p) = new' v (New.tail p)
+"tail/new [Vector]" forall p.
+  tail (new p) = new (New.tail p)
 
-"take/new [Vector]" forall n p.
-  take n (new' v p) = new' v (New.take n p)
+"take/new [Vector]" forall n p.
+  take n (new p) = new (New.take n p)
 
-"drop/new [Vector]" forall n p.
-  drop n (new' v p) = new' v (New.drop n p)
+"drop/new [Vector]" forall n p.
+  drop n (new p) = new (New.drop n p)
 
-"unsafeSlice/new [Vector]" forall i n p.
-  unsafeSlice i n (new' v p) = new' v (New.unsafeSlice i n p)
+"unsafeSlice/new [Vector]" forall i n p.
+  unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
 
-"unsafeInit/new [Vector]" forall p.
-  unsafeInit (new' v p) = new' v (New.unsafeInit p)
+"unsafeInit/new [Vector]" forall p.
+  unsafeInit (new p) = new (New.unsafeInit p)
 
-"unsafeTail/new [Vector]" forall p.
-  unsafeTail (new' v p) = new' v (New.unsafeTail p)
+"unsafeTail/new [Vector]" forall p.
+  unsafeTail (new p) = new (New.unsafeTail p)
 
   #-}
 
@@ -538,8 +504,8 @@ unsafeDrop n v = unsafeSlice n (length v - n) v
 
 unsafeAccum_stream
   :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
-{-# INLINE unsafeAccum_stream #-}
-unsafeAccum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
+{-# INLINE_STREAM unsafeAccum_stream #-}
+unsafeAccum_stream f v s = s `seq` modify (\mv -> M.unsafeAccum f mv s) v
 
 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
 {-# INLINE unsafeAccum #-}
@@ -557,8 +523,8 @@ unsafeAccumulate_ f v is xs
   = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
 
 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
-{-# INLINE accum_stream #-}
-accum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
+{-# INLINE_STREAM accum_stream #-}
+accum_stream f v s = s `seq` modify (\mv -> M.accum f mv s) v
 
 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
 {-# INLINE accum #-}
@@ -577,8 +543,8 @@ accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
                                         
 
 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
-{-# INLINE unsafeUpdate_stream #-}
-unsafeUpdate_stream v s = new (New.unsafeUpdate (New.unstream (stream v)) s)
+{-# INLINE_STREAM unsafeUpdate_stream #-}
+unsafeUpdate_stream v s = s `seq` modify (\mv -> M.unsafeUpdate mv s) v
 
 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
 {-# INLINE unsafeUpd #-}
@@ -594,8 +560,8 @@ unsafeUpdate_ v is w
   = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
 
 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
-{-# INLINE update_stream #-}
-update_stream v s = new (New.update (New.unstream (stream v)) s)
+{-# INLINE_STREAM update_stream #-}
+update_stream v s = s `seq` modify (\mv -> M.update mv s) v
 
 (//) :: Vector v a => v a -> [(Int, a)] -> v a
 {-# INLINE (//) #-}
@@ -630,9 +596,10 @@ unsafeBackpermute v is = seq v
                        $ Stream.map (unsafeIndexM v)
                        $ stream is
 
+-- FIXME: make this fuse better, add support for recycling
 reverse :: (Vector v a) => v a -> v a
 {-# INLINE reverse #-}
-reverse = new . New.reverse . New.unstream . stream
+reverse = unstream . streamR
 
 -- Mapping
 -- -------
@@ -860,8 +827,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
@@ -876,19 +864,19 @@ unstablePartition_stream f s = s `seq` runST (
     v2 <- unsafeFreeze mv2
     return (v1,v2))
 
-unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
+unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
 {-# INLINE_STREAM unstablePartition_new #-}
 unstablePartition_new f (New.New p) = runST (
   do
     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
 
-"unstablePartition" forall f p.
-  unstablePartition_stream f (stream (new' v p))
+"unstablePartition" forall f p.
+  unstablePartition_stream f (stream (new p))
     = unstablePartition_new f p
 
   #-}
@@ -942,9 +930,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
@@ -991,6 +978,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 #-}
@@ -1007,6 +1004,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
 -- -----------------
 
@@ -1088,10 +1092,16 @@ minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
 -- Unfolding
 -- ---------
 
+-- | Unfold
 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
 {-# INLINE unfoldr #-}
 unfoldr f = unstream . Stream.unfoldr f
 
+-- | Unfoldr at most @n@ elements.
+unfoldrN  :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
+{-# INLINE unfoldrN #-}
+unfoldrN n f = unstream . Stream.unfoldrN n f
+
 -- Scans
 -- -----
 
@@ -1135,17 +1145,85 @@ 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)
 
+-- Conversion to/from lists
+-- ------------------------
+
 -- | Convert a vector to a list
 toList :: Vector v a => v a -> [a]
 {-# INLINE toList #-}
@@ -1156,3 +1234,142 @@ fromList :: Vector v a => [a] -> v a
 {-# INLINE fromList #-}
 fromList = unstream . Stream.fromList
 
+-- | Convert the first @n@ elements of a list to a vector
+--
+-- > fromListN n xs = fromList (take n xs)
+fromListN :: Vector v a => Int -> [a] -> v a
+{-# INLINE fromListN #-}
+fromListN n = unstream . Stream.fromListN n
+
+unstreamM :: (Vector v a, Monad m) => MStream m a -> m (v a)
+{-# INLINE_STREAM unstreamM #-}
+unstreamM s = do
+                xs <- MStream.toList s
+                return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
+
+-- Monadic operations
+-- ------------------
+
+-- FIXME: specialise various combinators for ST and IO?
+
+-- | Perform the monadic action the given number of times and store the
+-- results in a vector.
+replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a)
+{-# INLINE replicateM #-}
+replicateM n m = fromListN n `Monad.liftM` Monad.replicateM n m
+
+-- | Apply the monadic action to all elements of the vector, yielding a vector
+-- of results
+mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
+{-# INLINE mapM #-}
+mapM f = unstreamM . Stream.mapM f . stream
+
+-- | Apply the monadic action to all elements of a vector and ignore the
+-- results
+mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
+{-# INLINE mapM_ #-}
+mapM_ f = Stream.mapM_ f . stream
+
+-- | Apply the monadic action to all elements of the vector, yielding a vector
+-- of results
+forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
+{-# INLINE forM #-}
+forM as f = mapM f as
+
+-- | Apply the monadic action to all elements of a vector and ignore the
+-- results
+forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
+{-# INLINE forM_ #-}
+forM_ as f = mapM_ f as
+
+-- | Zip the two vectors with the monadic action and yield a vector of results
+zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
+         => (a -> b -> m c) -> v a -> v b -> m (v c)
+{-# INLINE zipWithM #-}
+zipWithM f as bs = unstreamM $ Stream.zipWithM f (stream as) (stream bs)
+
+-- | Zip the two vectors with the monadic action and ignore the results
+zipWithM_ :: (Monad m, Vector v a, Vector v b)
+          => (a -> b -> m c) -> v a -> v b -> m ()
+{-# INLINE zipWithM_ #-}
+zipWithM_ f as bs = Stream.zipWithM_ f (stream as) (stream bs)
+
+-- | Drop elements that do not satisfy the monadic predicate
+filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
+{-# INLINE filterM #-}
+filterM f = unstreamM . Stream.filterM f . stream
+
+-- | Monadic fold
+foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
+{-# INLINE foldM #-}
+foldM m z = Stream.foldM m z . stream
+
+-- | Monadic fold over non-empty vectors
+fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
+{-# INLINE fold1M #-}
+fold1M m = Stream.fold1M m . stream
+
+-- | Monadic fold with strict accumulator
+foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
+{-# INLINE foldM' #-}
+foldM' m z = Stream.foldM' m z . stream
+
+-- | Monad fold over non-empty vectors with strict accumulator
+fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
+{-# INLINE fold1M' #-}
+fold1M' m = Stream.fold1M' m . stream
+
+-- Destructive operations
+-- ----------------------
+
+-- | Destructively initialise a vector.
+create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
+{-# INLINE create #-}
+create p = new (New.create p)
+
+-- | Apply a destructive operation to a vector. The operation modifies a
+-- copy of the vector unless it can be safely performed in place.
+modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
+{-# INLINE modify #-}
+modify p = new . New.modify p . clone
+
+-- | Copy an immutable vector into a mutable one. The two vectors must have
+-- the same length. This is not checked.
+unsafeCopy
+  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
+{-# INLINE unsafeCopy #-}
+unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
+                                         (M.length dst == length src)
+                   $ (dst `seq` src `seq` basicUnsafeCopy dst src)
+           
+-- | Copy an immutable vector into a mutable one. The two vectors must have the
+-- same length.
+copy
+  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
+{-# INLINE copy #-}
+copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
+                                          (M.length dst == length src)
+             $ unsafeCopy dst src
+
+-- Utilities for defining Data instances
+-- -------------------------------------
+
+-- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
+-- list.
+gfoldl :: (Vector v a, Data a)
+       => (forall d b. Data d => c (d -> b) -> d -> c b)
+       -> (forall g. g -> c g)
+       -> v a
+       -> c (v a)
+{-# INLINE gfoldl #-}
+gfoldl f z v = z fromList `f` toList v
+
+mkType :: String -> DataType
+{-# INLINE mkType #-}
+mkType = mkNorepType
+
+dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
+         => (forall d. Data  d => c (t d)) -> Maybe  (c (v a))
+{-# INLINE dataCast #-}
+dataCast f = gcast1 f
+