phases.h -> vector.h
[darcs-mirrors/vector.git] / Data / Vector / Fusion / Stream / Monadic.hs
index 7aeaa44..c94c238 100644 (file)
@@ -1,9 +1,21 @@
-{-# LANGUAGE ExistentialQuantification #-}
-
-#include "phases.h"
+{-# LANGUAGE ExistentialQuantification, Rank2Types #-}
+
+-- |
+-- Module      : Data.Vector.Fusion.Stream.Monadic
+-- Copyright   : (c) Roman Leshchinskiy 2008-2009
+-- License     : BSD-style
+--
+-- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
+-- Stability   : experimental
+-- Portability : non-portable
+--
+-- Monadic streams
+--
+
+#include "vector.h"
 
 module Data.Vector.Fusion.Stream.Monadic (
-  Stream(..),
+  Stream(..), Step(..),
 
   -- * Size hints
   size, sized,
@@ -20,8 +32,11 @@ module Data.Vector.Fusion.Stream.Monadic (
   -- * Substreams
   extract, init, tail, take, drop,
 
-  -- * Mapping and zipping
-  map, mapM, mapM_, zipWith, zipWithM,
+  -- * Mapping
+  map, mapM, mapM_, trans, unbox, concatMap,
+  
+  -- * Zipping
+  zipWith, zipWithM, zipWith3, zipWith3M,
 
   -- * Filtering
   filter, filterM, takeWhile, takeWhileM, dropWhile, dropWhileM,
@@ -30,33 +45,56 @@ module Data.Vector.Fusion.Stream.Monadic (
   elem, notElem, find, findM, findIndex, findIndexM,
 
   -- * Folding
-  foldl, foldlM, foldM, foldl1, foldl1M,
-  foldl', foldlM', foldl1', foldl1M',
+  foldl, foldlM, foldl1, foldl1M, foldM, fold1M,
+  foldl', foldlM', foldl1', foldl1M', foldM', fold1M',
   foldr, foldrM, foldr1, foldr1M,
 
+  -- * Specialised folds
+  and, or, concatMapM,
+
   -- * Unfolding
-  unfold, unfoldM,
+  unfoldr, unfoldrM,
 
   -- * Scans
   prescanl, prescanlM, prescanl', prescanlM',
+  postscanl, postscanlM, postscanl', postscanlM',
+  scanl, scanlM, scanl', scanlM',
+  scanl1, scanl1M, scanl1', scanl1M',
+
+  -- * Enumerations
+  enumFromTo,
 
+  -- * Conversions
   toList, fromList
 ) where
 
-import Data.Vector.Fusion.Stream.Step
 import Data.Vector.Fusion.Stream.Size
+import Data.Vector.Fusion.Util ( Box(..) )
 
 import Control.Monad  ( liftM )
 import Prelude hiding ( length, null,
                         replicate, (++),
                         head, last, (!!),
                         init, tail, take, drop,
-                        map, mapM, mapM_, zipWith,
+                        map, mapM, mapM_, concatMap,
+                        zipWith, zipWith3,
                         filter, takeWhile, dropWhile,
                         elem, notElem,
-                        foldl, foldl1, foldr, foldr1 )
+                        foldl, foldl1, foldr, foldr1,
+                        and, or,
+                        scanl, scanl1,
+                        enumFromTo, enumFromThenTo )
 import qualified Prelude
 
+import Data.Int  ( Int8, Int16, Int32, Int64 )
+import Data.Word ( Word8, Word16, Word32, Word, Word64 )
+
+-- | Result of taking a single step in a stream
+data Step s a = Yield a s  -- ^ a new element and a new seed
+              | Skip    s  -- ^ just a new seed
+              | Done       -- ^ end of stream
+
+-- | Monadic streams
 data Stream m a = forall s. Stream (s -> m (Step s a)) s Size
 
 -- | 'Size' hint of a 'Stream'
@@ -96,7 +134,7 @@ singleton :: Monad m => a -> Stream m a
 {-# INLINE_STREAM singleton #-}
 singleton x = Stream (return . step) True (Exact 1)
   where
-    {-# INLINE step #-}
+    {-# INLINE_INNER step #-}
     step True  = Yield x False
     step False = Done
 
@@ -105,7 +143,7 @@ replicate :: Monad m => Int -> a -> Stream m a
 {-# INLINE_STREAM replicate #-}
 replicate n x = Stream (return . step) n (Exact (max n 0))
   where
-    {-# INLINE step #-}
+    {-# INLINE_INNER step #-}
     step i | i > 0     = Yield x (i-1)
            | otherwise = Done
 
@@ -125,6 +163,7 @@ infixr 5 ++
 {-# INLINE_STREAM (++) #-}
 Stream stepa sa na ++ Stream stepb sb nb = Stream step (Left sa) (na + nb)
   where
+    {-# INLINE_INNER step #-}
     step (Left  sa) = do
                         r <- stepa sa
                         case r of
@@ -175,7 +214,17 @@ last (Stream step s _) = last_loop0 s
 -- | Element at the given position
 (!!) :: Monad m => Stream m a -> Int -> m a
 {-# INLINE (!!) #-}
-s !! i = head (drop i s)
+Stream step s _ !! i | i < 0     = errorNegativeIndex "!!"
+                     | otherwise = loop s i
+  where
+    loop s i = i `seq`
+               do
+                 r <- step s
+                 case r of
+                   Yield x s' | i == 0    -> return x
+                              | otherwise -> loop s' (i-1)
+                   Skip    s'             -> loop s' i
+                   Done                   -> errorIndexOutOfRange "!!"
 
 -- Substreams
 -- ----------
@@ -192,12 +241,12 @@ init :: Monad m => Stream m a -> Stream m a
 {-# INLINE_STREAM init #-}
 init (Stream step s sz) = Stream step' (Nothing, s) (sz - 1)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (Nothing, s) = liftM (\r ->
                            case r of
                              Yield x s' -> Skip (Just x,  s')
                              Skip    s' -> Skip (Nothing, s')
-                             Done       -> Done  -- FIXME: should be an error
+                             Done       -> errorEmptyStream "init"
                          ) (step s)
 
     step' (Just x,  s) = liftM (\r -> 
@@ -212,12 +261,12 @@ tail :: Monad m => Stream m a -> Stream m a
 {-# INLINE_STREAM tail #-}
 tail (Stream step s sz) = Stream step' (Left s) (sz - 1)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (Left  s) = liftM (\r ->
                         case r of
                           Yield x s' -> Skip (Right s')
                           Skip    s' -> Skip (Left  s')
-                          Done       -> Done    -- FIXME: should be error?
+                          Done       -> errorEmptyStream "tail"
                       ) (step s)
 
     step' (Right s) = liftM (\r ->
@@ -232,7 +281,7 @@ take :: Monad m => Int -> Stream m a -> Stream m a
 {-# INLINE_STREAM take #-}
 take n (Stream step s sz) = Stream step' (s, 0) (smaller (Exact n) sz)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (s, i) | i < n = liftM (\r ->
                              case r of
                                Yield x s' -> Yield x (s', i+1)
@@ -246,7 +295,7 @@ drop :: Monad m => Int -> Stream m a -> Stream m a
 {-# INLINE_STREAM drop #-}
 drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (s, Just i) | i > 0 = liftM (\r ->
                                 case r of
                                    Yield x s' -> Skip (s', Just (i-1))
@@ -263,22 +312,24 @@ drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
                            ) (step s)
                      
 
--- Mapping/zipping
--- ---------------
+-- Mapping
+-- -------
 
 instance Monad m => Functor (Stream m) where
   {-# INLINE fmap #-}
   fmap = map
 
+-- | Map a function over a 'Stream'
 map :: Monad m => (a -> b) -> Stream m a -> Stream m b
 {-# INLINE map #-}
 map f = mapM (return . f)
 
+-- | Map a monadic function over a 'Stream'
 mapM :: Monad m => (a -> m b) -> Stream m a -> Stream m b
 {-# INLINE_STREAM mapM #-}
 mapM f (Stream step s n) = Stream step' s n
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' s = do
                 r <- step s
                 case r of
@@ -286,6 +337,7 @@ mapM f (Stream step s n) = Stream step' s n
                   Skip    s' -> return (Skip    s')
                   Done       -> return Done
 
+-- | Execute a monadic action for each element of the 'Stream'
 mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
 {-# INLINE_STREAM mapM_ #-}
 mapM_ m (Stream step s _) = mapM_go s
@@ -297,18 +349,39 @@ mapM_ m (Stream step s _) = mapM_go s
                     Skip    s' -> mapM_go s'
                     Done       -> return ()
 
+-- | Transform a 'Stream' to use a different monad
+trans :: (Monad m, Monad m') => (forall a. m a -> m' a)
+                             -> Stream m a -> Stream m' a
+{-# INLINE_STREAM trans #-}
+trans f (Stream step s n) = Stream (f . step) s n
+
+unbox :: Monad m => Stream m (Box a) -> Stream m a
+{-# INLINE_STREAM unbox #-}
+unbox (Stream step s n) = Stream step' s n
+  where
+    {-# INLINE_INNER step' #-}
+    step' s = do
+                r <- step s
+                case r of
+                  Yield (Box x) s' -> return $ Yield x s'
+                  Skip          s' -> return $ Skip    s'
+                  Done             -> return $ Done
+
+-- Zipping
+-- -------
+
 -- | Zip two 'Stream's with the given function
 zipWith :: Monad m => (a -> b -> c) -> Stream m a -> Stream m b -> Stream m c
 {-# INLINE zipWith #-}
 zipWith f = zipWithM (\a b -> return (f a b))
 
--- | Zip two 'Stream's with the given function
+-- | Zip two 'Stream's with the given monadic function
 zipWithM :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> Stream m c
 {-# INLINE_STREAM zipWithM #-}
 zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
   = Stream step (sa, sb, Nothing) (smaller na nb)
   where
-    {-# INLINE step #-}
+    {-# INLINE_INNER step #-}
     step (sa, sb, Nothing) = liftM (\r ->
                                case r of
                                  Yield x sa' -> Skip (sa', sb, Just x)
@@ -326,6 +399,39 @@ zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
                                  Skip    sb' -> return $ Skip (sa, sb', Just x)
                                  Done        -> return $ Done
 
+-- | Zip three 'Stream's with the given function
+zipWith3 :: Monad m => (a -> b -> c -> d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d
+{-# INLINE zipWith3 #-}
+zipWith3 f = zipWith3M (\a b c -> return (f a b c))
+
+-- | Zip three 'Stream's with the given monadic function
+zipWith3M :: Monad m => (a -> b -> c -> m d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d
+{-# INLINE_STREAM zipWith3M #-}
+zipWith3M f (Stream stepa sa na) (Stream stepb sb nb) (Stream stepc sc nc)
+  = Stream step (sa, sb, sc, Nothing) (smaller na (smaller nb nc))
+  where
+    {-# INLINE_INNER step #-}
+    step (sa, sb, sc, Nothing) = do
+        r <- stepa sa
+        return $ case r of
+            Yield x sa' -> Skip (sa', sb, sc, Just (x, Nothing))
+            Skip    sa' -> Skip (sa', sb, sc, Nothing)
+            Done        -> Done
+
+    step (sa, sb, sc, Just (x, Nothing)) = do
+        r <- stepb sb
+        return $ case r of
+            Yield y sb' -> Skip (sa, sb', sc, Just (x, Just y))
+            Skip    sb' -> Skip (sa, sb', sc, Just (x, Nothing))
+            Done        -> Done
+
+    step (sa, sb, sc, Just (x, Just y)) = do
+        r <- stepc sc
+        case r of
+            Yield z sc' -> f x y z >>= (\res -> return $ Yield res (sa, sb, sc', Nothing))
+            Skip    sc' -> return $ Skip (sa, sb, sc', Just (x, Just y))
+            Done        -> return $ Done
+
 -- Filtering
 -- ---------
 
@@ -334,12 +440,12 @@ filter :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
 {-# INLINE filter #-}
 filter f = filterM (return . f)
 
--- | Drop elements which do not satisfy the predicate
+-- | Drop elements which do not satisfy the monadic predicate
 filterM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
 {-# INLINE_STREAM filterM #-}
 filterM f (Stream step s n) = Stream step' s (toMax n)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' s = do
                 r <- step s
                 case r of
@@ -355,12 +461,12 @@ takeWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
 {-# INLINE takeWhile #-}
 takeWhile f = takeWhileM (return . f)
 
--- | Longest prefix of elements that satisfy the predicate
+-- | Longest prefix of elements that satisfy the monadic predicate
 takeWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
 {-# INLINE_STREAM takeWhileM #-}
 takeWhileM f (Stream step s n) = Stream step' s (toMax n)
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' s = do
                 r <- step s
                 case r of
@@ -370,14 +476,14 @@ takeWhileM f (Stream step s n) = Stream step' s (toMax n)
                   Skip    s' -> return $ Skip s'
                   Done       -> return $ Done
 
-
+-- | Drop the longest prefix of elements that satisfy the predicate
 dropWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
 {-# INLINE dropWhile #-}
 dropWhile f = dropWhileM (return . f)
 
 data DropWhile s a = DropWhile_Drop s | DropWhile_Yield a s | DropWhile_Next s
 
--- | Drop the longest prefix of elements that satisfy the predicate
+-- | Drop the longest prefix of elements that satisfy the monadic predicate
 dropWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
 {-# INLINE_STREAM dropWhileM #-}
 dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
@@ -385,7 +491,7 @@ dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
     -- NOTE: we jump through hoops here to have only one Yield; local data
     -- declarations would be nice!
 
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (DropWhile_Drop s)
       = do
           r <- step s
@@ -430,12 +536,14 @@ notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
 {-# INLINE notElem #-}
 notElem x s = liftM not (elem x s)
 
+-- | Yield 'Just' the first element that satisfies the predicate or 'Nothing'
+-- if no such element exists.
 find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
 {-# INLINE find #-}
 find f = findM (return . f)
 
--- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
--- such element exists.
+-- | Yield 'Just' the first element that satisfies the monadic predicate or
+-- 'Nothing' if no such element exists.
 findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
 {-# INLINE_STREAM findM #-}
 findM f (Stream step s _) = find_loop s
@@ -450,12 +558,14 @@ findM f (Stream step s _) = find_loop s
                       Skip    s' -> find_loop s'
                       Done       -> return Nothing
 
+-- | Yield 'Just' the index of the first element that satisfies the predicate
+-- or 'Nothing' if no such element exists.
 findIndex :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe Int)
 {-# INLINE_STREAM findIndex #-}
 findIndex f = findIndexM (return . f)
 
--- | Yield 'Just' the index of the first element matching the predicate or
--- 'Nothing' if no such element exists.
+-- | Yield 'Just' the index of the first element that satisfies the monadic
+-- predicate or 'Nothing' if no such element exists.
 findIndexM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe Int)
 {-# INLINE_STREAM findIndexM #-}
 findIndexM f (Stream step s _) = findIndex_loop s 0
@@ -473,10 +583,12 @@ findIndexM f (Stream step s _) = findIndex_loop s 0
 -- Folding
 -- -------
 
+-- | Left fold
 foldl :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
 {-# INLINE foldl #-}
 foldl f = foldlM (\a b -> return (f a b))
 
+-- | Left fold with a monadic operator
 foldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE_STREAM foldlM #-}
 foldlM m z (Stream step s _) = foldlM_go z s
@@ -488,14 +600,17 @@ foldlM m z (Stream step s _) = foldlM_go z s
                         Skip    s' -> foldlM_go z s'
                         Done       -> return z
 
+-- | Same as 'foldlM'
 foldM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE foldM #-}
 foldM = foldlM
 
+-- | Left fold over a non-empty 'Stream'
 foldl1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldl1 #-}
 foldl1 f = foldl1M (\a b -> return (f a b))
 
+-- | Left fold over a non-empty 'Stream' with a monadic operator
 foldl1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldl1M #-}
 foldl1M f (Stream step s sz) = foldl1M_go s
@@ -507,10 +622,17 @@ foldl1M f (Stream step s sz) = foldl1M_go s
                        Skip    s' -> foldl1M_go s'
                        Done       -> errorEmptyStream "foldl1M"
 
+-- | Same as 'foldl1M'
+fold1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+{-# INLINE fold1M #-}
+fold1M = foldl1M
+
+-- | Left fold with a strict accumulator
 foldl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
 {-# INLINE foldl' #-}
 foldl' f = foldlM' (\a b -> return (f a b))
 
+-- | Left fold with a strict accumulator and a monadic operator
 foldlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE_STREAM foldlM' #-}
 foldlM' m z (Stream step s _) = foldlM'_go z s
@@ -523,10 +645,18 @@ foldlM' m z (Stream step s _) = foldlM'_go z s
                          Skip    s' -> foldlM'_go z s'
                          Done       -> return z
 
+-- | Same as 'foldlM''
+foldM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
+{-# INLINE foldM' #-}
+foldM' = foldlM'
+
+-- | Left fold over a non-empty 'Stream' with a strict accumulator
 foldl1' :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldl1' #-}
 foldl1' f = foldl1M' (\a b -> return (f a b))
 
+-- | Left fold over a non-empty 'Stream' with a strict accumulator and a
+-- monadic operator
 foldl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldl1M' #-}
 foldl1M' f (Stream step s sz) = foldl1M'_go s
@@ -538,10 +668,17 @@ foldl1M' f (Stream step s sz) = foldl1M'_go s
                         Skip    s' -> foldl1M'_go s'
                         Done       -> errorEmptyStream "foldl1M'"
 
+-- | Same as 'foldl1M''
+fold1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+{-# INLINE fold1M' #-}
+fold1M' = foldl1M'
+
+-- | Right fold
 foldr :: Monad m => (a -> b -> b) -> b -> Stream m a -> m b
 {-# INLINE foldr #-}
 foldr f = foldrM (\a b -> return (f a b))
 
+-- | Right fold with a monadic operator
 foldrM :: Monad m => (a -> b -> m b) -> b -> Stream m a -> m b
 {-# INLINE_STREAM foldrM #-}
 foldrM f z (Stream step s _) = foldrM_go s
@@ -553,10 +690,12 @@ foldrM f z (Stream step s _) = foldrM_go s
                       Skip    s' -> foldrM_go s'
                       Done       -> return z
 
+-- | Right fold over a non-empty stream
 foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldr1 #-}
 foldr1 f = foldr1M (\a b -> return (f a b))
 
+-- | Right fold over a non-empty stream with a monadic operator
 foldr1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldr1M #-}
 foldr1M f (Stream step s _) = foldr1M_go0 s
@@ -575,19 +714,70 @@ foldr1M f (Stream step s _) = foldr1M_go0 s
                           Skip    s' -> foldr1M_go1 x s'
                           Done       -> return x
 
+-- Specialised folds
+-- -----------------
+
+and :: Monad m => Stream m Bool -> m Bool
+{-# INLINE_STREAM and #-}
+and (Stream step s _) = and_go s
+  where
+    and_go s = do
+                 r <- step s
+                 case r of
+                   Yield False _  -> return False
+                   Yield True  s' -> and_go s'
+                   Skip        s' -> and_go s'
+                   Done           -> return True
+
+or :: Monad m => Stream m Bool -> m Bool
+{-# INLINE_STREAM or #-}
+or (Stream step s _) = or_go s
+  where
+    or_go s = do
+                r <- step s
+                case r of
+                  Yield False s' -> or_go s'
+                  Yield True  _  -> return True
+                  Skip        s' -> or_go s'
+                  Done           -> return False
+
+concatMap :: Monad m => (a -> Stream m b) -> Stream m a -> Stream m b
+{-# INLINE concatMap #-}
+concatMap f = concatMapM (return . f)
+
+concatMapM :: Monad m => (a -> m (Stream m b)) -> Stream m a -> Stream m b
+{-# INLINE_STREAM concatMapM #-}
+concatMapM f (Stream step s _) = Stream concatMap_go (Left s) Unknown
+  where
+    concatMap_go (Left s) = do
+        r <- step s
+        case r of
+            Yield a s' -> do
+                b_stream <- f a
+                return $ Skip (Right (b_stream, s'))
+            Skip    s' -> return $ Skip (Left s')
+            Done       -> return Done
+    concatMap_go (Right (Stream inner_step inner_s sz, s)) = do
+        r <- inner_step inner_s
+        case r of
+            Yield b inner_s' -> return $ Yield b (Right (Stream inner_step inner_s' sz, s))
+            Skip    inner_s' -> return $ Skip (Right (Stream inner_step inner_s' sz, s))
+            Done             -> return $ Skip (Left s)
+
 -- Unfolding
 -- ---------
 
 -- | Unfold
-unfold :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
-{-# INLINE_STREAM unfold #-}
-unfold f = unfoldM (return . f)
-
-unfoldM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
-{-# INLINE_STREAM unfoldM #-}
-unfoldM f s = Stream step s Unknown
+unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
+{-# INLINE_STREAM unfoldr #-}
+unfoldr f = unfoldrM (return . f)
+
+-- | Unfold with a monadic function
+unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
+{-# INLINE_STREAM unfoldrM #-}
+unfoldrM f s = Stream step s Unknown
   where
-    {-# INLINE step #-}
+    {-# INLINE_INNER step #-}
     step s = liftM (\r ->
                case r of
                  Just (x, s') -> Yield x s'
@@ -602,12 +792,12 @@ prescanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
 {-# INLINE prescanl #-}
 prescanl f = prescanlM (\a b -> return (f a b))
 
--- | Prefix scan
+-- | Prefix scan with a monadic operator
 prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
 {-# INLINE_STREAM prescanlM #-}
 prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (s,x) = do
                     r <- step s
                     case r of
@@ -617,18 +807,17 @@ prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
                       Skip    s' -> return $ Skip (s', x)
                       Done       -> return Done
 
-
 -- | Prefix scan with strict accumulator
 prescanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
 {-# INLINE prescanl' #-}
 prescanl' f = prescanlM' (\a b -> return (f a b))
 
--- | Prefix scan with strict accumulator
+-- | Prefix scan with strict accumulator and a monadic operator
 prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
 {-# INLINE_STREAM prescanlM' #-}
 prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
   where
-    {-# INLINE step' #-}
+    {-# INLINE_INNER step' #-}
     step' (s,x) = x `seq`
                   do
                     r <- step s
@@ -639,13 +828,206 @@ 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_INNER 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_INNER 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)
+
+-- | Scan over a non-empty 'Stream'
+scanl1 :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a
+{-# INLINE scanl1 #-}
+scanl1 f = scanl1M (\x y -> return (f x y))
+
+-- | Scan over a non-empty 'Stream' with a monadic operator
+scanl1M :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a
+{-# INLINE_STREAM scanl1M #-}
+scanl1M f (Stream step s sz) = Stream step' (s, Nothing) sz
+  where
+    {-# INLINE_INNER step' #-}
+    step' (s, Nothing) = do
+                           r <- step s
+                           case r of
+                             Yield x s' -> return $ Yield x (s', Just x)
+                             Skip    s' -> return $ Skip (s', Nothing)
+                             Done       -> errorEmptyStream "scanl1M"
+
+    step' (s, Just x) = do
+                          r <- step s
+                          case r of
+                            Yield y s' -> do
+                                            z <- f x y
+                                            return $ Yield z (s', Just z)
+                            Skip    s' -> return $ Skip (s', Just x)
+                            Done       -> return Done
+
+-- | Scan over a non-empty 'Stream' with a strict accumulator
+scanl1' :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a
+{-# INLINE scanl1' #-}
+scanl1' f = scanl1M' (\x y -> return (f x y))
+
+-- | Scan over a non-empty 'Stream' with a strict accumulator and a monadic
+-- operator
+scanl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a
+{-# INLINE_STREAM scanl1M' #-}
+scanl1M' f (Stream step s sz) = Stream step' (s, Nothing) sz
+  where
+    {-# INLINE_INNER step' #-}
+    step' (s, Nothing) = do
+                           r <- step s
+                           case r of
+                             Yield x s' -> x `seq` return (Yield x (s', Just x))
+                             Skip    s' -> return $ Skip (s', Nothing)
+                             Done       -> errorEmptyStream "scanl1M"
+
+    step' (s, Just x) = x `seq`
+                        do
+                          r <- step s
+                          case r of
+                            Yield y s' -> do
+                                            z <- f x y
+                                            z `seq` return (Yield z (s', Just z))
+                            Skip    s' -> return $ Skip (s', Just x)
+                            Done       -> return Done
+
+-- Enumerations
+-- ------------
+
+-- | Enumerate values from @x@ to @y@
+enumFromTo :: (Enum a, Monad m) => a -> a -> Stream m a
+{-# INLINE_STREAM enumFromTo #-}
+enumFromTo x y = fromList [x .. y]
+
+enumFromTo_small :: (Enum a, Ord a, Monad m) => a -> a -> Stream m a
+{-# INLINE_STREAM enumFromTo_small #-}
+enumFromTo_small x y = Stream step x (Exact n)
+  where
+    n = max (fromEnum y - fromEnum x + 1) 0
+
+    {-# INLINE_INNER step #-}
+    step x | x <= y    = return $ Yield x (succ x)
+           | otherwise = return $ Done
+
+{-# RULES
+
+"enumFromTo<Int> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Int -> Int -> Stream m Int
+
+"enumFromTo<Char> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Char -> Char -> Stream m Char
+
+"enumFromTo<Int8> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Int8 -> Int8 -> Stream m Int8
+
+"enumFromTo<Int16> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Int16 -> Int16 -> Stream m Int16
+
+"enumFromTo<Int32> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Int32 -> Int32 -> Stream m Int32
+
+"enumFromTo<Word8> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Word8 -> Word8 -> Stream m Word8
+
+"enumFromTo<Word16> [Stream]"
+  enumFromTo = enumFromTo_small :: Monad m => Word16 -> Word16 -> Stream m Word16
+
+  #-}
+
+enumFromTo_big :: (Enum a, Integral a, Monad m) => a -> a -> Stream m a
+{-# INLINE_STREAM enumFromTo_big #-}
+enumFromTo_big x y = Stream step x (Exact n)
+  where
+    n | x > y = 0
+      | y - x < fromIntegral (maxBound :: Int) = fromIntegral (y-x+1)
+      | otherwise = error $ "vector.enumFromTo_big: Array too large"
+
+    {-# INLINE_INNER step #-}
+    step x | x <= y    = return $ Yield x (succ x)
+           | otherwise = return $ Done
+
+{-# RULES
+
+
+"enumFromTo<Int64> [Stream]"
+  enumFromTo = enumFromTo_big :: Monad m => Int64 -> Int64 -> Stream m Int64
+
+"enumFromTo<Word32> [Stream]"
+  enumFromTo = enumFromTo_big :: Monad m => Word32 -> Word32 -> Stream m Word32
+
+"enumFromTo<Word64> [Stream]"
+  enumFromTo = enumFromTo_big :: Monad m => Word64 -> Word64 -> Stream m Word64
+
+"enumFromTo<Integer> [Stream]"
+  enumFromTo = enumFromTo_big :: Monad m => Integer -> Integer -> Stream m Integer
+
+  #-}
+
+
+
 -- Conversions
 -- -----------
 
+-- | Convert a 'Stream' to a list
 toList :: Monad m => Stream m a -> m [a]
 {-# INLINE toList #-}
 toList = foldr (:) []
 
+-- | Convert a list to a 'Stream'
 fromList :: Monad m => [a] -> Stream m a
 {-# INLINE_STREAM fromList #-}
 fromList xs = Stream step xs Unknown
@@ -654,7 +1036,16 @@ fromList xs = Stream step xs Unknown
     step []     = return Done
 
 
+streamError :: String -> String -> a
+streamError fn msg = error $ "Data.Vector.Fusion.Stream.Monadic."
+                             Prelude.++ fn Prelude.++ ": " Prelude.++ msg
+
 errorEmptyStream :: String -> a
-errorEmptyStream s = error $ "Data.Vector.Fusion.Stream.Monadic."
-                        Prelude.++ s Prelude.++ ": empty stream"
+errorEmptyStream fn = streamError fn "empty stream"
+
+errorNegativeIndex :: String -> a
+errorNegativeIndex fn = streamError fn "negative index"
+
+errorIndexOutOfRange :: String -> a
+errorIndexOutOfRange fn = streamError fn "index out of range"