2-- Module : Streamly.Internal.Data.Stream.IsStream.Eliminate
3-- Copyright : (c) 2017 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- This module contains functions ending in the shape:
15-- We call them stream folding functions, they reduce a stream @t m a@ to a
16-- monadic value @m b@.
18module Streamly.Internal.Data.Stream.IsStream.Eliminate
24 -- See "Streamly.Internal.Data.Fold".
29 -- * Running a 'Parser'
30 -- "Streamly.Internal.Data.Parser".
37 -- * Stream Deconstruction
38 -- | foldr and foldl do not provide the remaining stream. 'uncons' is more
39 -- general, as it can be used to implement those as well. It allows to use
40 -- the stream one element at a time, and we have the remaining stream all
49 -- Lazy left folds are useful only for reversing the stream
57 -- * Specific Fold Functions
58 -- | Folds as functions of the shape @t m a -> m b@.
60 -- These functions are good to run individually but they do not compose
61 -- well. Prefer writing folds as the 'Fold' data type. Use folds from
62 -- "Streamly.Internal.Data.Fold" instead of using the functions in this
65 -- This section can possibly be removed in future. Are these better in
66 -- some case compared to 'Fold'? When the input stream is in CPS style
67 -- (StreamK) we may want to rewrite the function call to CPS implementation
68 -- of the fold through these definitions. Will that be more efficient for
73 -- -- ** To Summary (Full Folds)
82 -- -- ** To Summary (Maybe) (Full Folds)
91 -- -- ** To Elements (Partial Folds)
95 -- -- | Folds that extract selected elements of a stream or their properties.
107 -- -- ** To Boolean (Partial Folds)
123 -- * Concurrent Folds
128 -- * Multi-Stream folds
133 -- finding subsequences
139 -- trimming sequences
157import Control.Monad.Catch (MonadThrow)
158import Control.Monad.IO.Class (MonadIO(..))
159import Control.Monad.Trans.Class (MonadTrans(..))
160import Foreign.Storable (Storable)
161import Streamly.Internal.Control.Concurrent (MonadAsync)
162import Streamly.Internal.Data.Parser (Parser (..))
163import Streamly.Internal.Data.SVar (defState)
164import Streamly.Internal.Data.Stream.IsStream.Common
165 ( fold, fold_, foldOn, drop, findIndices, reverse, splitOnSeq, take
166 , takeWhile, mkParallel)
167import Streamly.Internal.Data.Stream.IsStream.Type
168 (IsStream, toStreamS, fromStreamD, toStreamD)
169import Streamly.Internal.Data.Stream.Serial (SerialT(..))
171import qualified Streamly.Internal.Data.Array.Foreign.Type as A
172import qualified Streamly.Internal.Data.Fold as FL
173import qualified Streamly.Internal.Data.Stream.IsStream.Type as IsStream
174import qualified Streamly.Internal.Data.Stream.StreamD as D
175import qualified Streamly.Internal.Data.Stream.StreamK.Type as K
176import qualified Streamly.Internal.Data.Parser.ParserD as PRD
177import qualified Streamly.Internal.Data.Parser.ParserK.Type as PRK
178import qualified System.IO as IO
179#ifdef USE_STREAMK_ONLY
180import qualified Streamly.Internal.Data.Stream.StreamK as S
182import qualified Streamly.Internal.Data.Stream.StreamD as S
186 ( drop, take, takeWhile, foldr , foldl, mapM_, sequence, all, any, sum
187 , product, elem, notElem, maximum, minimum, head, last, tail, length
188 , null , reverse, init, and, or, lookup, foldr1, (!!) , splitAt, break
193-- >>> import Streamly.Prelude (SerialT)
194-- >>> import qualified Streamly.Prelude as Stream
195-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream
196-- >>> import qualified Streamly.Internal.Data.Parser as Parser
197-- >>> import qualified Streamly.Data.Fold as Fold
199------------------------------------------------------------------------------
201------------------------------------------------------------------------------
203-- | Decompose a stream into its head and tail. If the stream is empty, returns
204-- 'Nothing'. If the stream is non-empty, returns @Just (a, ma)@, where @a@ is
205-- the head of the stream and @ma@ its tail.
207-- This is a brute force primitive. Avoid using it as long as possible, use it
208-- when no other combinator can do the job. This can be used to do pretty much
209-- anything in an imperative manner, as it just breaks down the stream into
210-- individual elements and we can loop over them as we deem fit. For example,
211-- this can be used to convert a streamly stream into other stream types.
213-- All the folds in this module can be expressed in terms of 'uncons', however
214-- the specific implementations are generally more efficient.
218uncons :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (a, t m a))
219uncons (SerialT m) = fmap (fmap (fmap IsStream.fromStream)) $ K.uncons m
221------------------------------------------------------------------------------
223------------------------------------------------------------------------------
225-- | Right associative/lazy pull fold. @foldrM build final stream@ constructs
226-- an output structure using the step function @build@. @build@ is invoked with
227-- the next input element and the remaining (lazy) tail of the output
228-- structure. It builds a lazy output expression using the two. When the "tail
229-- structure" in the output expression is evaluated it calls @build@ again thus
230-- lazily consuming the input @stream@ until either the output expression built
231-- by @build@ is free of the "tail" or the input is exhausted in which case
232-- @final@ is used as the terminating case for the output structure. For more
233-- details see the description in the previous section.
235-- Example, determine if any element is 'odd' in a stream:
237-- >>> Stream.foldrM (\x xs -> if odd x then return True else xs) (return False) $ Stream.fromList (2:4:5:undefined)
240-- /Since: 0.7.0 (signature changed)/
242-- /Since: 0.2.0 (signature changed)/
246foldrM :: Monad m => (a -> m b -> m b) -> m b -> SerialT m a -> m b
247foldrM = IsStream.foldrM
249-- | Right fold, lazy for lazy monads and pure streams, and strict for strict
252-- Please avoid using this routine in strict monads like IO unless you need a
253-- strict right fold. This is provided only for use in lazy monads (e.g.
254-- Identity) or pure streams. Note that with this signature it is not possible
255-- to implement a lazy foldr when the monad @m@ is strict. In that case it
256-- would be strict in its accumulator and therefore would necessarily consume
261foldr :: Monad m => (a -> b -> b) -> b -> SerialT m a -> m b
262foldr = IsStream.foldr
264-- XXX This seems to be of limited use as it cannot be used to construct
265-- recursive structures and for reduction foldl1' is better.
267-- | Lazy right fold for non-empty streams, using first element as the starting
268-- value. Returns 'Nothing' if the stream is empty.
272{-# DEPRECATED foldr1 "Use foldrM instead." #-}
273foldr1 :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
274foldr1 f m = S.foldr1 f (toStreamS m)
276------------------------------------------------------------------------------
278------------------------------------------------------------------------------
280-- | Lazy left fold to a stream.
282foldlS :: IsStream t => (t m b -> a -> t m b) -> t m b -> t m a -> t m b
286 (\xs x -> IsStream.toStream $ f (IsStream.fromStream xs) x)
287 (IsStream.toStream z)
290-- | Lazy left fold to a transformer monad.
292-- For example, to reverse a stream:
294-- > S.toList $ S.foldlT (flip S.cons) S.nil $ (S.fromList [1..5] :: SerialT IO Int)
297foldlT :: (Monad m, IsStream t, Monad (s m), MonadTrans s)
298 => (s m b -> a -> s m b) -> s m b -> t m a -> s m b
299foldlT f z s = S.foldlT f z (toStreamS s)
301-- | Strict left fold with an extraction function. Like the standard strict
302-- left fold, but applies a user supplied extraction function (the third
303-- argument) to the folded value at the end. This is designed to work with the
304-- @foldl@ library. The suffix @x@ is a mnemonic for extraction.
307{-# DEPRECATED foldx "Please use foldl' followed by fmap instead." #-}
309foldx :: Monad m => (x -> a -> x) -> x -> (x -> b) -> SerialT m a -> m b
310foldx = IsStream.foldlx'
312-- | Left associative/strict push fold. @foldl' reduce initial stream@ invokes
313-- @reduce@ with the accumulator and the next input in the input stream, using
314-- @initial@ as the initial value of the current value of the accumulator. When
315-- the input is exhausted the current value of the accumulator is returned.
316-- Make sure to use a strict data structure for accumulator to not build
317-- unnecessary lazy expressions unless that's what you want. See the previous
318-- section for more details.
322foldl' :: Monad m => (b -> a -> b) -> b -> SerialT m a -> m b
323foldl' = IsStream.foldl'
325-- | Strict left fold, for non-empty streams, using first element as the
326-- starting value. Returns 'Nothing' if the stream is empty.
329{-# INLINE foldl1' #-}
330foldl1' :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
334 Nothing -> return Nothing
336 res <- foldl' step h t
339-- | Like 'foldx', but with a monadic step function.
342{-# DEPRECATED foldxM "Please use foldlM' followed by fmap instead." #-}
344foldxM :: Monad m => (x -> a -> m x) -> m x -> (x -> m b) -> SerialT m a -> m b
345foldxM = IsStream.foldlMx'
347-- | Like 'foldl'' but with a monadic step function.
351-- /Since: 0.8.0 (signature change)/
352{-# INLINE foldlM' #-}
353foldlM' :: Monad m => (b -> a -> m b) -> m b -> SerialT m a -> m b
354foldlM' step begin m = S.foldlM' step begin $ toStreamS m
356------------------------------------------------------------------------------
358------------------------------------------------------------------------------
361-- | Drain a stream to a 'Sink'.
362{-# INLINE runSink #-}
363runSink :: Monad m => Sink m a -> SerialT m a -> m ()
364runSink = fold . toFold
367------------------------------------------------------------------------------
369------------------------------------------------------------------------------
371-- | Parse a stream using the supplied ParserD 'PRD.Parser'.
375{-# INLINE_NORMAL parseD #-}
376parseD :: MonadThrow m => PRD.Parser m a b -> SerialT m a -> m b
377parseD p = D.parse p . toStreamD
379-- | Parse a stream using the supplied ParserK 'PRK.Parser'.
383parseK :: MonadThrow m => PRK.Parser m a b -> SerialT m a -> m b
386-- | Parse a stream using the supplied 'Parser'.
388-- Unlike folds, parsers may not always result in a valid output, they may
389-- result in an error. For example:
391-- >>> Stream.parse (Parser.takeEQ 1 Fold.drain) Stream.nil
392-- *** Exception: ParseError "takeEQ: Expecting exactly 1 elements, input terminated on 0"
397-- fold f = Stream.parse (Parser.fromFold f)
400-- @parse p@ is not the same as @head . parseMany p@ on an empty stream.
404{-# INLINE [3] parse #-}
405parse :: MonadThrow m => Parser m a b -> SerialT m a -> m b
406parse = parseD . PRD.fromParserK
408{-# INLINE_NORMAL parseD_ #-}
409parseD_ :: MonadThrow m => PRD.Parser m a b -> SerialT m a -> m (b, SerialT m a)
410parseD_ parser strm = do
411 (b, strmD) <- D.parse_ parser (toStreamD strm)
412 return $! (b, fromStreamD strmD)
414-- | Parse a stream using the supplied 'Parser'.
418{-# INLINE [3] parse_ #-}
419parse_ :: MonadThrow m => Parser m a b -> SerialT m a -> m (b, SerialT m a)
420parse_ = parseD_ . PRD.fromParserK
422------------------------------------------------------------------------------
423-- Specific Fold Functions
424------------------------------------------------------------------------------
426-- XXX this can utilize parallel mapping if we implement it as drain . mapM
428-- > mapM_ = Stream.drain . Stream.mapM
430-- Apply a monadic action to each element of the stream and discard the output
431-- of the action. This is not really a pure transformation operation but a
432-- transformation followed by fold.
436mapM_ :: Monad m => (a -> m b) -> SerialT m a -> m ()
437mapM_ f m = S.mapM_ f $ toStreamS m
440-- > drain = mapM_ (\_ -> return ())
441-- > drain = Stream.fold Fold.drain
443-- Run a stream, discarding the results. By default it interprets the stream
444-- as 'SerialT', to run other types of streams use the type adapting
445-- combinators for example @Stream.drain . 'fromAsync'@.
449drain :: Monad m => SerialT m a -> m ()
450drain = IsStream.drain
453-- > drainN n = Stream.drain . Stream.take n
454-- > drainN n = Stream.fold (Fold.take n Fold.drain)
456-- Run maximum up to @n@ iterations of a stream.
460drainN :: Monad m => Int -> SerialT m a -> m ()
461drainN n = drain . take n
464-- > runN n = runStream . take n
466-- Run maximum up to @n@ iterations of a stream.
469{-# DEPRECATED runN "Please use \"drainN\" instead" #-}
471runN :: Monad m => Int -> SerialT m a -> m ()
475-- > drainWhile p = Stream.drain . Stream.takeWhile p
477-- Run a stream as long as the predicate holds true.
480{-# INLINE drainWhile #-}
481drainWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
482drainWhile p = drain . takeWhile p
485-- > runWhile p = runStream . takeWhile p
487-- Run a stream as long as the predicate holds true.
490{-# DEPRECATED runWhile "Please use \"drainWhile\" instead" #-}
491{-# INLINE runWhile #-}
492runWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
495-- | Run a stream, discarding the results. By default it interprets the stream
496-- as 'SerialT', to run other types of streams use the type adapting
497-- combinators for example @runStream . 'fromAsync'@.
500{-# DEPRECATED runStream "Please use \"drain\" instead" #-}
501{-# INLINE runStream #-}
502runStream :: Monad m => SerialT m a -> m ()
505-- | Determine whether the stream is empty.
507-- > null = Stream.fold Fold.null
511null :: Monad m => SerialT m a -> m Bool
512null = S.null . toStreamS
514-- | Extract the first element of the stream, if any.
517-- > head = Stream.fold Fold.head
521head :: Monad m => SerialT m a -> m (Maybe a)
522head = S.head . toStreamS
524-- | Extract the first element of the stream, if any, otherwise use the
525-- supplied default value. It can help avoid one branch in high performance
529{-# INLINE headElse #-}
530headElse :: Monad m => a -> SerialT m a -> m a
531headElse x = D.headElse x . toStreamD
534-- > tail = fmap (fmap snd) . Stream.uncons
536-- Extract all but the first element of the stream, if any.
540tail :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
541tail (SerialT m) = fmap (fmap IsStream.fromStream) $ K.tail m
543-- | Extract all but the last element of the stream, if any.
547init :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
548init (SerialT m) = fmap (fmap IsStream.fromStream) $ K.init m
550-- | Extract the last element of the stream, if any.
552-- > last xs = xs !! (Stream.length xs - 1)
553-- > last = Stream.fold Fold.last
557last :: Monad m => SerialT m a -> m (Maybe a)
558last m = S.last $ toStreamS m
560-- | Determine whether an element is present in the stream.
562-- > elem = Stream.fold Fold.elem
566elem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
567elem e m = S.elem e (toStreamS m)
569-- | Determine whether an element is not present in the stream.
571-- > notElem = Stream.fold Fold.length
574{-# INLINE notElem #-}
575notElem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
576notElem e m = S.notElem e (toStreamS m)
578-- | Determine the length of the stream.
582length :: Monad m => SerialT m a -> m Int
583length = foldl' (\n _ -> n + 1) 0
585-- | Determine whether all elements of a stream satisfy a predicate.
587-- > all = Stream.fold Fold.all
591all :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
592all p m = S.all p (toStreamS m)
594-- | Determine whether any of the elements of a stream satisfy a predicate.
596-- > any = Stream.fold Fold.any
600any :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
601any p m = S.any p (toStreamS m)
603-- | Determines if all elements of a boolean stream are True.
605-- > and = Stream.fold Fold.and
609and :: Monad m => SerialT m Bool -> m Bool
612-- | Determines whether at least one element of a boolean stream is True.
614-- > or = Stream.fold Fold.or
618or :: Monad m => SerialT m Bool -> m Bool
621-- | Determine the sum of all elements of a stream of numbers. Returns @0@ when
622-- the stream is empty. Note that this is not numerically stable for floating
625-- > sum = Stream.fold Fold.sum
629sum :: (Monad m, Num a) => SerialT m a -> m a
632-- | Determine the product of all elements of a stream of numbers. Returns @1@
633-- when the stream is empty.
635-- > product = Stream.fold Fold.product
638{-# INLINE product #-}
639product :: (Monad m, Num a) => SerialT m a -> m a
640product = foldl' (*) 1
642-- | Fold a stream of monoid elements by appending them.
644-- > mconcat = Stream.fold Fold.mconcat
647{-# INLINE mconcat #-}
648mconcat :: (Monad m, Monoid a) => SerialT m a -> m a
649mconcat = foldr mappend mempty
653-- minimum = 'minimumBy' compare
654 -- minimum = Stream.fold Fold.minimum
657-- Determine the minimum element in a stream.
660{-# INLINE minimum #-}
661minimum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
662minimum m = S.minimum (toStreamS m)
664-- | Determine the minimum element in a stream using the supplied comparison
667-- > minimumBy = Stream.fold Fold.minimumBy
670{-# INLINE minimumBy #-}
671minimumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
672minimumBy cmp m = S.minimumBy cmp (toStreamS m)
676-- maximum = 'maximumBy' compare
677-- maximum = Stream.fold Fold.maximum
680-- Determine the maximum element in a stream.
683{-# INLINE maximum #-}
684maximum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
685maximum m = S.maximum (toStreamS m)
687-- | Determine the maximum element in a stream using the supplied comparison
690-- > maximumBy = Stream.fold Fold.maximumBy
693{-# INLINE maximumBy #-}
694maximumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
695maximumBy cmp m = S.maximumBy cmp (toStreamS m)
697-- | Ensures that all the elements of the stream are identical and then returns
698-- that unique element.
702the :: (Eq a, Monad m) => SerialT m a -> m (Maybe a)
703the m = S.the (toStreamS m)
705------------------------------------------------------------------------------
707------------------------------------------------------------------------------
709-- | Lookup the element at the given index.
713(!!) :: Monad m => SerialT m a -> Int -> m (Maybe a)
714m !! i = toStreamS m S.!! i
716-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
717-- first pair where the key equals the given value @a@.
719-- > lookup = snd <$> Stream.find ((==) . fst)
720-- > lookup = Stream.fold Fold.lookup
724lookup :: (Monad m, Eq a) => a -> SerialT m (a, b) -> m (Maybe b)
725lookup a m = S.lookup a (toStreamS m)
727-- | Like 'findM' but with a non-monadic predicate.
729-- > find p = findM (return . p)
730-- > find = Stream.fold Fold.find
734find :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe a)
735find p m = S.find p (toStreamS m)
737-- | Returns the first element that satisfies the given predicate.
739-- > findM = Stream.fold Fold.findM
743findM :: Monad m => (a -> m Bool) -> SerialT m a -> m (Maybe a)
744findM p m = S.findM p (toStreamS m)
746-- | Returns the first index that satisfies the given predicate.
748-- > findIndex = Stream.fold Fold.findIndex
751{-# INLINE findIndex #-}
752findIndex :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe Int)
753findIndex p = head . findIndices p
755-- | Returns the first index where a given value is found in the stream.
757-- > elemIndex a = Stream.findIndex (== a)
760{-# INLINE elemIndex #-}
761elemIndex :: (Monad m, Eq a) => a -> SerialT m a -> m (Maybe Int)
762elemIndex a = findIndex (== a)
764------------------------------------------------------------------------------
766------------------------------------------------------------------------------
770-- toList = Stream.foldr (:) []
773-- Convert a stream into a list in the underlying monad. The list can be
774-- consumed lazily in a lazy monad (e.g. 'Identity'). In a strict monad (e.g.
775-- IO) the whole list is generated and buffered before it can be consumed.
777-- /Warning!/ working on large lists accumulated as buffers in memory could be
778-- very inefficient, consider using "Streamly.Array" instead.
782toList :: Monad m => SerialT m a -> m [a]
783toList = IsStream.toList
787-- toListRev = Stream.foldl' (flip (:)) []
790-- Convert a stream into a list in reverse order in the underlying monad.
792-- /Warning!/ working on large lists accumulated as buffers in memory could be
793-- very inefficient, consider using "Streamly.Array" instead.
796{-# INLINE toListRev #-}
797toListRev :: Monad m => SerialT m a -> m [a]
798toListRev = D.toListRev . toStreamD
802-- toHandle h = S.mapM_ $ hPutStrLn h
805-- Write a stream of Strings to an IO Handle.
808{-# DEPRECATED toHandle
809 "Please use Streamly.FileSystem.Handle module (see the changelog)" #-}
810toHandle :: MonadIO m => IO.Handle -> SerialT m String -> m ()
815 single a = liftIO (IO.hPutStrLn h a)
816 yieldk a r = liftIO (IO.hPutStrLn h a) >> go r
817 in IsStream.foldStream defState yieldk single stop m1
819-- | Convert a stream to a pure stream.
822-- toStream = Stream.foldr Stream.cons Stream.nil
827{-# INLINE toStream #-}
828toStream :: Monad m => SerialT m a -> m (SerialT n a)
829toStream = foldr IsStream.cons IsStream.nil
831-- | Convert a stream to a pure stream in reverse order.
834-- toStreamRev = Stream.foldl' (flip Stream.cons) Stream.nil
839{-# INLINE toStreamRev #-}
840toStreamRev :: Monad m => SerialT m a -> m (SerialT n a)
841toStreamRev = foldl' (flip IsStream.cons) IsStream.nil
843------------------------------------------------------------------------------
844-- Concurrent Application
845------------------------------------------------------------------------------
847-- | Parallel fold application operator; applies a fold function @t m a -> m b@
848-- to a stream @t m a@ concurrently; The the input stream is evaluated
849-- asynchronously in an independent thread yielding elements to a buffer and
850-- the folding action runs in another thread consuming the input from the
853-- If you read the signature as @(t m a -> m b) -> (t m a -> m b)@ you can look
854-- at it as a transformation that converts a fold function to a buffered
855-- concurrent fold function.
857-- The @.@ at the end of the operator is a mnemonic for termination of the
860-- In the example below, each stage introduces a delay of 1 sec but output is
861-- printed every second because both stages are concurrent.
863-- >>> import Control.Concurrent (threadDelay)
864-- >>> import Streamly.Prelude ((|$.))
866-- Stream.foldlM' (\_ a -> threadDelay 1000000 >> print a) (return ())
867-- |$. Stream.replicateM 3 (threadDelay 1000000 >> return 1)
875-- /Since: 0.3.0 ("Streamly")/
879(|$.) :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
880-- (|$.) f = f . Async.mkAsync
881(|$.) f = f . mkParallel
889{-# INLINE foldAsync #-}
890foldAsync :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
893-- | Same as '|$.' but with arguments reversed.
895-- > (|&.) = flip (|$.)
899-- /Since: 0.3.0 ("Streamly")/
903(|&.) :: (IsStream t, MonadAsync m) => t m a -> (t m a -> m b) -> m b
908------------------------------------------------------------------------------
910------------------------------------------------------------------------------
912-- | Returns 'True' if the first stream is the same as or a prefix of the
913-- second. A stream is a prefix of itself.
915-- >>> Stream.isPrefixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
919{-# INLINE isPrefixOf #-}
920isPrefixOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
921isPrefixOf m1 m2 = D.isPrefixOf (toStreamD m1) (toStreamD m2)
923-- | Returns 'True' if the first stream is an infix of the second. A stream is
924-- considered an infix of itself.
926-- > Stream.isInfixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
929-- Space: @O(n)@ worst case where @n@ is the length of the infix.
933-- /Requires 'Storable' constraint/
935{-# INLINE isInfixOf #-}
936isInfixOf :: (MonadIO m, Eq a, Enum a, Storable a)
937 => SerialT m a -> SerialT m a -> m Bool
938isInfixOf infx stream = do
939 arr <- fold A.write infx
940 -- XXX can use breakOnSeq instead (when available)
941 r <- null $ drop 1 $ splitOnSeq arr FL.drain stream
944-- Note: isPrefixOf uses the prefix stream only once. In contrast, isSuffixOf
945-- may use the suffix stream many times. To run in optimal memory we do not
946-- want to buffer the suffix stream in memory therefore we need an ability to
947-- clone (or consume it multiple times) the suffix stream without any side
948-- effects so that multiple potential suffix matches can proceed in parallel
949-- without buffering the suffix stream. For example, we may create the suffix
950-- stream from a file handle, however, if we evaluate the stream multiple
951-- times, once for each match, we will need a different file handle each time
952-- which may exhaust the file descriptors. Instead, we want to share the same
953-- underlying file descriptor, use pread on it to generate the stream and clone
954-- the stream for each match. Therefore the suffix stream should be built in
955-- such a way that it can be consumed multiple times without any problems.
957-- XXX Can be implemented with better space/time complexity.
958-- Space: @O(n)@ worst case where @n@ is the length of the suffix.
960-- | Returns 'True' if the first stream is a suffix of the second. A stream is
961-- considered a suffix of itself.
963-- >>> Stream.isSuffixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
966-- Space: @O(n)@, buffers entire input stream and the suffix.
970-- /Suboptimal/ - Help wanted.
972{-# INLINE isSuffixOf #-}
973isSuffixOf :: (Monad m, Eq a) => SerialT m a -> SerialT m a -> m Bool
974isSuffixOf suffix stream = reverse suffix `isPrefixOf` reverse stream
976-- | Returns 'True' if all the elements of the first stream occur, in order, in
977-- the second stream. The elements do not have to occur consecutively. A stream
978-- is a subsequence of itself.
980-- >>> Stream.isSubsequenceOf (Stream.fromList "hlo") (Stream.fromList "hello" :: SerialT IO Char)
984{-# INLINE isSubsequenceOf #-}
985isSubsequenceOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
986isSubsequenceOf m1 m2 = D.isSubsequenceOf (toStreamD m1) (toStreamD m2)
988-- Note: If we want to return a Maybe value to know whether the
989-- suffix/infix was present or not along with the stripped stream then
990-- we need to buffer the whole input stream.
992-- | @stripPrefix prefix stream@ strips @prefix@ from @stream@ if it is a
993-- prefix of stream. Returns 'Nothing' if the stream does not start with the
994-- given prefix, stripped stream otherwise. Returns @Just nil@ when the prefix
995-- is the same as the stream.
997-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropPrefix".
1002{-# INLINE stripPrefix #-}
1004 :: (Eq a, IsStream t, Monad m)
1005 => t m a -> t m a -> m (Maybe (t m a))
1006stripPrefix m1 m2 = fmap fromStreamD <$>
1007 D.stripPrefix (toStreamD m1) (toStreamD m2)
1009-- | Drops the given suffix from a stream. Returns 'Nothing' if the stream does
1010-- not end with the given suffix. Returns @Just nil@ when the suffix is the
1011-- same as the stream.
1013-- It may be more efficient to convert the stream to an Array and use
1014-- stripSuffix on that especially if the elements have a Storable or Prim
1017-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropSuffix".
1019-- Space: @O(n)@, buffers the entire input stream as well as the suffix
1022{-# INLINE stripSuffix #-}
1025 => SerialT m a -> SerialT m a -> m (Maybe (SerialT m a))
1026stripSuffix m1 m2 = fmap reverse <$> stripPrefix (reverse m1) (reverse m2)
1028------------------------------------------------------------------------------
1030------------------------------------------------------------------------------
1032-- | Compare two streams for equality using an equality function.
1035{-# INLINABLE eqBy #-}
1036eqBy :: (IsStream t, Monad m) => (a -> b -> Bool) -> t m a -> t m b -> m Bool
1039-- | Compare two streams lexicographically using a comparison function.
1042{-# INLINABLE cmpBy #-}
1044 :: (IsStream t, Monad m)
1045 => (a -> b -> Ordering) -> t m a -> t m b -> m Ordering
1046cmpBy = IsStream.cmpBy
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list