Add postscanl and scanl
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 12 Sep 2009 11:09:40 +0000 (11:09 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 12 Sep 2009 11:09:40 +0000 (11:09 +0000)
Data/Vector.hs
Data/Vector/Fusion/Stream.hs
Data/Vector/Fusion/Stream/Monadic.hs
Data/Vector/IVector.hs
Data/Vector/Unboxed.hs

index 230b0cc..fa84be3 100644 (file)
@@ -53,6 +53,8 @@ module Data.Vector (
 
   -- * Scans
   prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl',
 
   -- * Enumeration
   enumFromTo, enumFromThenTo,
@@ -81,6 +83,7 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         and, or, sum, product, minimum, maximum,
+                        scanl,
                         enumFromTo, enumFromThenTo )
 
 import qualified Prelude
@@ -419,6 +422,26 @@ prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE prescanl' #-}
 prescanl' = IV.prescanl'
 
+-- | Suffix scan
+postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE postscanl #-}
+postscanl = IV.postscanl
+
+-- | Suffix scan with strict accumulator
+postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE postscanl' #-}
+postscanl' = IV.postscanl'
+
+-- | Haskell-style scan
+scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE scanl #-}
+scanl = IV.scanl
+
+-- | Haskell-style scan with strict accumulator
+scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE scanl' #-}
+scanl' = IV.scanl'
+
 -- Enumeration
 -- -----------
 
index e0b0e33..fd04d48 100644 (file)
@@ -56,6 +56,8 @@ module Data.Vector.Fusion.Stream (
 
   -- * Scans
   prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl',
 
   -- * Conversions
   toList, fromList, liftStream,
@@ -79,6 +81,7 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         and, or,
+                        scanl,
                         mapM_ )
 
 -- | The type of pure streams 
@@ -332,6 +335,26 @@ prescanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
 {-# INLINE prescanl' #-}
 prescanl' = M.prescanl'
 
+-- | Suffix scan
+postscanl :: (a -> b -> a) -> a -> Stream b -> Stream a
+{-# INLINE postscanl #-}
+postscanl = M.postscanl
+
+-- | Suffix scan with strict accumulator
+postscanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
+{-# INLINE postscanl' #-}
+postscanl' = M.postscanl'
+
+-- | Haskell-style scan
+scanl :: (a -> b -> a) -> a -> Stream b -> Stream a
+{-# INLINE scanl #-}
+scanl = M.scanl
+
+-- | Haskell-style scan with strict accumulator
+scanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
+{-# INLINE scanl' #-}
+scanl' = M.scanl'
+
 -- Comparisons
 -- -----------
 
index d3ca985..c31eae5 100644 (file)
@@ -57,6 +57,8 @@ module Data.Vector.Fusion.Stream.Monadic (
 
   -- * Scans
   prescanl, prescanlM, prescanl', prescanlM',
+  postscanl, postscanlM, postscanl', postscanlM',
+  scanl, scanlM, scanl', scanlM',
 
   -- * Conversions
   toList, fromList
@@ -74,7 +76,8 @@ import Prelude hiding ( length, null,
                         filter, takeWhile, dropWhile,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
-                        and, or )
+                        and, or,
+                        scanl )
 import qualified Prelude
 
 -- | Result of taking a single step in a stream
@@ -788,6 +791,67 @@ prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
                       Skip    s' -> return $ Skip (s', x)
                       Done       -> return Done
 
+-- | Suffix scan
+postscanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+{-# INLINE postscanl #-}
+postscanl f = postscanlM (\a b -> return (f a b))
+
+-- | Suffix scan with a monadic operator
+postscanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+{-# INLINE_STREAM postscanlM #-}
+postscanlM f z (Stream step s sz) = Stream step' (s,z) sz
+  where
+    {-# INLINE step' #-}
+    step' (s,x) = do
+                    r <- step s
+                    case r of
+                      Yield y s' -> do
+                                      z <- f x y
+                                      return $ Yield z (s',z)
+                      Skip    s' -> return $ Skip (s',x)
+                      Done       -> return Done
+
+-- | Suffix scan with strict accumulator
+postscanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+{-# INLINE postscanl' #-}
+postscanl' f = postscanlM' (\a b -> return (f a b))
+
+-- | Suffix scan with strict acccumulator and a monadic operator
+postscanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+{-# INLINE_STREAM postscanlM' #-}
+postscanlM' f z (Stream step s sz) = z `seq` Stream step' (s,z) sz
+  where
+    {-# INLINE step' #-}
+    step' (s,x) = x `seq`
+                  do
+                    r <- step s
+                    case r of
+                      Yield y s' -> do
+                                      z <- f x y
+                                      z `seq` return (Yield z (s',z))
+                      Skip    s' -> return $ Skip (s',x)
+                      Done       -> return Done
+
+-- | Haskell-style scan
+scanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+{-# INLINE scanl #-}
+scanl f = scanlM (\a b -> return (f a b))
+
+-- | Haskell-style scan with a monadic operator
+scanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+{-# INLINE scanlM #-}
+scanlM f z s = z `cons` postscanlM f z s
+
+-- | Haskell-style scan with strict accumulator
+scanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+{-# INLINE scanl' #-}
+scanl' f = scanlM' (\a b -> return (f a b))
+
+-- | Haskell-style scan with strict accumulator and a monadic operator
+scanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+{-# INLINE scanlM' #-}
+scanlM' f z s = z `seq` (z `cons` postscanlM f z s)
+
 -- Conversions
 -- -----------
 
index 444674c..4832f60 100644 (file)
@@ -59,6 +59,8 @@ module Data.Vector.IVector (
 
   -- * Scans
   prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl',
 
   -- * Enumeration
   enumFromTo, enumFromThenTo,
@@ -103,6 +105,7 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         and, or, sum, product, maximum, minimum,
+                        scanl,
                         enumFromTo, enumFromThenTo )
 
 -- | Class of immutable vectors.
@@ -633,6 +636,45 @@ inplace_prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
 
  #-}
 
+-- | Suffix scan
+postscanl :: (IVector v a, IVector v b) => (a -> b -> a) -> a -> v b -> v a
+{-# INLINE postscanl #-}
+postscanl f z = unstream . Stream.postscanl f z . stream
+
+inplace_postscanl :: IVector v a => (a -> a -> a) -> a -> v a -> v a
+{-# INLINE inplace_postscanl #-}
+inplace_postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
+
+{-# RULES
+
+"postscanl -> inplace_postscanl [IVector]" postscanl = inplace_postscanl
+
+ #-}
+
+-- | Suffix scan with strict accumulator
+postscanl' :: (IVector v a, IVector v b) => (a -> b -> a) -> a -> v b -> v a
+{-# INLINE postscanl' #-}
+postscanl' f z = unstream . Stream.postscanl' f z . stream
+
+inplace_postscanl' :: IVector v a => (a -> a -> a) -> a -> v a -> v a
+{-# INLINE inplace_postscanl' #-}
+inplace_postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
+
+{-# RULES
+
+"postscanl' -> inplace_postscanl' [IVector]" postscanl' = inplace_postscanl'
+
+ #-}
+
+-- | Haskell-style scan
+scanl :: (IVector v a, IVector v b) => (a -> b -> a) -> a -> v b -> v a
+{-# INLINE scanl #-}
+scanl f z = unstream . Stream.scanl f z . stream
+
+-- | Haskell-style scan with strict accumulator
+scanl' :: (IVector v a, IVector v b) => (a -> b -> a) -> a -> v b -> v a
+{-# INLINE scanl' #-}
+scanl' f z = unstream . Stream.scanl' f z . stream
 
 -- Enumeration
 -- -----------
index 2d7e052..e0b628c 100644 (file)
@@ -53,6 +53,8 @@ module Data.Vector.Unboxed (
 
   -- * Scans
   prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl',
 
   -- * Enumeration
   enumFromTo, enumFromThenTo,
@@ -82,6 +84,7 @@ import Prelude hiding ( length, null,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         and, or, sum, product, minimum, maximum,
+                        scanl,
                         enumFromTo, enumFromThenTo )
 
 import qualified Prelude
@@ -390,6 +393,26 @@ prescanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE prescanl' #-}
 prescanl' = IV.prescanl'
 
+-- | Suffix scan
+postscanl :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE postscanl #-}
+postscanl = IV.postscanl
+
+-- | Suffix scan with strict accumulator
+postscanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE postscanl' #-}
+postscanl' = IV.postscanl'
+
+-- | Haskell-style scan
+scanl :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE scanl #-}
+scanl = IV.scanl
+
+-- | Haskell-style scan with strict accumulator
+scanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
+{-# INLINE scanl' #-}
+scanl' = IV.scanl'
+
 -- Enumeration
 -- -----------