{-# 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 Parser
      parse
    , parsePos
    , parseBreak
    , parseBreakPos

    -- * Deconstruction
    , uncons

    -- * Right Folds
    , foldr1

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

    -- * To containers
    , toListRev

    -- * Multi-Stream Folds
    -- | These should probably be expressed using parsers.
    , isPrefixOf
    , isInfixOf
    , isSuffixOf
    , isSuffixOfUnbox
    , isSubsequenceOf
    , stripPrefix
    , stripSuffix
    , stripSuffixUnbox

    -- * Deprecated
    , parseD
    , parseBreakD
    )
where

#include "inline.hs"
#include "deprecation.h"

import Control.Monad.IO.Class (MonadIO(..))
import GHC.Types (SPEC(..))
import Streamly.Internal.Data.Parser (ParseError(..), ParseErrorPos(..))
import Streamly.Internal.Data.SVar.Type (adaptState, 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.ParserDrivers as Drivers
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, init, tail, (!!))
import Streamly.Internal.Data.Stream.Type hiding (splitAt)

#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
------------------------------------------------------------------------------

-- 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.

-- | Parse a stream using the supplied 'Parser'.
--
{-# INLINE parseBreak #-}
parseBreak, parseBreakD :: 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)
Drivers.parseBreak

RENAME(parseBreakD,parseBreak)

-- | Like 'parseBreak' but includes stream position information in the error
-- messages.
--
{-# INLINE parseBreakPos #-}
parseBreakPos :: Monad m =>
    PR.Parser a m b -> Stream m a -> m (Either ParseErrorPos b, Stream m a)
parseBreakPos :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b
-> Stream m a -> m (Either ParseErrorPos b, Stream m a)
parseBreakPos = Parser a m b
-> Stream m a -> m (Either ParseErrorPos b, Stream m a)
forall (m :: * -> *) a b.
Monad m =>
Parser a m b
-> Stream m a -> m (Either ParseErrorPos b, Stream m a)
Drivers.parseBreakPos

-- | 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, parseD :: 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
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)
parseBreak 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

RENAME(parseD,parse)

-- | Like 'parse' but includes stream position information in the error
-- messages.
--
-- >>> Stream.parsePos (Parser.takeEQ 2 Fold.drain) (Stream.fromList [1])
-- Left (ParseErrorPos 1 "takeEQ: Expecting exactly 2 elements, input terminated on 1")
--
{-# INLINE [3] parsePos #-}
parsePos :: Monad m => PR.Parser a m b -> Stream m a -> m (Either ParseErrorPos b)
parsePos :: forall (m :: * -> *) a b.
Monad m =>
Parser a m b -> Stream m a -> m (Either ParseErrorPos b)
parsePos Parser a m b
parser Stream m a
strm = do
    (Either ParseErrorPos b
b, Stream m a
_) <- Parser a m b
-> Stream m a -> m (Either ParseErrorPos b, Stream m a)
forall (m :: * -> *) a b.
Monad m =>
Parser a m b
-> Stream m a -> m (Either ParseErrorPos b, Stream m a)
parseBreakPos Parser a m b
parser Stream m a
strm
    Either ParseErrorPos b -> m (Either ParseErrorPos b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Either ParseErrorPos b
b

------------------------------------------------------------------------------
-- 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 init #-}
init :: Monad m => Stream m a -> m (Maybe (Stream m a))
init :: forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (Stream m a))
init Stream m a
stream = 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
stream
    case Maybe (a, Stream m a)
r of
        Maybe (a, Stream m a)
Nothing -> 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
        Just (a
h, Stream State StreamK m a -> s -> m (Step s a)
step1 s
state1) ->
            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 (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 -> (a, s) -> m (Step (a, s) a))
-> (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 -> (a, s) -> m (Step (a, s) a)
forall {m :: * -> *} {a}.
State StreamK m a -> (a, s) -> m (Step (a, s) a)
step (a
h, s
state1)

            where

            step :: State StreamK m a -> (a, s) -> m (Step (a, s) a)
step State StreamK m a
gst (a
a, s
s1) = do
                Step s a
res <- State StreamK m a -> s -> m (Step s a)
step1 (State StreamK m a -> State StreamK m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a (n :: * -> *) b.
State t m a -> State t n b
adaptState State StreamK m a
gst) s
s1
                Step (a, s) a -> m (Step (a, s) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (a, s) a -> m (Step (a, s) a))
-> Step (a, s) a -> m (Step (a, s) a)
forall a b. (a -> b) -> a -> b
$
                    case Step s a
res of
                        Yield a
x s
s -> a -> (a, s) -> Step (a, s) a
forall s a. a -> s -> Step s a
Yield a
a (a
x, s
s)
                        Skip s
s -> (a, s) -> Step (a, s) a
forall s a. s -> Step s a
Skip (a
a, s
s)
                        Step s a
Stop -> Step (a, s) a
forall s a. Step s a
Stop

-- | Same as:
--
-- >>> tail = fmap (fmap snd) . Stream.uncons
--
-- 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 = (Maybe (a, Stream m a) -> Maybe (Stream m a))
-> m (Maybe (a, Stream m a)) -> m (Maybe (Stream m a))
forall a b. (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((a, Stream m a) -> Stream m a)
-> Maybe (a, 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 (a, Stream m a) -> Stream m a
forall a b. (a, b) -> b
snd) (m (Maybe (a, Stream m a)) -> m (Maybe (Stream m a)))
-> (Stream m a -> m (Maybe (a, Stream m a)))
-> Stream m a
-> m (Maybe (Stream m a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Stream m a -> m (Maybe (a, Stream m a))
forall (m :: * -> *) a.
Monad m =>
Stream m a -> m (Maybe (a, Stream m a))
uncons
{-
tail (UnStream step state) = go SPEC state
  where
    go !_ st = do
        r <- step defState st
        case r of
            Yield _ s -> return (Just $ Stream step s)
            Skip  s   -> go SPEC s
            Stop      -> return 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
e a -> Stream m a -> m Bool
forall (m :: * -> *) a.
(Monad m, Eq a) =>
a -> Stream m a -> m Bool
`elem` 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, Unbox a)
    => Stream m a -> Stream m a -> m Bool
isInfixOf :: forall (m :: * -> *) a.
(MonadIO m, Eq a, Enum 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.create 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, Unbox a, Enum a, Eq a) =>
Array a -> Fold m a b -> Stream m a -> Stream m b
Nesting.splitSepBySeq_ 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)