{-# LANGUAGE CPP #-}
-- |
-- Module      : Streamly.Internal.Data.Stream.Eliminate
-- Copyright   : (c) 2018 Composewell Technologies
--               (c) Roman Leshchinskiy 2008-2010
-- License     : BSD-3-Clause
-- Maintainer  : streamly@composewell.com
-- Stability   : experimental
-- Portability : GHC

-- A few functions in this module have been adapted from the vector package
-- (c) Roman Leshchinskiy.
--
module Streamly.Internal.Data.Stream.Eliminate
    (
    -- * Running a 'Fold'
      fold

    -- -- * Running a 'Parser'
    , parse
    , parseD
    , parseBreak
    , parseBreakD

    -- * Stream Deconstruction
    , uncons

    -- * Right Folds
    , foldrM
    , foldr
    , foldrMx
    , foldr1

    -- * Left Folds
    , foldlM'
    , foldl'
    , foldlMx'
    , foldlx'

    -- * Specific Fold Functions
    , drain
    , mapM_ -- Map and Fold
    , null
    , head
    , headElse
    , tail
    , last
    , elem
    , notElem
    , all
    , any
    , maximum
    , maximumBy
    , minimum
    , minimumBy
    , lookup
    , findM
    , find
    , (!!)
    , the

    -- * To containers
    , toList
    , toListRev

    -- * Multi-Stream Folds
    -- ** Comparisons
    -- | These should probably be expressed using zipping operations.
    , eqBy
    , cmpBy

    -- ** Substreams
    -- | These should probably be expressed using parsers.
    , isPrefixOf
    , isInfixOf
    , isSuffixOf
    , isSuffixOfUnbox
    , isSubsequenceOf
    , stripPrefix
    , stripSuffix
    , stripSuffixUnbox
    )
where

#include "inline.hs"

import Control.Exception (assert)
import Control.Monad.IO.Class (MonadIO(..))
import Foreign.Storable (Storable)
import GHC.Exts (SpecConstrAnnotation(..))
import GHC.Types (SPEC(..))
import Streamly.Internal.Data.Parser (ParseError(..))
import Streamly.Internal.Data.SVar.Type (defState)
import Streamly.Internal.Data.Unbox (Unbox)

import Streamly.Internal.Data.Maybe.Strict (Maybe'(..))

import qualified Streamly.Internal.Data.Array.Type as Array
import qualified Streamly.Internal.Data.Fold as Fold
import qualified Streamly.Internal.Data.Parser as PR
import qualified Streamly.Internal.Data.Parser as PRD
import qualified Streamly.Internal.Data.Stream.Generate as StreamD
import qualified Streamly.Internal.Data.Stream.Nesting as Nesting
import qualified Streamly.Internal.Data.Stream.Transform as StreamD

import Prelude hiding
       ( Foldable(..), all, any, head, last, lookup, mapM, mapM_
       , notElem, splitAt, tail, (!!))
import Data.Foldable (length)
import Streamly.Internal.Data.Stream.Type

#include "DocTestDataStream.hs"

------------------------------------------------------------------------------
-- Elimination by Folds
------------------------------------------------------------------------------

------------------------------------------------------------------------------
-- Right Folds
------------------------------------------------------------------------------

{-# INLINE_NORMAL foldr1 #-}
foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m (Maybe a)
foldr1 :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> a) -> Stream m a -> m (Maybe a)
foldr1 a -> a -> a
f Stream m a
m = do
     Maybe (a, Stream m a)
r <- Stream m a -> m (Maybe (a, Stream m a))
forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (a, Stream m a))
uncons Stream m a
m
     case Maybe (a, Stream m a)
r of
         Maybe (a, Stream m a)
Nothing   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
         Just (a
h, Stream m a
t) -> (a -> Maybe a) -> m a -> m (Maybe a)
forall a b. (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Maybe a
forall a. a -> Maybe a
Just ((a -> a -> a) -> a -> Stream m a -> m a
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> b) -> b -> Stream m a -> m b
foldr a -> a -> a
f a
h Stream m a
t)

------------------------------------------------------------------------------
-- Parsers
------------------------------------------------------------------------------

-- Inlined definition. Without the inline "serially/parser/take" benchmark
-- degrades and parseMany does not fuse. Even using "inline" at the callsite
-- does not help.
{-# INLINE splitAt #-}
splitAt :: Int -> [a] -> ([a],[a])
splitAt :: forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [a]
ls
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = ([], [a]
ls)
  | Bool
otherwise          = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' Int
n [a]
ls
    where
        splitAt' :: Int -> [a] -> ([a], [a])
        splitAt' :: forall a. Int -> [a] -> ([a], [a])
splitAt' Int
_  []     = ([], [])
        splitAt' Int
1  (a
x:[a]
xs) = ([a
x], [a]
xs)
        splitAt' Int
m  (a
x:[a]
xs) = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs', [a]
xs'')
          where
            ([a]
xs', [a]
xs'') = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
xs

-- GHC parser does not accept {-# ANN type [] NoSpecConstr #-}, so we need
-- to make a newtype.
{-# ANN type List NoSpecConstr #-}
newtype List a = List {forall a. List a -> [a]
getList :: [a]}

-- | Run a 'Parse' over a stream.
{-# INLINE_NORMAL parseD #-}
parseD
    :: Monad m
    => PRD.Parser a m b
    -> Stream m a
    -> m (Either ParseError b)
parseD :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parseD Parser a m b
parser Stream m a
strm = do
    (Either ParseError b
b, Stream m a
_) <- Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD Parser a m b
parser Stream m a
strm
    Either ParseError b -> m (Either ParseError b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Either ParseError b
b

-- | Parse a stream using the supplied 'Parser'.
--
-- Parsers (See "Streamly.Internal.Data.Parser") are more powerful folds that
-- add backtracking and error functionality to terminating folds. Unlike folds,
-- parsers may not always result in a valid output, they may result in an
-- error.  For example:
--
-- >>> Stream.parse (Parser.takeEQ 1 Fold.drain) Stream.nil
-- Left (ParseError "takeEQ: Expecting exactly 1 elements, input terminated on 0")
--
-- Note: @parse p@ is not the same as  @head . parseMany p@ on an empty stream.
--
{-# INLINE [3] parse #-}
parse :: Monad m => PR.Parser a m b -> Stream m a -> m (Either ParseError b)
parse :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parse = Parser a m b -> Stream m a -> m (Either ParseError b)
forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b)
parseD

-- XXX It may be a good idea to use constant sized chunks for backtracking. We
-- can take a byte stream but when we have to backtrack we create constant
-- sized chunks. We maintain one forward list and one backward list of constant
-- sized chunks, and a last backtracking offset. That way we just need lists of
-- contents and no need to maintain start/end pointers for individual arrays,
-- reducing bookkeeping work.

-- | Run a 'Parse' over a stream and return rest of the Stream.
{-# INLINE_NORMAL parseBreakD #-}
parseBreakD
    :: Monad m
    => PRD.Parser a m b
    -> Stream m a
    -> m (Either ParseError b, Stream m a)
parseBreakD :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD (PRD.Parser s -> a -> m (Step s b)
pstep m (Initial s b)
initial s -> m (Step s b)
extract) stream :: Stream m a
stream@(Stream State StreamK m a -> s -> m (Step s a)
step s
state) = do
    Initial s b
res <- m (Initial s b)
initial
    case Initial s b
res of
        PRD.IPartial s
s -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
state ([a] -> List a
forall a. [a] -> List a
List []) s
s
        PRD.IDone b
b -> (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, Stream m a
stream)
        PRD.IError String
err -> (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), Stream m a
stream)

    where

    -- "buf" contains last few items in the stream that we may have to
    -- backtrack to.
    --
    -- XXX currently we are using a dumb list based approach for backtracking
    -- buffer. This can be replaced by a sliding/ring buffer using Data.Array.
    -- That will allow us more efficient random back and forth movement.
    go :: SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go !SPEC
_ s
st List a
buf !s
pst = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> do
                Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
                case Step s b
pRes of
                    PR.Partial Int
0 s
pst1 -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List []) s
pst1
                    PR.Partial Int
1 s
pst1 -> SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
                    PR.Partial Int
n s
pst1 -> do
                        Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List []) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
                    PR.Continue Int
0 s
pst1 -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) s
pst1
                    PR.Continue Int
1 s
pst1 -> SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s List a
buf ([a] -> List a
forall a. [a] -> List a
List [a
x]) s
pst1
                    PR.Continue Int
n s
pst1 -> do
                        Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let ([a]
src0, [a]
buf1) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List [a]
buf1) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
                    PR.Done Int
0 b
b -> (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, (State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    PR.Done Int
n b
b -> do
                        Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                        let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                            src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                        -- XXX This would make it quadratic. We should probably
                        -- use StreamK if we have to append many times.
                        (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
                            ( b -> Either ParseError b
forall a b. b -> Either a b
Right b
b,
                              Stream m a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append ([a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
                    PR.Error String
err -> do
                        let src :: [a]
src = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf
                        (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
                            ( ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err)
                            , Stream m a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append ([a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                            )

            Skip s
s -> SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s List a
buf s
pst
            Step s a
Stop -> SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
forall {m :: * -> *}.
Applicative m =>
SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst

    go1 :: SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
_ s
s a
x !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List []) s
pst1
            PR.Partial Int
1 s
pst1 -> do
                SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
            PR.Partial Int
n s
_ ->
                String -> m (Either ParseError b, Stream m a)
forall a. (?callStack::CallStack) => String -> a
error (String -> m (Either ParseError b, Stream m a))
-> String -> m (Either ParseError b, Stream m a)
forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Partial n = " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n
            PR.Continue Int
0 s
pst1 ->
                SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List [a
x]) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC -> s -> a -> s -> m (Either ParseError b, Stream m a)
go1 SPEC
SPEC s
s a
x s
pst1
            PR.Continue Int
n s
_ -> do
                String -> m (Either ParseError b, Stream m a)
forall a. (?callStack::CallStack) => String -> a
error (String -> m (Either ParseError b, Stream m a))
-> String -> m (Either ParseError b, Stream m a)
forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Continue n = " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n
            PR.Done Int
0 b
b -> do
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, (State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
            PR.Done Int
1 b
b -> do
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Applicative m =>
a -> Stream m a -> Stream m a
StreamD.cons a
x ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
            PR.Done Int
n b
_ -> do
                String -> m (Either ParseError b, Stream m a)
forall a. (?callStack::CallStack) => String -> a
error (String -> m (Either ParseError b, Stream m a))
-> String -> m (Either ParseError b, Stream m a)
forall a b. (a -> b) -> a -> b
$ String
"parseBreak: parser bug, go1: Done n = " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n
            PR.Error String
err ->
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
                    ( ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err)
                    , Stream m a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append (a -> Stream m a
forall (m :: * -> *) a. Applicative m => a -> Stream m a
fromPure a
x) ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    )

    gobuf :: SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf !SPEC
_ s
s List a
buf (List []) !s
pst = SPEC -> s -> List a -> s -> m (Either ParseError b, Stream m a)
go SPEC
SPEC s
s List a
buf s
pst
    gobuf !SPEC
_ s
s List a
buf (List (a
x:[a]
xs)) !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List []) ([a] -> List a
forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Partial Int
n s
pst1 -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List []) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Continue Int
0 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) ([a] -> List a
forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s List a
buf ([a] -> List a
forall a. [a] -> List a
List (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)) s
pst1
            PR.Continue Int
n s
pst1 -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> s
-> List a
-> List a
-> s
-> m (Either ParseError b, Stream m a)
gobuf SPEC
SPEC s
s ([a] -> List a
forall a. [a] -> List a
List [a]
buf1) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
n b
b -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, Stream m a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append ([a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s))
            PR.Error String
err -> do
                let src :: [a]
src = ([a] -> [a]
forall a. [a] -> [a]
Prelude.reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ List a -> [a]
forall a. List a -> [a]
getList List a
buf) [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
                    ( ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err)
                    , Stream m a -> Stream m a -> Stream m a
forall (m :: * -> *) a.
Monad m =>
Stream m a -> Stream m a -> Stream m a
Nesting.append ([a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src) ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
                    )

    -- This is simplified gobuf
    goExtract :: SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract !SPEC
_ List a
buf (List []) !s
pst = SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst
    goExtract !SPEC
_ List a
buf (List (a
x:[a]
xs)) !s
pst = do
        Step s b
pRes <- s -> a -> m (Step s b)
pstep s
pst a
x
        case Step s b
pRes of
            PR.Partial Int
0 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC ([a] -> List a
forall a. [a] -> List a
List []) ([a] -> List a
forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Partial Int
n s
pst1 -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC ([a] -> List a
forall a. [a] -> List a
List []) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Continue Int
0 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC ([a] -> List a
forall a. [a] -> List a
List (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) ([a] -> List a
forall a. [a] -> List a
List [a]
xs) s
pst1
            PR.Continue Int
1 s
pst1 ->
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC List a
buf ([a] -> List a
forall a. [a] -> List a
List (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)) s
pst1
            PR.Continue Int
n s
pst1 -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC ([a] -> List a
forall a. [a] -> List a
List [a]
buf1) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
n b
b -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, [a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)
            PR.Error String
err -> do
                let src :: [a]
src = ([a] -> [a]
forall a. [a] -> [a]
Prelude.reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ List a -> [a]
forall a. List a -> [a]
getList List a
buf) [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), [a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)

    -- This is simplified goExtract
    -- XXX Use SPEC?
    {-# INLINE goStop #-}
    goStop :: SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
_ List a
buf s
pst = do
        Step s b
pRes <- s -> m (Step s b)
extract s
pst
        case Step s b
pRes of
            PR.Partial Int
_ s
_ -> String -> m (Either ParseError b, Stream m a)
forall a. (?callStack::CallStack) => String -> a
error String
"Bug: parseBreak: Partial in extract"
            PR.Continue Int
0 s
pst1 -> SPEC -> List a -> s -> m (Either ParseError b, Stream m a)
goStop SPEC
SPEC List a
buf s
pst1
            PR.Continue Int
n s
pst1 -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let ([a]
src0, [a]
buf1) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n (List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                SPEC
-> List a -> List a -> s -> m (Either ParseError b, Stream m a)
goExtract SPEC
SPEC ([a] -> List a
forall a. [a] -> List a
List [a]
buf1) ([a] -> List a
forall a. [a] -> List a
List [a]
src) s
pst1
            PR.Done Int
0 b
b -> (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, Stream m a
forall (m :: * -> *) a. Applicative m => Stream m a
StreamD.nil)
            PR.Done Int
n b
b -> do
                Bool -> m () -> m ()
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (List a -> [a]
forall a. List a -> [a]
getList List a
buf)) (() -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ())
                let src0 :: [a]
src0 = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
Prelude.take Int
n (List a -> [a]
forall a. List a -> [a]
getList List a
buf)
                    src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse [a]
src0
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Either ParseError b
forall a b. b -> Either a b
Right b
b, [a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)
            PR.Error String
err -> do
                let src :: [a]
src  = [a] -> [a]
forall a. [a] -> [a]
Prelude.reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ List a -> [a]
forall a. List a -> [a]
getList List a
buf
                (Either ParseError b, Stream m a)
-> m (Either ParseError b, Stream m a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (ParseError -> Either ParseError b
forall a b. a -> Either a b
Left (String -> ParseError
ParseError String
err), [a] -> Stream m a
forall (m :: * -> *) a. Applicative m => [a] -> Stream m a
fromList [a]
src)

-- | Parse a stream using the supplied 'Parser'.
--
{-# INLINE parseBreak #-}
parseBreak :: Monad m => PR.Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreak :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreak = Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseError b, Stream m a)
parseBreakD

------------------------------------------------------------------------------
-- Specialized Folds
------------------------------------------------------------------------------

-- benchmark after dropping 1 item from stream or using unfolds
{-# INLINE_NORMAL null #-}
null :: Monad m => Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
null = fold Fold.null
#else
null :: forall (m :: * -> *) a. Monad m => Stream m a -> m Bool
null = (a -> m Bool -> m Bool) -> m Bool -> Stream m a -> m Bool
forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
_ m Bool
_ -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False) (Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True)
#endif

{-# INLINE_NORMAL head #-}
head :: Monad m => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
head = fold Fold.one
#else
head :: forall (m :: * -> *) a. Monad m => Stream m a -> m (Maybe a)
head = (a -> m (Maybe a) -> m (Maybe a))
-> m (Maybe a) -> Stream m a -> m (Maybe a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m (Maybe a)
_ -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
x)) (Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing)
#endif

{-# INLINE_NORMAL headElse #-}
headElse :: Monad m => a -> Stream m a -> m a
headElse :: forall (m :: * -> *) a. Monad m => a -> Stream m a -> m a
headElse a
a = (a -> m a -> m a) -> m a -> Stream m a -> m a
forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m a
_ -> a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x) (a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
a)

-- Does not fuse, has the same performance as the StreamK version.
{-# INLINE_NORMAL tail #-}
tail :: Monad m => Stream m a -> m (Maybe (Stream m a))
tail :: forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (Stream m a))
tail (UnStream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m (Maybe (Stream m a))
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m (Maybe (Stream m a))
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
_ s
s -> Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Stream m a -> Maybe (Stream m a)
forall a. a -> Maybe a
Just (Stream m a -> Maybe (Stream m a))
-> Stream m a -> Maybe (Stream m a)
forall a b. (a -> b) -> a -> b
$ (State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
step s
s)
            Skip  s
s   -> SPEC -> s -> m (Maybe (Stream m a))
go SPEC
SPEC s
s
            Step s a
Stop      -> Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (Stream m a)
forall a. Maybe a
Nothing

-- XXX will it fuse? need custom impl?
{-# INLINE_NORMAL last #-}
last :: Monad m => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
last = fold Fold.last
#else
last :: forall (m :: * -> *) a. Monad m => Stream m a -> m (Maybe a)
last = (Maybe a -> a -> Maybe a) -> Maybe a -> Stream m a -> m (Maybe a)
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> b) -> b -> Stream m a -> m b
foldl' (\Maybe a
_ a
y -> a -> Maybe a
forall a. a -> Maybe a
Just a
y) Maybe a
forall a. Maybe a
Nothing
#endif

-- XXX Use the foldrM based impl instead
{-# INLINE_NORMAL elem #-}
elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
elem e = fold (Fold.elem e)
#else
-- elem e m = foldrM (\x xs -> if x == e then return True else xs) (return False) m
elem :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
elem a
e (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
e -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
              | Bool
otherwise -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
#endif

{-# INLINE_NORMAL notElem #-}
notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
notElem :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
notElem a
e Stream m a
s = (Bool -> Bool) -> m Bool -> m Bool
forall a b. (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bool -> Bool
not (a -> Stream m a -> m Bool
forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
elem a
e Stream m a
s)

{-# INLINE_NORMAL all #-}
all :: Monad m => (a -> Bool) -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
all p = fold (Fold.all p)
#else
-- all p m = foldrM (\x xs -> if p x then xs else return False) (return True) m
all :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m Bool
all a -> Bool
p (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a -> Bool
p a
x -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
              | Bool
otherwise -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
#endif

{-# INLINE_NORMAL any #-}
any :: Monad m => (a -> Bool) -> Stream m a -> m Bool
#ifdef USE_FOLDS_EVERYWHERE
any p = fold (Fold.any p)
#else
-- any p m = foldrM (\x xs -> if p x then return True else xs) (return False) m
any :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m Bool
any a -> Bool
p (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m Bool
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m Bool
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a -> Bool
p a
x -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
              | Bool
otherwise -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Skip s
s -> SPEC -> s -> m Bool
go SPEC
SPEC s
s
            Step s a
Stop   -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
#endif

{-# INLINE_NORMAL maximum #-}
maximum :: (Monad m, Ord a) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
maximum = fold Fold.maximum
#else
maximum :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
Stream m a -> m (Maybe a)
maximum (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
state
  where
    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
acc a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
              | Bool
otherwise -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL maximumBy #-}
maximumBy :: Monad m => (a -> a -> Ordering) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
maximumBy cmp = fold (Fold.maximumBy cmp)
#else
maximumBy :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> Ordering) -> Stream m a -> m (Maybe a)
maximumBy a -> a -> Ordering
cmp (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
state
  where
    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> case a -> a -> Ordering
cmp a
acc a
x of
                Ordering
GT -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
                Ordering
_  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL minimum #-}
minimum :: (Monad m, Ord a) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
minimum = fold Fold.minimum
#else
minimum :: forall (m :: * -> *) a.
(Monad m, Ord a) =>
Stream m a -> m (Maybe a)
minimum (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
state

    where

    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s
              | a
acc a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
x  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
              | Bool
otherwise -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL minimumBy #-}
minimumBy :: Monad m => (a -> a -> Ordering) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
minimumBy cmp = fold (Fold.minimumBy cmp)
#else
minimumBy :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> Ordering) -> Stream m a -> m (Maybe a)
minimumBy a -> a -> Ordering
cmp (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
state

    where

    go :: SPEC -> Maybe' a -> s -> m (Maybe a)
go !SPEC
_ Maybe' a
Nothing' s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
            Skip  s
s   -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
s
            Step s a
Stop      -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
    go !SPEC
_ (Just' a
acc) s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> case a -> a -> Ordering
cmp a
acc a
x of
                Ordering
GT -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
s
                Ordering
_  -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Skip s
s -> SPEC -> Maybe' a -> s -> m (Maybe a)
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
acc) s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
acc)
#endif

{-# INLINE_NORMAL (!!) #-}
(!!) :: (Monad m) => Stream m a -> Int -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
stream !! i = fold (Fold.index i) stream
#else
(Stream State StreamK m a -> s -> m (Step s a)
step s
state) !! :: forall (m :: * -> *) a. Monad m => Stream m a -> Int -> m (Maybe a)
!! Int
i = SPEC -> Int -> s -> m (Maybe a)
forall {t}. (Ord t, Num t) => SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC Int
i s
state

    where

    go :: SPEC -> t -> s -> m (Maybe a)
go !SPEC
_ !t
n s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s | t
n t -> t -> Bool
forall a. Ord a => a -> a -> Bool
< t
0 -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
                      | t
n t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe a -> m (Maybe a)) -> Maybe a -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
x
                      | Bool
otherwise -> SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC (t
n t -> t -> t
forall a. Num a => a -> a -> a
- t
1) s
s
            Skip s
s -> SPEC -> t -> s -> m (Maybe a)
go SPEC
SPEC t
n s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
#endif

{-# INLINE_NORMAL lookup #-}
lookup :: (Monad m, Eq a) => a -> Stream m (a, b) -> m (Maybe b)
#ifdef USE_FOLDS_EVERYWHERE
lookup e = fold (Fold.lookup e)
#else
lookup :: forall (m :: * -> *) a b.
(Monad m, Eq a) =>
a -> Stream m (a, b) -> m (Maybe b)
lookup a
e = ((a, b) -> m (Maybe b) -> m (Maybe b))
-> m (Maybe b) -> Stream m (a, b) -> m (Maybe b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\(a
a, b
b) m (Maybe b)
xs -> if a
e a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a then Maybe b -> m (Maybe b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Maybe b
forall a. a -> Maybe a
Just b
b) else m (Maybe b)
xs)
                   (Maybe b -> m (Maybe b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe b
forall a. Maybe a
Nothing)
#endif

{-# INLINE_NORMAL findM #-}
findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
findM p = fold (Fold.findM p)
#else
findM :: forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Stream m a -> m (Maybe a)
findM a -> m Bool
p = (a -> m (Maybe a) -> m (Maybe a))
-> m (Maybe a) -> Stream m a -> m (Maybe a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b -> m b) -> m b -> Stream m a -> m b
foldrM (\a
x m (Maybe a)
xs -> a -> m Bool
p a
x m Bool -> (Bool -> m (Maybe a)) -> m (Maybe a)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Bool
r -> if Bool
r then Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
x) else m (Maybe a)
xs)
                   (Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing)
#endif

{-# INLINE find #-}
find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
find :: forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> m (Maybe a)
find a -> Bool
p = (a -> m Bool) -> Stream m a -> m (Maybe a)
forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Stream m a -> m (Maybe a)
findM (Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> m Bool) -> (a -> Bool) -> a -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

{-# INLINE toListRev #-}
toListRev :: Monad m => Stream m a -> m [a]
#ifdef USE_FOLDS_EVERYWHERE
toListRev = fold Fold.toListRev
#else
toListRev :: forall (m :: * -> *) a. Monad m => Stream m a -> m [a]
toListRev = ([a] -> a -> [a]) -> [a] -> Stream m a -> m [a]
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> b) -> b -> Stream m a -> m b
foldl' ((a -> [a] -> [a]) -> [a] -> a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) []
#endif

------------------------------------------------------------------------------
-- Transformation comprehensions
------------------------------------------------------------------------------

{-# INLINE_NORMAL the #-}
the :: (Eq a, Monad m) => Stream m a -> m (Maybe a)
#ifdef USE_FOLDS_EVERYWHERE
the = fold Fold.the
#else
the :: forall a (m :: * -> *).
(Eq a, Monad m) =>
Stream m a -> m (Maybe a)
the (Stream State StreamK m a -> s -> m (Step s a)
step s
state) = SPEC -> s -> m (Maybe a)
go SPEC
SPEC s
state
  where
    go :: SPEC -> s -> m (Maybe a)
go !SPEC
_ s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
x s
s
            Skip s
s    -> SPEC -> s -> m (Maybe a)
go SPEC
SPEC s
s
            Step s a
Stop      -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
    go' :: SPEC -> a -> s -> m (Maybe a)
go' !SPEC
_ a
n s
st = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
step State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
st
        case Step s a
r of
            Yield a
x s
s | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
n -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
n s
s
                      | Bool
otherwise -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing
            Skip s
s -> SPEC -> a -> s -> m (Maybe a)
go' SPEC
SPEC a
n s
s
            Step s a
Stop   -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> Maybe a
forall a. a -> Maybe a
Just a
n)
#endif

------------------------------------------------------------------------------
-- Map and Fold
------------------------------------------------------------------------------

-- | Execute a monadic action for each element of the 'Stream'
{-# INLINE_NORMAL mapM_ #-}
mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
#ifdef USE_FOLDS_EVERYWHERE
mapM_ f = fold (Fold.drainBy f)
#else
mapM_ :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
mapM_ a -> m b
m = Stream m b -> m ()
forall (m :: * -> *) a. Monad m => Stream m a -> m ()
drain (Stream m b -> m ())
-> (Stream m a -> Stream m b) -> Stream m a -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m b) -> Stream m a -> Stream m b
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> Stream m b
mapM a -> m b
m
#endif

------------------------------------------------------------------------------
-- Multi-stream folds
------------------------------------------------------------------------------

-- | Returns 'True' if the first stream is the same as or a prefix of the
-- second. A stream is a prefix of itself.
--
-- >>> Stream.isPrefixOf (Stream.fromList "hello") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
{-# INLINE_NORMAL isPrefixOf #-}
isPrefixOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isPrefixOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isPrefixOf (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m Bool
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa'    -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop        -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa s
sb'
                    else Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop     -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False

-- | Returns 'True' if all the elements of the first stream occur, in order, in
-- the second stream. The elements do not have to occur consecutively. A stream
-- is a subsequence of itself.
--
-- >>> Stream.isSubsequenceOf (Stream.fromList "hlo") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
{-# INLINE_NORMAL isSubsequenceOf #-}
isSubsequenceOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isSubsequenceOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isSubsequenceOf (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m Bool
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa s
sb'
                    else SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m Bool
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop -> Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False

-- | @stripPrefix prefix input@ strips the @prefix@ stream from the @input@
-- stream if it is a prefix of input. Returns 'Nothing' if the input does not
-- start with the given prefix, stripped input otherwise. Returns @Just nil@
-- when the prefix is the same as the input stream.
--
-- Space: @O(1)@
--
{-# INLINE_NORMAL stripPrefix #-}
stripPrefix
    :: (Monad m, Eq a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (Stream State StreamK m a -> s -> m (Step s a)
stepa s
ta) (Stream State StreamK m a -> s -> m (Step s a)
stepb s
tb) = SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
ta s
tb

    where

    go :: SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go !SPEC
_ Maybe' a
Nothing' s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepa State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sa
        case Step s a
r of
            Yield a
x s
sa' -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa' s
sb
            Skip s
sa'    -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa' s
sb
            Step s a
Stop        -> Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (Stream m a) -> m (Maybe (Stream m a)))
-> Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a b. (a -> b) -> a -> b
$ Stream m a -> Maybe (Stream m a)
forall a. a -> Maybe a
Just ((State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
forall (m :: * -> *) a s.
(State StreamK m a -> s -> m (Step s a)) -> s -> Stream m a
Stream State StreamK m a -> s -> m (Step s a)
stepb s
sb)

    go !SPEC
_ (Just' a
x) s
sa s
sb = do
        Step s a
r <- State StreamK m a -> s -> m (Step s a)
stepb State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a. State t m a
defState s
sb
        case Step s a
r of
            Yield a
y s
sb' ->
                if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
                    then SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC Maybe' a
forall a. Maybe' a
Nothing' s
sa s
sb'
                    else Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (Stream m a)
forall a. Maybe a
Nothing
            Skip s
sb' -> SPEC -> Maybe' a -> s -> s -> m (Maybe (Stream m a))
go SPEC
SPEC (a -> Maybe' a
forall a. a -> Maybe' a
Just' a
x) s
sa s
sb'
            Step s a
Stop     -> Maybe (Stream m a) -> m (Maybe (Stream m a))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (Stream m a)
forall a. Maybe a
Nothing

-- | Returns 'True' if the first stream is an infix of the second. A stream is
-- considered an infix of itself.
--
-- >>> s = Stream.fromList "hello" :: Stream IO Char
-- >>> Stream.isInfixOf s s
-- True
--
-- Space: @O(n)@ worst case where @n@ is the length of the infix.
--
-- /Pre-release/
--
-- /Requires 'Storable' constraint/
--
{-# INLINE isInfixOf #-}
isInfixOf :: (MonadIO m, Eq a, Enum a, Storable a, Unbox a)
    => Stream m a -> Stream m a -> m Bool
isInfixOf :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Enum a, Storable a, Unbox a) =>
Stream m a -> Stream m a -> m Bool
isInfixOf Stream m a
infx Stream m a
stream = do
    Array a
arr <- Fold m a (Array a) -> Stream m a -> m (Array a)
forall (m :: * -> *) a b.
Monad m =>
Fold m a b -> Stream m a -> m b
fold Fold m a (Array a)
forall (m :: * -> *) a. (MonadIO m, Unbox a) => Fold m a (Array a)
Array.write Stream m a
infx
    -- XXX can use breakOnSeq instead (when available)
    Bool
r <- Stream m () -> m Bool
forall (m :: * -> *) a. Monad m => Stream m a -> m Bool
null (Stream m () -> m Bool) -> Stream m () -> m Bool
forall a b. (a -> b) -> a -> b
$ Int -> Stream m () -> Stream m ()
forall (m :: * -> *) a. Monad m => Int -> Stream m a -> Stream m a
StreamD.drop Int
1 (Stream m () -> Stream m ()) -> Stream m () -> Stream m ()
forall a b. (a -> b) -> a -> b
$ Array a -> Fold m a () -> Stream m a -> Stream m ()
forall (m :: * -> *) a b.
(MonadIO m, Storable a, Unbox a, Enum a, Eq a) =>
Array a -> Fold m a b -> Stream m a -> Stream m b
Nesting.splitOnSeq Array a
arr Fold m a ()
forall (m :: * -> *) a. Monad m => Fold m a ()
Fold.drain Stream m a
stream
    Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Bool
not Bool
r)

-- Note: isPrefixOf uses the prefix stream only once. In contrast, isSuffixOf
-- may use the suffix stream many times. To run in optimal memory we do not
-- want to buffer the suffix stream in memory therefore  we need an ability to
-- clone (or consume it multiple times) the suffix stream without any side
-- effects so that multiple potential suffix matches can proceed in parallel
-- without buffering the suffix stream. For example, we may create the suffix
-- stream from a file handle, however, if we evaluate the stream multiple
-- times, once for each match, we will need a different file handle each time
-- which may exhaust the file descriptors. Instead, we want to share the same
-- underlying file descriptor, use pread on it to generate the stream and clone
-- the stream for each match. Therefore the suffix stream should be built in
-- such a way that it can be consumed multiple times without any problems.

-- XXX Can be implemented with better space/time complexity.
-- Space: @O(n)@ worst case where @n@ is the length of the suffix.

-- | Returns 'True' if the first stream is a suffix of the second. A stream is
-- considered a suffix of itself.
--
-- >>> Stream.isSuffixOf (Stream.fromList "hello") (Stream.fromList "hello" :: Stream IO Char)
-- True
--
-- Space: @O(n)@, buffers entire input stream and the suffix.
--
-- /Pre-release/
--
-- /Suboptimal/ - Help wanted.
--
{-# INLINE isSuffixOf #-}
isSuffixOf :: (Monad m, Eq a) => Stream m a -> Stream m a -> m Bool
isSuffixOf :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
isSuffixOf Stream m a
suffix Stream m a
stream =
    Stream m a -> Stream m a
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
suffix Stream m a -> Stream m a -> m Bool
forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
`isPrefixOf` Stream m a -> Stream m a
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
stream

-- | Much faster than 'isSuffixOf'.
{-# INLINE isSuffixOfUnbox #-}
isSuffixOfUnbox :: (MonadIO m, Eq a, Unbox a) =>
    Stream m a -> Stream m a -> m Bool
isSuffixOfUnbox :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Unbox a) =>
Stream m a -> Stream m a -> m Bool
isSuffixOfUnbox Stream m a
suffix Stream m a
stream =
    Stream m a -> Stream m a
forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
suffix Stream m a -> Stream m a -> m Bool
forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m Bool
`isPrefixOf` Stream m a -> Stream m a
forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
stream

-- | Drops the given suffix from a stream. Returns 'Nothing' if the stream does
-- not end with the given suffix. Returns @Just nil@ when the suffix is the
-- same as the stream.
--
-- It may be more efficient to convert the stream to an Array and use
-- stripSuffix on that especially if the elements have a Storable or Prim
-- instance.
--
-- Space: @O(n)@, buffers the entire input stream as well as the suffix
--
-- /Pre-release/
{-# INLINE stripSuffix #-}
stripSuffix
    :: (Monad m, Eq a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffix :: forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffix Stream m a
m1 Stream m a
m2 =
    (Stream m a -> Stream m a)
-> Maybe (Stream m a) -> Maybe (Stream m a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Stream m a -> Stream m a
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse
        (Maybe (Stream m a) -> Maybe (Stream m a))
-> m (Maybe (Stream m a)) -> m (Maybe (Stream m a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream m a -> Stream m a -> m (Maybe (Stream m a))
forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (Stream m a -> Stream m a
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
m1) (Stream m a -> Stream m a
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
StreamD.reverse Stream m a
m2)

-- | Much faster than 'stripSuffix'.
{-# INLINE stripSuffixUnbox #-}
stripSuffixUnbox
    :: (MonadIO m, Eq a, Unbox a)
    => Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffixUnbox :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Unbox a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripSuffixUnbox Stream m a
m1 Stream m a
m2 =
    (Stream m a -> Stream m a)
-> Maybe (Stream m a) -> Maybe (Stream m a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Stream m a -> Stream m a
forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox
        (Maybe (Stream m a) -> Maybe (Stream m a))
-> m (Maybe (Stream m a)) -> m (Maybe (Stream m a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Stream m a -> Stream m a -> m (Maybe (Stream m a))
forall (m :: * -> *) a.
(Monad m, Eq a) =>
Stream m a -> Stream m a -> m (Maybe (Stream m a))
stripPrefix (Stream m a -> Stream m a
forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
m1) (Stream m a -> Stream m a
forall (m :: * -> *) a.
(MonadIO m, Unbox a) =>
Stream m a -> Stream m a
StreamD.reverseUnbox Stream m a
m2)