content: {-# LANGUAGE ExistentialQuantification, Rank2Types, BangPatterns, CPP #-}
  
  -- |
  -- Module      : Data.Vector.Fusion.Stream.Monadic
  -- Copyright   : (c) Roman Leshchinskiy 2008-2010
  -- License     : BSD-style
  --
  -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
  -- Stability   : experimental
  -- Portability : non-portable
  --
  -- Monadic stream combinators.
  --
  
  {-@ LIQUID "--no-termination" @-}
  {-@ LIQUID "--diffcheck" @-}
  
  module Data.Vector.Fusion.Stream.Monadic (
    Stream(..), Step(..), SPEC(..),
  
    -- * Size hints
    size, sized,
  
    -- * Length
    length, null,
  
    -- * Construction
    empty, singleton, cons, snoc, replicate, replicateM, generate, generateM, (++),
  
    -- * Accessing elements
    head, last, (!!), (!?),
  
    -- * Substreams
    slice, init, tail, take, drop,
  
    -- * Mapping
    map, mapM, mapM_, trans, unbox, concatMap, flatten,
    
    -- * Zipping
    indexed, indexedR, zipWithM_,
    zipWithM, zipWith3M, zipWith4M, zipWith5M, zipWith6M,
    zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
    zip, zip3, zip4, zip5, zip6,
  
    -- * Filtering
    filter, filterM, takeWhile, takeWhileM, dropWhile, dropWhileM,
  
    -- * Searching
    elem, notElem, find, findM, findIndex, findIndexM,
  
    -- * Folding
    foldl, foldlM, foldl1, foldl1M, foldM, fold1M,
    foldl', foldlM', foldl1', foldl1M', foldM', fold1M',
    foldr, foldrM, foldr1, foldr1M,
  
    -- * Specialised folds
    and, or, concatMapM,
  
    -- * Unfolding
    unfoldr, unfoldrM,
    unfoldrN, unfoldrNM,
    iterateN, iterateNM,
  
    -- * Scans
    prescanl, prescanlM, prescanl', prescanlM',
    postscanl, postscanlM, postscanl', postscanlM',
    scanl, scanlM, scanl', scanlM',
    scanl1, scanl1M, scanl1', scanl1M',
  
    -- * Enumerations
    enumFromStepN, enumFromTo, enumFromThenTo,
  
    -- * Conversions
    toList, fromList, fromListN, unsafeFromList
  ) where
  
  import Data.Vector.Fusion.Stream.Size
  import Data.Vector.Fusion.Util ( Box(..), delay_inline )
  
  import Data.Char      ( ord )
  import GHC.Base       ( unsafeChr )
  import Control.Monad  ( liftM )
  import Prelude hiding ( length, null,
                          replicate, (++),
                          head, last, (!!),
                          init, tail, take, drop,
                          map, mapM, mapM_, concatMap,
                          zipWith, zipWith3, zip, zip3,
                          filter, takeWhile, dropWhile,
                          elem, notElem,
                          foldl, foldl1, foldr, foldr1,
                          and, or,
                          scanl, scanl1,
                          enumFromTo, enumFromThenTo )
  
  import Data.Int  ( Int8, Int16, Int32, Int64 )
  import Data.Word ( Word8, Word16, Word32, Word, Word64 )
  
  
  --LIQUID triggers TH expansion which can't happen in interpretive mode
  --import GHC.Exts ( SpecConstrAnnotation(..) )
  
  
  
  
  
  
  
  
  
  
  import qualified Data.Vector.Internal.Check as Ck
  
  
  
  
  
  
  
  
  
  
  
  
  
  data SPEC = SPEC | SPEC2
  
  --LIQUID triggers TH expansion which can't happen in interpretive mode
  {- ANN type SPEC ForceSpecConstr #-}
  
  
  emptyStream :: String
  {-# NOINLINE emptyStream #-}
  emptyStream = "empty stream"
  
  
  
  -- | 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'
  size :: Stream m a -> Size
  {-# INLINE size #-}
  size (Stream _ _ sz) = sz
  
  -- | Attach a 'Size' hint to a 'Stream'
  sized :: Stream m a -> Size -> Stream m a
  {-# INLINE [1] sized #-}
  sized (Stream step s _) sz = Stream step s sz
  
  -- Length
  -- ------
  
  -- | Length of a 'Stream'
  length :: Monad m => Stream m a -> m Int
  {-# INLINE [1] length #-}
  length s = foldl' (\n _ -> n+1) 0 s
  
  -- | Check if a 'Stream' is empty
  null :: Monad m => Stream m a -> m Bool
  {-# INLINE [1] null #-}
  null s = foldr (\_ _ -> False) True s
  
  
  -- Construction
  -- ------------
  
  -- | Empty 'Stream'
  empty :: Monad m => Stream m a
  {-# INLINE [1] empty #-}
  empty = Stream (const (return Done)) () (Exact 0)
  
  -- | Singleton 'Stream'
  singleton :: Monad m => a -> Stream m a
  {-# INLINE [1] singleton #-}
  singleton x = Stream (return . step) True (Exact 1)
    where
      {-# INLINE [0] step #-}
      step True  = Yield x False
      step False = Done
  
  -- | Replicate a value to a given length
  replicate :: Monad m => Int -> a -> Stream m a
  {-# INLINE replicate #-}
  replicate n x = replicateM n (return x)
  
  -- | Yield a 'Stream' of values obtained by performing the monadic action the
  -- given number of times
  replicateM :: Monad m => Int -> m a -> Stream m a
  {-# INLINE [1] replicateM #-}
  -- NOTE: We delay inlining max here because GHC will create a join point for
  -- the call to newArray# otherwise which is not really nice.
  replicateM n p = Stream step n (Exact (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step i | i <= 0    = return Done
             | otherwise = do { x <- p; return $ Yield x (i-1) }
  
  generate :: Monad m => Int -> (Int -> a) -> Stream m a
  {-# INLINE generate #-}
  generate n f = generateM n (return . f)
  
  -- | Generate a stream from its indices
  generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
  {-# INLINE [1] generateM #-}
  generateM n f = n `seq` Stream step 0 (Exact (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step i | i < n     = do
                             x <- f i
                             return $ Yield x (i+1)
             | otherwise = return Done
  
  -- | Prepend an element
  cons :: Monad m => a -> Stream m a -> Stream m a
  {-# INLINE cons #-}
  cons x s = singleton x ++ s
  
  -- | Append an element
  snoc :: Monad m => Stream m a -> a -> Stream m a
  {-# INLINE snoc #-}
  snoc s x = s ++ singleton x
  
  infixr 5 ++
  -- | Concatenate two 'Stream's
  (++) :: Monad m => Stream m a -> Stream m a -> Stream m a
  {-# INLINE [1] (++) #-}
  Stream stepa sa na ++ Stream stepb sb nb = Stream step (Left sa) (na + nb)
    where
      {-# INLINE [0] step #-}
      step (Left  sa) = do
                          r <- stepa sa
                          case r of
                            Yield x sa' -> return $ Yield x (Left  sa')
                            Skip    sa' -> return $ Skip    (Left  sa')
                            Done        -> return $ Skip    (Right sb)
      step (Right sb) = do
                          r <- stepb sb
                          case r of
                            Yield x sb' -> return $ Yield x (Right sb')
                            Skip    sb' -> return $ Skip    (Right sb')
                            Done        -> return $ Done
  
  -- Accessing elements
  -- ------------------
  
  -- | First element of the 'Stream' or error if empty
  head :: Monad m => Stream m a -> m a
  {-# INLINE [1] head #-}
  head (Stream step s _) = head_loop SPEC s
    where
      head_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield x _  -> return x
              Skip    s' -> head_loop SPEC s'
              Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 244) s emptyStream) "head"
  
  
  
  -- | Last element of the 'Stream' or error if empty
  last :: Monad m => Stream m a -> m a
  {-# INLINE [1] last #-}
  last (Stream step s _) = last_loop0 SPEC s
    where
      last_loop0 !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> last_loop1 SPEC x s'
              Skip    s' -> last_loop0 SPEC   s'
              Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 259) s emptyStream) "last"
  
      last_loop1 !sPEC x s
        = do
            r <- step s
            case r of
              Yield y s' -> last_loop1 SPEC y s'
              Skip    s' -> last_loop1 SPEC x s'
              Done       -> return x
  
  infixl 9 !!
  -- | Element at the given position
  (!!) :: Monad m => Stream m a -> Int -> m a
  {-# INLINE (!!) #-}
  Stream step s _ !! i | i < 0     = (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 273) "!!" "negative index"
                       | otherwise = index_loop SPEC s i
    where
      index_loop !sPEC s i
        = i `seq`
          do
            r <- step s
            case r of
              Yield x s' | i == 0    -> return x
                         | otherwise -> index_loop SPEC s' (i-1)
              Skip    s'             -> index_loop SPEC s' i
              Done                   -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 284) s emptyStream) "!!"
  
  infixl 9 !?
  -- | Element at the given position or 'Nothing' if out of bounds
  (!?) :: Monad m => Stream m a -> Int -> m (Maybe a)
  {-# INLINE (!?) #-}
  Stream step s _ !? i = index_loop SPEC s i
    where
      index_loop !sPEC s i
        = i `seq`
          do
            r <- step s
            case r of
              Yield x s' | i == 0    -> return (Just x)
                         | otherwise -> index_loop SPEC s' (i-1)
              Skip    s'             -> index_loop SPEC s' i
              Done                   -> return Nothing
  
  -- Substreams
  -- ----------
  
  -- | Extract a substream of the given length starting at the given position.
  slice :: Monad m => Int   -- ^ starting index
                   -> Int   -- ^ length
                   -> Stream m a
                   -> Stream m a
  {-# INLINE slice #-}
  slice i n s = take n (drop i s)
  
  -- | All but the last element
  init :: Monad m => Stream m a -> Stream m a
  {-# INLINE [1] init #-}
  init (Stream step s sz) = Stream step' (Nothing, s) (sz - 1)
    where
      {-# INLINE [0] step' #-}
      step' (Nothing, s) = liftM (\r ->
                             case r of
                               Yield x s' -> Skip (Just x,  s')
                               Skip    s' -> Skip (Nothing, s')
                               Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 323) s emptyStream) "init"
                           ) (step s)
  
      step' (Just x,  s) = liftM (\r -> 
                             case r of
                               Yield y s' -> Yield x (Just y, s')
                               Skip    s' -> Skip    (Just x, s')
                               Done       -> Done
                           ) (step s)
  
  -- | All but the first element
  tail :: Monad m => Stream m a -> Stream m a
  {-# INLINE [1] tail #-}
  tail (Stream step s sz) = Stream step' (Left s) (sz - 1)
    where
      {-# INLINE [0] step' #-}
      step' (Left  s) = liftM (\r ->
                          case r of
                            Yield x s' -> Skip (Right s')
                            Skip    s' -> Skip (Left  s')
                            Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 343) s emptyStream) "tail"
                        ) (step s)
  
      step' (Right s) = liftM (\r ->
                          case r of
                            Yield x s' -> Yield x (Right s')
                            Skip    s' -> Skip    (Right s')
                            Done       -> Done
                        ) (step s)
  
  -- | The first @n@ elements
  take :: Monad m => Int -> Stream m a -> Stream m a
  {-# INLINE [1] take #-}
  take n (Stream step s sz) = Stream step' (s, 0) (smaller (Exact n) sz)
    where
      {-# INLINE [0] step' #-}
      step' (s, i) | i < n = liftM (\r ->
                               case r of
                                 Yield x s' -> Yield x (s', i+1)
                                 Skip    s' -> Skip    (s', i)
                                 Done       -> Done
                             ) (step s)
      step' (s, i) = return Done
  
  -- | All but the first @n@ elements
  drop :: Monad m => Int -> Stream m a -> Stream m a
  {-# INLINE [1] drop #-}
  drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
    where
      {-# INLINE [0] step' #-}
      step' (s, Just i) | i > 0 = liftM (\r ->
                                  case r of
                                     Yield x s' -> Skip (s', Just (i-1))
                                     Skip    s' -> Skip (s', Just i)
                                     Done       -> Done
                                  ) (step s)
                        | otherwise = return $ Skip (s, Nothing)
  
      step' (s, Nothing) = liftM (\r ->
                             case r of
                               Yield x s' -> Yield x (s', Nothing)
                               Skip    s' -> Skip    (s', Nothing)
                               Done       -> Done
                             ) (step s)
                       
  -- 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 [1] mapM #-}
  mapM f (Stream step s n) = Stream step' s n
    where
      {-# INLINE [0] step' #-}
      step' s = do
                  r <- step s
                  case r of
                    Yield x s' -> liftM  (`Yield` s') (f x)
                    Skip    s' -> return (Skip    s')
                    Done       -> return Done
  
  consume :: Monad m => Stream m a -> m ()
  {-# INLINE [1] consume #-}
  consume (Stream step s _) = consume_loop SPEC s
    where
      consume_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield _ s' -> consume_loop SPEC s'
              Skip    s' -> consume_loop SPEC s'
              Done       -> return ()
  
  -- | Execute a monadic action for each element of the 'Stream'
  mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
  {-# INLINE [1] mapM_ #-}
  mapM_ m = consume . mapM m
  
  -- | 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 [1] trans #-}
  trans f (Stream step s n) = Stream (f . step) s n
  
  unbox :: Monad m => Stream m (Box a) -> Stream m a
  {-# INLINE [1] unbox #-}
  unbox (Stream step s n) = Stream step' s n
    where
      {-# INLINE [0] 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
  -- -------
  
  -- | Pair each element in a 'Stream' with its index
  indexed :: Monad m => Stream m a -> Stream m (Int,a)
  {-# INLINE [1] indexed #-}
  indexed (Stream step s n) = Stream step' (s,0) n
    where
      {-# INLINE [0] step' #-}
      step' (s,i) = i `seq`
                    do
                      r <- step s
                      case r of
                        Yield x s' -> return $ Yield (i,x) (s', i+1)
                        Skip    s' -> return $ Skip        (s', i)
                        Done       -> return Done
  
  -- | Pair each element in a 'Stream' with its index, starting from the right
  -- and counting down
  indexedR :: Monad m => Int -> Stream m a -> Stream m (Int,a)
  {-# INLINE [1] indexedR #-}
  indexedR m (Stream step s n) = Stream step' (s,m) n
    where
      {-# INLINE [0] step' #-}
      step' (s,i) = i `seq`
                    do
                      r <- step s
                      case r of
                        Yield x s' -> let i' = i-1
                                      in
                                      return $ Yield (i',x) (s', i')
                        Skip    s' -> return $ Skip         (s', i)
                        Done       -> return Done
  
  -- | 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 [1] zipWithM #-}
  zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
    = Stream step (sa, sb, Nothing) (smaller na nb)
    where
      {-# INLINE [0] step #-}
      step (sa, sb, Nothing) = liftM (\r ->
                                 case r of
                                   Yield x sa' -> Skip (sa', sb, Just x)
                                   Skip    sa' -> Skip (sa', sb, Nothing)
                                   Done        -> Done
                               ) (stepa sa)
  
      step (sa, sb, Just x)  = do
                                 r <- stepb sb
                                 case r of
                                   Yield y sb' ->
                                     do
                                       z <- f x y
                                       return $ Yield z (sa, sb', Nothing)
                                   Skip    sb' -> return $ Skip (sa, sb', Just x)
                                   Done        -> return $ Done
  
  -- FIXME: This might expose an opportunity for inplace execution.
  {-# RULES
  
  "zipWithM xs xs [Vector.Stream]" forall f xs.
    zipWithM f xs xs = mapM (\x -> f x x) xs
  
    #-}
  
  
  zipWithM_ :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> m ()
  {-# INLINE zipWithM_ #-}
  zipWithM_ f sa sb = consume (zipWithM f sa sb)
  
  zipWith3M :: Monad m => (a -> b -> c -> m d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d
  {-# INLINE [1] 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 [0] 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
  
  zipWith4M :: Monad m => (a -> b -> c -> d -> m e)
                       -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                       -> Stream m e
  {-# INLINE zipWith4M #-}
  zipWith4M f sa sb sc sd
    = zipWithM (\(a,b) (c,d) -> f a b c d) (zip sa sb) (zip sc sd)
  
  zipWith5M :: Monad m => (a -> b -> c -> d -> e -> m f)
                       -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                       -> Stream m e -> Stream m f
  {-# INLINE zipWith5M #-}
  zipWith5M f sa sb sc sd se
    = zipWithM (\(a,b,c) (d,e) -> f a b c d e) (zip3 sa sb sc) (zip sd se)
  
  zipWith6M :: Monad m => (a -> b -> c -> d -> e -> f -> m g)
                       -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                       -> Stream m e -> Stream m f -> Stream m g
  {-# INLINE zipWith6M #-}
  zipWith6M fn sa sb sc sd se sf
    = zipWithM (\(a,b,c) (d,e,f) -> fn a b c d e f) (zip3 sa sb sc)
                                                    (zip3 sd se sf)
  
  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))
  
  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))
  
  zipWith4 :: Monad m => (a -> b -> c -> d -> e)
                      -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                      -> Stream m e
  {-# INLINE zipWith4 #-}
  zipWith4 f = zipWith4M (\a b c d -> return (f a b c d))
  
  zipWith5 :: Monad m => (a -> b -> c -> d -> e -> f)
                      -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                      -> Stream m e -> Stream m f
  {-# INLINE zipWith5 #-}
  zipWith5 f = zipWith5M (\a b c d e -> return (f a b c d e))
  
  zipWith6 :: Monad m => (a -> b -> c -> d -> e -> f -> g)
                      -> Stream m a -> Stream m b -> Stream m c -> Stream m d
                      -> Stream m e -> Stream m f -> Stream m g
  {-# INLINE zipWith6 #-}
  zipWith6 fn = zipWith6M (\a b c d e f -> return (fn a b c d e f))
  
  zip :: Monad m => Stream m a -> Stream m b -> Stream m (a,b)
  {-# INLINE zip #-}
  zip = zipWith (,)
  
  zip3 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m (a,b,c)
  {-# INLINE zip3 #-}
  zip3 = zipWith3 (,,)
  
  zip4 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
                  -> Stream m (a,b,c,d)
  {-# INLINE zip4 #-}
  zip4 = zipWith4 (,,,)
  
  zip5 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
                  -> Stream m e -> Stream m (a,b,c,d,e)
  {-# INLINE zip5 #-}
  zip5 = zipWith5 (,,,,)
  
  zip6 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
                  -> Stream m e -> Stream m f -> Stream m (a,b,c,d,e,f)
  {-# INLINE zip6 #-}
  zip6 = zipWith6 (,,,,,)
  
  -- Filtering
  -- ---------
  
  -- | Drop elements which do not satisfy the predicate
  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 monadic predicate
  filterM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
  {-# INLINE [1] filterM #-}
  filterM f (Stream step s n) = Stream step' s (toMax n)
    where
      {-# INLINE [0] step' #-}
      step' s = do
                  r <- step s
                  case r of
                    Yield x s' -> do
                                    b <- f x
                                    return $ if b then Yield x s'
                                                  else Skip    s'
                    Skip    s' -> return $ Skip s'
                    Done       -> return $ Done
  
  -- | Longest prefix of elements that satisfy the predicate
  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 monadic predicate
  takeWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
  {-# INLINE [1] takeWhileM #-}
  takeWhileM f (Stream step s n) = Stream step' s (toMax n)
    where
      {-# INLINE [0] step' #-}
      step' s = do
                  r <- step s
                  case r of
                    Yield x s' -> do
                                    b <- f x
                                    return $ if b then Yield x s' else Done
                    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 monadic predicate
  dropWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
  {-# INLINE [1] dropWhileM #-}
  dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
    where
      -- NOTE: we jump through hoops here to have only one Yield; local data
      -- declarations would be nice!
  
      {-# INLINE [0] step' #-}
      step' (DropWhile_Drop s)
        = do
            r <- step s
            case r of
              Yield x s' -> do
                              b <- f x
                              return $ if b then Skip (DropWhile_Drop    s')
                                            else Skip (DropWhile_Yield x s')
              Skip    s' -> return $ Skip (DropWhile_Drop    s')
              Done       -> return $ Done
  
      step' (DropWhile_Yield x s) = return $ Yield x (DropWhile_Next s)
  
      step' (DropWhile_Next s)
        = liftM (\r ->
            case r of
              Yield x s' -> Skip    (DropWhile_Yield x s')
              Skip    s' -> Skip    (DropWhile_Next    s')
              Done       -> Done
          ) (step s)
  
  -- Searching
  -- ---------
  
  infix 4 `elem`
  -- | Check whether the 'Stream' contains an element
  elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
  {-# INLINE [1] elem #-}
  elem x (Stream step s _) = elem_loop SPEC s
    where
      elem_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield y s' | x == y    -> return True
                         | otherwise -> elem_loop SPEC s'
              Skip    s'             -> elem_loop SPEC s'
              Done                   -> return False
  
  infix 4 `notElem`
  -- | Inverse of `elem`
  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 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 [1] findM #-}
  findM f (Stream step s _) = find_loop SPEC s
    where
      find_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> do
                              b <- f x
                              if b then return $ Just x
                                   else find_loop SPEC s'
              Skip    s' -> find_loop SPEC 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 [1] findIndex #-}
  findIndex f = findIndexM (return . f)
  
  -- | 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 [1] findIndexM #-}
  findIndexM f (Stream step s _) = findIndex_loop SPEC s 0
    where
      findIndex_loop !sPEC s i
        = do
            r <- step s
            case r of
              Yield x s' -> do
                              b <- f x
                              if b then return $ Just i
                                   else findIndex_loop SPEC s' (i+1)
              Skip    s' -> findIndex_loop SPEC s' i
              Done       -> return Nothing
  
  -- 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 [1] foldlM #-}
  foldlM m z (Stream step s _) = foldlM_loop SPEC z s
    where
      foldlM_loop !sPEC z s
        = do
            r <- step s
            case r of
              Yield x s' -> do { z' <- m z x; foldlM_loop SPEC z' s' }
              Skip    s' -> foldlM_loop SPEC 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 [1] foldl1M #-}
  foldl1M f (Stream step s sz) = foldl1M_loop SPEC s
    where
      foldl1M_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> foldlM f x (Stream step s' (sz - 1))
              Skip    s' -> foldl1M_loop SPEC s'
              Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 811) s emptyStream) "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 [1] foldlM' #-}
  foldlM' m z (Stream step s _) = foldlM'_loop SPEC z s
    where
      foldlM'_loop !sPEC z s
        = z `seq`
          do
            r <- step s
            case r of
              Yield x s' -> do { z' <- m z x; foldlM'_loop SPEC z' s' }
              Skip    s' -> foldlM'_loop SPEC 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 [1] foldl1M' #-}
  foldl1M' f (Stream step s sz) = foldl1M'_loop SPEC s
    where
      foldl1M'_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> foldlM' f x (Stream step s' (sz - 1))
              Skip    s' -> foldl1M'_loop SPEC s'
              Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 859) s emptyStream) "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 [1] foldrM #-}
  foldrM f z (Stream step s _) = foldrM_loop SPEC s
    where
      foldrM_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> f x =<< foldrM_loop SPEC s'
              Skip    s' -> foldrM_loop SPEC 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 [1] foldr1M #-}
  foldr1M f (Stream step s _) = foldr1M_loop0 SPEC s
    where
      foldr1M_loop0 !sPEC s
        = do
            r <- step s
            case r of
              Yield x s' -> foldr1M_loop1 SPEC x s'
              Skip    s' -> foldr1M_loop0 SPEC   s'
              Done       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 900) s emptyStream) "foldr1M"
  
      foldr1M_loop1 !sPEC x s
        = do
            r <- step s
            case r of
              Yield y s' -> f x =<< foldr1M_loop1 SPEC y s'
              Skip    s' -> foldr1M_loop1 SPEC x s'
              Done       -> return x
  
  -- Specialised folds
  -- -----------------
  
  and :: Monad m => Stream m Bool -> m Bool
  {-# INLINE [1] and #-}
  and (Stream step s _) = and_loop SPEC s
    where
      and_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield False _  -> return False
              Yield True  s' -> and_loop SPEC s'
              Skip        s' -> and_loop SPEC s'
              Done           -> return True
  
  or :: Monad m => Stream m Bool -> m Bool
  {-# INLINE [1] or #-}
  or (Stream step s _) = or_loop SPEC s
    where
      or_loop !sPEC s
        = do
            r <- step s
            case r of
              Yield False s' -> or_loop SPEC s'
              Yield True  _  -> return True
              Skip        s' -> or_loop SPEC 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 [1] 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)
  
  -- | Create a 'Stream' of values from a 'Stream' of streamable things
  flatten :: Monad m => (a -> m s) -> (s -> m (Step s b)) -> Size
                     -> Stream m a -> Stream m b
  {-# INLINE [1] flatten #-}
  flatten mk istep sz (Stream ostep t _) = Stream step (Left t) sz
    where
      {-# INLINE [0] step #-}
      step (Left t) = do
                        r <- ostep t
                        case r of
                          Yield a t' -> do
                                          s <- mk a
                                          s `seq` return (Skip (Right (s,t')))
                          Skip    t' -> return $ Skip (Left t')
                          Done       -> return $ Done
  
      
      step (Right (s,t)) = do
                             r <- istep s
                             case r of
                               Yield x s' -> return $ Yield x (Right (s',t))
                               Skip    s' -> return $ Skip    (Right (s',t))
                               Done       -> return $ Skip    (Left t)
  
  -- Unfolding
  -- ---------
  
  -- | Unfold
  unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
  {-# INLINE [1] unfoldr #-}
  unfoldr f = unfoldrM (return . f)
  
  -- | Unfold with a monadic function
  unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
  {-# INLINE [1] unfoldrM #-}
  unfoldrM f s = Stream step s Unknown
    where
      {-# INLINE [0] step #-}
      step s = liftM (\r ->
                 case r of
                   Just (x, s') -> Yield x s'
                   Nothing      -> Done
               ) (f s)
  
  -- | Unfold at most @n@ elements
  unfoldrN :: Monad m => Int -> (s -> Maybe (a, s)) -> s -> Stream m a
  {-# INLINE [1] unfoldrN #-}
  unfoldrN n f = unfoldrNM n (return . f)
  
  -- | Unfold at most @n@ elements with a monadic functions
  unfoldrNM :: Monad m => Int -> (s -> m (Maybe (a, s))) -> s -> Stream m a
  {-# INLINE [1] unfoldrNM #-}
  unfoldrNM n f s = Stream step (s,n) (Max (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step (s,n) | n <= 0    = return Done
                 | otherwise = liftM (\r ->
                                 case r of
                                   Just (x,s') -> Yield x (s',n-1)
                                   Nothing     -> Done
                               ) (f s)
  
  -- | Apply monadic function n times to value. Zeroth element is original value.
  iterateNM :: Monad m => Int -> (a -> m a) -> a -> Stream m a
  {-# INLINE [1] iterateNM #-}
  iterateNM n f x0 = Stream step (x0,n) (Exact (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step (x,i) | i <= 0    = return Done
                 | i == n    = return $ Yield x (x,i-1)
                 | otherwise = do a <- f x
                                  return $ Yield a (a,i-1)
  
  -- | Apply function n times to value. Zeroth element is original value.
  iterateN :: Monad m => Int -> (a -> a) -> a -> Stream m a
  {-# INLINE [1] iterateN #-}
  iterateN n f x0 = iterateNM n (return . f) x0
  
  -- Scans
  -- -----
  
  -- | Prefix scan
  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 a monadic operator
  prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
  {-# INLINE [1] prescanlM #-}
  prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
    where
      {-# INLINE [0] step' #-}
      step' (s,x) = do
                      r <- step s
                      case r of
                        Yield y s' -> do
                                        z <- f x y
                                        return $ Yield x (s', z)
                        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 and a monadic operator
  prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
  {-# INLINE [1] prescanlM' #-}
  prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
    where
      {-# INLINE [0] step' #-}
      step' (s,x) = x `seq`
                    do
                      r <- step s
                      case r of
                        Yield y s' -> do
                                        z <- f x y
                                        return $ Yield x (s', z)
                        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 [1] postscanlM #-}
  postscanlM f z (Stream step s sz) = Stream step' (s,z) sz
    where
      {-# INLINE [0] 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 [1] postscanlM' #-}
  postscanlM' f z (Stream step s sz) = z `seq` Stream step' (s,z) sz
    where
      {-# INLINE [0] 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 [1] scanl1M #-}
  scanl1M f (Stream step s sz) = Stream step' (s, Nothing) sz
    where
      {-# INLINE [0] 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       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 1161) s emptyStream) "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 [1] scanl1M' #-}
  scanl1M' f (Stream step s sz) = Stream step' (s, Nothing) sz
    where
      {-# INLINE [0] 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       -> (\s -> (Ck.error "Data/Vector/Fusion/Stream/Monadic.hs" 1189) s emptyStream) "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
  -- ------------
  
  -- The Enum class is broken for this, there just doesn't seem to be a
  -- way to implement this generically. We have to specialise for as many types
  -- as we can but this doesn't help in polymorphic loops.
  
  -- | Yield a 'Stream' of the given length containing the values @x@, @x+y@,
  -- @x+y+y@ etc.
  enumFromStepN :: (Num a, Monad m) => a -> a -> Int -> Stream m a
  {-# INLINE [1] enumFromStepN #-}
  enumFromStepN x y n = x `seq` y `seq` n `seq`
                        Stream step (x,n) (Exact (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step (x,n) | n > 0     = return $ Yield x (x+y,n-1)
                 | otherwise = return $ Done
  
  -- | Enumerate values
  --
  -- /WARNING:/ This operation can be very inefficient. If at all possible, use
  -- 'enumFromStepN' instead.
  enumFromTo :: (Enum a, Monad m) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo #-}
  enumFromTo x y = fromList [x .. y]
  
  -- NOTE: We use (x+1) instead of (succ x) below because the latter checks for
  -- overflow which can't happen here.
  
  -- FIXME: add "too large" test for Int
  enumFromTo_small :: (Integral a, Monad m) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo_small #-}
  enumFromTo_small x y = x `seq` y `seq` Stream step x (Exact n)
    where
      n = delay_inline max (fromIntegral y - fromIntegral x + 1) 0
  
      {-# INLINE [0] step #-}
      step x | x <= y    = return $ Yield x (x+1)
             | otherwise = return $ Done
  
  {-# RULES
  
  "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<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
  
    #-}
  
  
  
  
  -- NOTE: We could implement a generic "too large" test:
  --
  -- len x y | x > y = 0
  --         | n > 0 && n <= fromIntegral (maxBound :: Int) = fromIntegral n
  --         | otherwise = error
  --   where
  --     n = y-x+1
  --
  -- Alas, GHC won't eliminate unnecessary comparisons (such as n >= 0 for
  -- unsigned types). See http://hackage.haskell.org/trac/ghc/ticket/3744
  --
  
  enumFromTo_int :: (Integral a, Monad m) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo_int #-}
  enumFromTo_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
    where
      {-# INLINE [0] len #-}
      len x y | x > y     = 0
              | otherwise = ((Ck.check "Data/Vector/Fusion/Stream/Monadic.hs" 1289) Ck.Bounds) "enumFromTo" "vector too large"
                            (n > 0)
                          $ fromIntegral n
        where
          n = y-x+1
  
      {-# INLINE [0] step #-}
      step x | x <= y    = return $ Yield x (x+1)
             | otherwise = return $ Done
  
  {-# RULES
  
  "enumFromTo<Int> [Stream]"
    enumFromTo = enumFromTo_int :: Monad m => Int -> Int -> Stream m Int
  
  
  
  
  
  
  
  
  "enumFromTo<Int32> [Stream]"
    enumFromTo = enumFromTo_int :: Monad m => Int32 -> Int32 -> Stream m Int32
  
  
  
    #-}
  
  
  enumFromTo_big_word :: (Integral a, Monad m) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo_big_word #-}
  enumFromTo_big_word x y = x `seq` y `seq` Stream step x (Exact (len x y))
    where
      {-# INLINE [0] len #-}
      len x y | x > y     = 0
              | otherwise = ((Ck.check "Data/Vector/Fusion/Stream/Monadic.hs" 1324) Ck.Bounds) "enumFromTo" "vector too large"
                            (n < fromIntegral (maxBound :: Int))
                          $ fromIntegral (n+1)
        where
          n = y-x
  
      {-# INLINE [0] step #-}
      step x | x <= y    = return $ Yield x (x+1)
             | otherwise = return $ Done
  
  {-# RULES
  
  "enumFromTo<Word> [Stream]"
    enumFromTo = enumFromTo_big_word :: Monad m => Word -> Word -> Stream m Word
  
  "enumFromTo<Word64> [Stream]"
    enumFromTo = enumFromTo_big_word
                          :: Monad m => Word64 -> Word64 -> Stream m Word64
  
  
  
  
  
  
  
  
  
  "enumFromTo<Integer> [Stream]"
    enumFromTo = enumFromTo_big_word
                          :: Monad m => Integer -> Integer -> Stream m Integer
  
    #-}
  
  
  -- FIXME: the "too large" test is totally wrong
  enumFromTo_big_int :: (Integral a, Monad m) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo_big_int #-}
  enumFromTo_big_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
    where
      {-# INLINE [0] len #-}
      len x y | x > y     = 0
              | otherwise = ((Ck.check "Data/Vector/Fusion/Stream/Monadic.hs" 1364) Ck.Bounds) "enumFromTo" "vector too large"
                            (n > 0 && n <= fromIntegral (maxBound :: Int))
                          $ fromIntegral n
        where
          n = y-x+1
  
      {-# INLINE [0] step #-}
      step x | x <= y    = return $ Yield x (x+1)
             | otherwise = return $ Done
  
  
  
  enumFromTo_char :: Monad m => Char -> Char -> Stream m Char
  {-# INLINE [1] enumFromTo_char #-}
  enumFromTo_char x y = x `seq` y `seq` Stream step xn (Exact n)
    where
      xn = ord x
      yn = ord y
  
      n = delay_inline max 0 (yn - xn + 1)
  
      {-# INLINE [0] step #-}
      step xn | xn <= yn  = return $ Yield (unsafeChr xn) (xn+1)
              | otherwise = return $ Done
  
  {-# RULES
  
  "enumFromTo<Char> [Stream]"
    enumFromTo = enumFromTo_char
  
    #-}
  
  
  ------------------------------------------------------------------------
  
  -- Specialise enumFromTo for Float and Double.
  -- Also, try to do something about pairs?
  
  enumFromTo_double :: (Monad m, Ord a, RealFrac a) => a -> a -> Stream m a
  {-# INLINE [1] enumFromTo_double #-}
  enumFromTo_double n m = n `seq` m `seq` Stream step n (Max (len n m))
    where
      lim = m + 1/2 -- important to float out
  
      {-# INLINE [0] len #-}
      len x y | x > y     = 0
              | otherwise = ((Ck.check "Data/Vector/Fusion/Stream/Monadic.hs" 1418) Ck.Bounds) "enumFromTo" "vector too large"
                            (n > 0)
                          $ fromIntegral n
        where
          n = truncate (y-x)+2
  
      {-# INLINE [0] step #-}
      step x | x <= lim  = return $ Yield x (x+1)
             | otherwise = return $ Done
  
  {-# RULES
  
  "enumFromTo<Double> [Stream]"
    enumFromTo = enumFromTo_double :: Monad m => Double -> Double -> Stream m Double
  
  "enumFromTo<Float> [Stream]"
    enumFromTo = enumFromTo_double :: Monad m => Float -> Float -> Stream m Float
  
    #-}
  
  
  ------------------------------------------------------------------------
  
  -- | Enumerate values with a given step.
  --
  -- /WARNING:/ This operation is very inefficient. If at all possible, use
  -- 'enumFromStepN' instead.
  enumFromThenTo :: (Enum a, Monad m) => a -> a -> a -> Stream m a
  {-# INLINE [1] enumFromThenTo #-}
  enumFromThenTo x y z = fromList [x, y .. z]
  
  -- FIXME: Specialise enumFromThenTo.
  
  -- 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 fromList #-}
  fromList xs = unsafeFromList Unknown xs
  
  -- | Convert the first @n@ elements of a list to a 'Stream'
  fromListN :: Monad m => Int -> [a] -> Stream m a
  {-# INLINE [1] fromListN #-}
  fromListN n xs = Stream step (xs,n) (Max (delay_inline max n 0))
    where
      {-# INLINE [0] step #-}
      step (xs,n) | n <= 0 = return Done
      step (x:xs,n)        = return (Yield x (xs,n-1))
      step ([],n)          = return Done
  
  -- | Convert a list to a 'Stream' with the given 'Size' hint. 
  unsafeFromList :: Monad m => Size -> [a] -> Stream m a
  {-# INLINE [1] unsafeFromList #-}
  unsafeFromList sz xs = Stream step xs sz
    where
      step (x:xs) = return (Yield x xs)
      step []     = return Done
  
  
  