Comments
[darcs-mirrors/vector.git] / Data / Vector / Fusion / Stream.hs
index 62070ef..bfa0950 100644 (file)
@@ -1,8 +1,8 @@
-{-# LANGUAGE ExistentialQuantification, FlexibleInstances #-}
+{-# LANGUAGE ExistentialQuantification, FlexibleInstances, Rank2Types #-}
 
 -- |
 -- Module      : Data.Vector.Fusion.Stream
--- Copyright   : (c) Roman Leshchinskiy 2008
+-- Copyright   : (c) Roman Leshchinskiy 2008-2009
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
 
 module Data.Vector.Fusion.Stream (
   -- * Types
-  Step(..), Stream, MStream, Id(..),
+  Step(..), Stream, MStream,
+
+  -- * In-place markers
+  inplace, inplace',
 
   -- * Size hints
   size, sized,
@@ -33,8 +36,11 @@ module Data.Vector.Fusion.Stream (
   -- * Substreams
   extract, init, tail, take, drop,
 
-  -- * Mapping and zipping
-  map, zipWith,
+  -- * Mapping
+  map, concatMap,
+  
+  -- * Zipping
+  zipWith, zipWith3,
 
   -- * Filtering
   filter, takeWhile, dropWhile,
@@ -46,22 +52,26 @@ module Data.Vector.Fusion.Stream (
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
   -- * Specialised folds
-  and, or, concatMap,
+  and, or,
 
   -- * Unfolding
   unfoldr,
 
   -- * Scans
   prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl',
+  scanl1, scanl1',
 
   -- * Conversions
   toList, fromList, liftStream,
 
   -- * Monadic combinators
-  mapM_, foldM
+  mapM_, foldM, fold1M, foldM', fold1M'
 ) where
 
 import Data.Vector.Fusion.Stream.Size
+import Data.Vector.Fusion.Util
 import Data.Vector.Fusion.Stream.Monadic ( Step(..) )
 import qualified Data.Vector.Fusion.Stream.Monadic as M
 
@@ -69,30 +79,45 @@ import Prelude hiding ( length, null,
                         replicate, (++),
                         head, last, (!!),
                         init, tail, take, drop,
-                        map, zipWith,
+                        map, concatMap,
+                        zipWith, zipWith3,
                         filter, takeWhile, dropWhile,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
-                        and, or, concatMap,
+                        and, or,
+                        scanl, scanl1,
                         mapM_ )
 
-
--- | Identity monad
-newtype Id a = Id { unId :: a }
-
-instance Functor Id where
-  fmap f (Id x) = Id (f x)
-
-instance Monad Id where
-  return     = Id
-  Id x >>= f = f x
-
 -- | The type of pure streams 
 type Stream = M.Stream Id
 
 -- | Alternative name for monadic streams
 type MStream = M.Stream
 
+inplace :: (forall m. Monad m => M.Stream m a -> M.Stream m a)
+        -> Stream a -> Stream a
+{-# INLINE_STREAM inplace #-}
+inplace f s = f s
+
+inplace' :: (forall m. Monad m => M.Stream m a -> M.Stream m b)
+         -> Stream a -> Stream b
+{-# INLINE_STREAM inplace' #-}
+inplace' f s = f s
+
+{-# RULES
+
+"inplace/inplace [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
+         (g :: forall m. Monad m => MStream m a -> MStream m a)
+         s.
+  inplace f (inplace g s) = inplace (f . g) s
+
+"inplace' [Vector]"
+  forall (f :: forall m. Monad m => MStream m a -> MStream m a).
+  inplace' f = inplace f
+
+  #-}
+
 -- | Convert a pure stream to a monadic stream
 liftStream :: Monad m => Stream a -> M.Stream m a
 {-# INLINE_STREAM liftStream #-}
@@ -136,7 +161,7 @@ singleton = M.singleton
 
 -- | Replicate a value to a given length
 replicate :: Int -> a -> Stream a
-{-# INLINE_STREAM replicate #-}
+{-# INLINE replicate #-}
 replicate = M.replicate
 
 -- | Prepend an element
@@ -203,7 +228,7 @@ drop :: Int -> Stream a -> Stream a
 {-# INLINE drop #-}
 drop = M.drop
 
--- Mapping/zipping
+-- Mapping
 -- ---------------
 
 -- | Map a function over a 'Stream'
@@ -211,11 +236,23 @@ map :: (a -> b) -> Stream a -> Stream b
 {-# INLINE map #-}
 map = M.map
 
+concatMap :: (a -> Stream b) -> Stream a -> Stream b
+{-# INLINE concatMap #-}
+concatMap = M.concatMap
+
+-- Zipping
+-- -------
+
 -- | Zip two 'Stream's with the given function
 zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
 {-# INLINE zipWith #-}
 zipWith = M.zipWith
 
+-- | Zip three 'Stream's with the given function
+zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
+{-# INLINE zipWith3 #-}
+zipWith3 = M.zipWith3
+
 -- Filtering
 -- ---------
 
@@ -305,10 +342,6 @@ or :: Stream Bool -> Bool
 {-# INLINE or #-}
 or = unId . M.or
 
-concatMap :: (a -> Stream b) -> Stream a -> Stream b
-{-# INLINE concatMap #-}
-concatMap = M.concatMap
-
 -- Unfolding
 -- ---------
 
@@ -330,6 +363,37 @@ 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'
+
+-- | Scan over a non-empty 'Stream'
+scanl1 :: (a -> a -> a) -> Stream a -> Stream a
+{-# INLINE scanl1 #-}
+scanl1 = M.scanl1
+
+-- | Scan over a non-empty 'Stream' with a strict accumulator
+scanl1' :: (a -> a -> a) -> Stream a -> Stream a
+{-# INLINE scanl1' #-}
+scanl1' = M.scanl1'
+
+
 -- Comparisons
 -- -----------
 
@@ -379,14 +443,30 @@ instance Ord a => Ord (M.Stream Id a) where
 
 -- | Apply a monadic action to each element of the stream
 mapM_ :: Monad m => (a -> m ()) -> Stream a -> m ()
-{-# INLINE_STREAM mapM_ #-}
+{-# INLINE mapM_ #-}
 mapM_ f = M.mapM_ f . liftStream
 
 -- | Monadic fold
 foldM :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
-{-# INLINE_STREAM foldM #-}
+{-# INLINE foldM #-}
 foldM m z = M.foldM m z . liftStream
 
+-- | Monadic fold over non-empty stream
+fold1M :: Monad m => (a -> a -> m a) -> Stream a -> m a
+{-# INLINE fold1M #-}
+fold1M m = M.fold1M m . liftStream
+
+-- | Monadic fold with strict accumulator
+foldM' :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
+{-# INLINE foldM' #-}
+foldM' m z = M.foldM' m z . liftStream
+
+-- | Monad fold over non-empty stream with strict accumulator
+fold1M' :: Monad m => (a -> a -> m a) -> Stream a -> m a
+{-# INLINE fold1M' #-}
+fold1M' m = M.fold1M' m . liftStream
+
+
 -- Conversions
 -- -----------