1{-# OPTIONS_GHC -Wno-deprecations #-}
4-- Module : Streamly.Internal.Data.Stream.IsStream.Eliminate
5-- Copyright : (c) 2017 Composewell Technologies
6-- License : BSD-3-Clause
7-- Maintainer : streamly@composewell.com
8-- Stability : experimental
11-- This module contains functions ending in the shape:
17-- We call them stream folding functions, they reduce a stream @t m a@ to a
18-- monadic value @m b@.
20module Streamly.Internal.Data.Stream.IsStream.Eliminate {-# DEPRECATED "Please use \"Streamly.Data.Stream.*\" instead." #-}
26 -- See "Streamly.Internal.Data.Fold".
29 -- * Running a 'Parser'
30 -- "Streamly.Internal.Data.Parser".
35 -- * Stream Deconstruction
36 -- | foldr and foldl do not provide the remaining stream. 'uncons' is more
37 -- general, as it can be used to implement those as well. It allows to use
38 -- the stream one element at a time, and we have the remaining stream all
47 -- Lazy left folds are useful only for reversing the stream
55 -- * Specific Fold Functions
56 -- | Folds as functions of the shape @t m a -> m b@.
58 -- These functions are good to run individually but they do not compose
59 -- well. Prefer writing folds as the 'Fold' data type. Use folds from
60 -- "Streamly.Internal.Data.Fold" instead of using the functions in this
63 -- This section can possibly be removed in future. Are these better in
64 -- some case compared to 'Fold'? When the input stream is in CPS style
65 -- (StreamK) we may want to rewrite the function call to CPS implementation
66 -- of the fold through these definitions. Will that be more efficient for
71 -- -- ** To Summary (Full Folds)
80 -- -- ** To Summary (Maybe) (Full Folds)
89 -- -- ** To Elements (Partial Folds)
93 -- -- | Folds that extract selected elements of a stream or their properties.
105 -- -- ** To Boolean (Partial Folds)
121 -- * Concurrent Folds
126 -- * Multi-Stream folds
131 -- finding subsequences
137 -- trimming sequences
155import Control.Monad.IO.Class (MonadIO(..))
156import Control.Monad.Trans.Class (MonadTrans(..))
157import Foreign.Storable (Storable)
158import Streamly.Internal.Control.Concurrent (MonadAsync)
159import Streamly.Internal.Data.Parser (Parser (..))
160import Streamly.Internal.Data.SVar (defState)
161import Streamly.Internal.Data.Stream.IsStream.Common
162 ( fold, drop, findIndices, reverse, splitOnSeq
163 , take , takeWhile, mkParallel)
164import Streamly.Internal.Data.Stream.IsStream.Type
165 (IsStream, fromStreamD, toStreamD)
166import Streamly.Internal.Data.Stream.Serial (SerialT)
167import Streamly.Internal.Data.Unboxed (Unbox)
169import qualified Streamly.Internal.Data.Array as A
170import qualified Streamly.Internal.Data.Stream.Serial as Stream
171import qualified Streamly.Internal.Data.Fold as FL
172import qualified Streamly.Internal.Data.Parser.ParserD as PRD
173-- import qualified Streamly.Internal.Data.Parser.ParserK.Type as PRK
174import qualified Streamly.Internal.Data.Stream.IsStream.Type as IsStream
175import qualified Streamly.Internal.Data.Stream.StreamD as D
176 (foldr1, foldlT, foldlM', mapM_, null, head, headElse, last, elem
177 , notElem, all, any, minimum, minimumBy, maximum, maximumBy, the, lookup
178 , find, findM, toListRev, isPrefixOf, isSubsequenceOf, stripPrefix, (!!)
179 , fromStreamK, foldrM, parseD)
180import qualified Streamly.Internal.Data.Stream.StreamK.Type as K
181 (uncons, foldlS, tail, init)
182import qualified System.IO as IO
185 ( drop, take, takeWhile, foldr , foldl, mapM_, sequence, all, any, sum
186 , product, elem, notElem, maximum, minimum, head, last, tail, length
187 , null , reverse, init, and, or, lookup, foldr1, (!!) , splitAt, break
192-- >>> :set -fno-warn-deprecations
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.Internal.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 can be used to do pretty much anything in an imperative manner, as it
208-- just breaks down the stream into individual elements and we can loop over
209-- them as we deem fit. For example, this can be used to convert a streamly
210-- stream into other stream types.
212-- All the folds in this module can be expressed in terms of 'uncons', however,
213-- this is generally less efficient than specific folds because it takes apart
214-- the stream one element at a time, therefore, does not take adavantage of
219uncons :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (a, t m a))
220uncons = fmap (fmap (fmap IsStream.fromStream)) . K.uncons . Stream.toStreamK
222------------------------------------------------------------------------------
224------------------------------------------------------------------------------
226-- | Right associative/lazy pull fold. @foldrM build final stream@ constructs
227-- an output structure using the step function @build@. @build@ is invoked with
228-- the next input element and the remaining (lazy) tail of the output
229-- structure. It builds a lazy output expression using the two. When the "tail
230-- structure" in the output expression is evaluated it calls @build@ again thus
231-- lazily consuming the input @stream@ until either the output expression built
232-- by @build@ is free of the "tail" or the input is exhausted in which case
233-- @final@ is used as the terminating case for the output structure. For more
234-- details see the description in the previous section.
236-- Example, determine if any element is 'odd' in a stream:
238-- >>> Stream.foldrM (\x xs -> if odd x then return True else xs) (return False) $ Stream.fromList (2:4:5:undefined)
241-- /Since: 0.7.0 (signature changed)/
243-- /Since: 0.2.0 (signature changed)/
247foldrM :: Monad m => (a -> m b -> m b) -> m b -> SerialT m a -> m b
248foldrM step acc (Stream.SerialT m) = D.foldrM step acc $ D.fromStreamK m
250-- | Right fold, lazy for lazy monads and pure streams, and strict for strict
253-- Please avoid using this routine in strict monads like IO unless you need a
254-- strict right fold. This is provided only for use in lazy monads (e.g.
255-- Identity) or pure streams. Note that with this signature it is not possible
256-- to implement a lazy foldr when the monad @m@ is strict. In that case it
257-- would be strict in its accumulator and therefore would necessarily consume
262foldr :: Monad m => (a -> b -> b) -> b -> SerialT m a -> m b
263foldr f z = foldrM (\a b -> f a <$> b) (return z)
265-- XXX This seems to be of limited use as it cannot be used to construct
266-- recursive structures and for reduction foldl1' is better.
268-- | Lazy right fold for non-empty streams, using first element as the starting
269-- value. Returns 'Nothing' if the stream is empty.
273{-# DEPRECATED foldr1 "Use foldrM instead." #-}
274foldr1 :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
275foldr1 f m = D.foldr1 f (toStreamD m)
277------------------------------------------------------------------------------
279------------------------------------------------------------------------------
281-- | Lazy left fold to a stream.
283foldlS :: IsStream t => (t m b -> a -> t m b) -> t m b -> t m a -> t m b
287 (\xs x -> IsStream.toStream $ f (IsStream.fromStream xs) x)
288 (IsStream.toStream z)
291-- | Lazy left fold to a transformer monad.
293-- For example, to reverse a stream:
295-- > D.toList $ D.foldlT (flip D.cons) D.nil $ (D.fromList [1..5] :: SerialT IO Int)
298foldlT :: (Monad m, IsStream t, Monad (s m), MonadTrans s)
299 => (s m b -> a -> s m b) -> s m b -> t m a -> s m b
300foldlT f z s = D.foldlT f z (toStreamD s)
302-- | Strict left fold with an extraction function. Like the standard strict
303-- left fold, but applies a user supplied extraction function (the third
304-- argument) to the folded value at the end. This is designed to work with the
305-- @foldl@ library. The suffix @x@ is a mnemonic for extraction.
308{-# DEPRECATED foldx "Please use foldl' followed by fmap instead." #-}
310foldx :: Monad m => (x -> a -> x) -> x -> (x -> b) -> SerialT m a -> m b
311foldx = IsStream.foldlx'
313-- | Left associative/strict push fold. @foldl' reduce initial stream@ invokes
314-- @reduce@ with the accumulator and the next input in the input stream, using
315-- @initial@ as the initial value of the current value of the accumulator. When
316-- the input is exhausted the current value of the accumulator is returned.
317-- Make sure to use a strict data structure for accumulator to not build
318-- unnecessary lazy expressions unless that's what you want. See the previous
319-- section for more details.
323foldl' :: Monad m => (b -> a -> b) -> b -> SerialT m a -> m b
324foldl' = IsStream.foldl'
326-- | Strict left fold, for non-empty streams, using first element as the
327-- starting value. Returns 'Nothing' if the stream is empty.
330{-# INLINE foldl1' #-}
331foldl1' :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
335 Nothing -> return Nothing
337 res <- foldl' step h t
340-- | Like 'foldx', but with a monadic step function.
343{-# DEPRECATED foldxM "Please use foldlM' followed by fmap instead." #-}
345foldxM :: Monad m => (x -> a -> m x) -> m x -> (x -> m b) -> SerialT m a -> m b
346foldxM = IsStream.foldlMx'
348-- | Like 'foldl'' but with a monadic step function.
352-- /Since: 0.8.0 (signature change)/
353{-# INLINE foldlM' #-}
354foldlM' :: Monad m => (b -> a -> m b) -> m b -> SerialT m a -> m b
355foldlM' step begin = D.foldlM' step begin . IsStream.toStreamD
357------------------------------------------------------------------------------
359------------------------------------------------------------------------------
362-- | Drain a stream to a 'Sink'.
363{-# INLINE runSink #-}
364runSink :: Monad m => Sink m a -> SerialT m a -> m ()
365runSink = fold . toFold
368------------------------------------------------------------------------------
370------------------------------------------------------------------------------
372-- | Parse a stream using the supplied ParserD 'PRD.Parser'.
376{-# INLINE_NORMAL parseD #-}
377parseD :: Monad m => PRD.Parser a m b -> SerialT m a -> m (Either PRD.ParseError b)
378parseD p = D.parseD p . toStreamD
381-- | Parse a stream using the supplied ParserK 'PRK.Parser'.
385parseK :: Monad m => PRK.Parser a m b -> SerialT m a -> m (Either PRD.ParseError b)
386parseK p = parse (PRK.toParser p)
389-- | Parse a stream using the supplied 'Parser'.
391-- Unlike folds, parsers may not always result in a valid output, they may
392-- result in an error. For example:
394-- >>> Stream.parse (Parser.takeEQ 1 Fold.drain) Stream.nil
395-- Left (ParseError "takeEQ: Expecting exactly 1 elements, input terminated on 0")
400-- fold f = Stream.parse (Parser.fromFold f)
403-- @parse p@ is not the same as @head . parseMany p@ on an empty stream.
407{-# INLINE [3] parse #-}
408parse :: Monad m => Parser a m b -> SerialT m a -> m (Either PRD.ParseError b)
411------------------------------------------------------------------------------
412-- Specific Fold Functions
413------------------------------------------------------------------------------
415-- XXX this can utilize parallel mapping if we implement it as drain . mapM
417-- > mapM_ = Stream.drain . Stream.mapM
419-- Apply a monadic action to each element of the stream and discard the output
420-- of the action. This is not really a pure transformation operation but a
421-- transformation followed by fold.
425mapM_ :: Monad m => (a -> m b) -> SerialT m a -> m ()
426mapM_ f = D.mapM_ f . IsStream.toStreamD
429-- > drain = mapM_ (\_ -> return ())
430-- > drain = Stream.fold Fold.drain
432-- Run a stream, discarding the results. By default it interprets the stream
433-- as 'SerialT', to run other types of streams use the type adapting
434-- combinators for example @Stream.drain . 'fromAsync'@.
438drain :: Monad m => SerialT m a -> m ()
439drain = IsStream.drain
442-- > drainN n = Stream.drain . Stream.take n
443-- > drainN n = Stream.fold (Fold.take n Fold.drain)
445-- Run maximum up to @n@ iterations of a stream.
449drainN :: Monad m => Int -> SerialT m a -> m ()
450drainN n = drain . take n
453-- > runN n = runStream . take n
455-- Run maximum up to @n@ iterations of a stream.
458{-# DEPRECATED runN "Please use \"drainN\" instead" #-}
460runN :: Monad m => Int -> SerialT m a -> m ()
464-- > drainWhile p = Stream.drain . Stream.takeWhile p
466-- Run a stream as long as the predicate holds true.
469{-# INLINE drainWhile #-}
470drainWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
471drainWhile p = drain . takeWhile p
474-- > runWhile p = runStream . takeWhile p
476-- Run a stream as long as the predicate holds true.
479{-# DEPRECATED runWhile "Please use \"drainWhile\" instead" #-}
480{-# INLINE runWhile #-}
481runWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
484-- | Run a stream, discarding the results. By default it interprets the stream
485-- as 'SerialT', to run other types of streams use the type adapting
486-- combinators for example @runStream . 'fromAsync'@.
489{-# DEPRECATED runStream "Please use \"drain\" instead" #-}
490{-# INLINE runStream #-}
491runStream :: Monad m => SerialT m a -> m ()
494-- | Determine whether the stream is empty.
496-- > null = Stream.fold Fold.null
500null :: Monad m => SerialT m a -> m Bool
501null = D.null . toStreamD
503-- | Extract the first element of the stream, if any.
506-- > head = Stream.fold Fold.one
510head :: Monad m => SerialT m a -> m (Maybe a)
511head = D.head . toStreamD
513-- | Extract the first element of the stream, if any, otherwise use the
514-- supplied default value. It can help avoid one branch in high performance
518{-# INLINE headElse #-}
519headElse :: Monad m => a -> SerialT m a -> m a
520headElse x = D.headElse x . toStreamD
523-- > tail = fmap (fmap snd) . Stream.uncons
525-- Extract all but the first element of the stream, if any.
529tail :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
530tail m = fmap (fmap IsStream.fromStream) $ K.tail $ Stream.toStreamK m
532-- | Extract all but the last element of the stream, if any.
536init :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
537init m = fmap (fmap IsStream.fromStream) $ K.init $ Stream.toStreamK m
539-- | Extract the last element of the stream, if any.
541-- > last xs = xs !! (Stream.length xs - 1)
542-- > last = Stream.fold Fold.last
546last :: Monad m => SerialT m a -> m (Maybe a)
547last m = D.last $ toStreamD m
549-- | Determine whether an element is present in the stream.
551-- > elem = Stream.fold Fold.elem
555elem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
556elem e m = D.elem e (toStreamD m)
558-- | Determine whether an element is not present in the stream.
560-- > notElem = Stream.fold Fold.length
563{-# INLINE notElem #-}
564notElem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
565notElem e m = D.notElem e (toStreamD m)
567-- | Determine the length of the stream.
571length :: Monad m => SerialT m a -> m Int
572length = foldl' (\n _ -> n + 1) 0
574-- | Determine whether all elements of a stream satisfy a predicate.
576-- > all = Stream.fold Fold.all
580all :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
581all p m = D.all p (toStreamD m)
583-- | Determine whether any of the elements of a stream satisfy a predicate.
585-- > any = Stream.fold Fold.any
589any :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
590any p m = D.any p (toStreamD m)
592-- | Determines if all elements of a boolean stream are True.
594-- > and = Stream.fold Fold.and
598and :: Monad m => SerialT m Bool -> m Bool
601-- | Determines whether at least one element of a boolean stream is True.
603-- > or = Stream.fold Fold.or
607or :: Monad m => SerialT m Bool -> m Bool
610-- | Determine the sum of all elements of a stream of numbers. Returns @0@ when
611-- the stream is empty. Note that this is not numerically stable for floating
614-- > sum = Stream.fold Fold.sum
618sum :: (Monad m, Num a) => SerialT m a -> m a
621-- | Determine the product of all elements of a stream of numbers. Returns @1@
622-- when the stream is empty.
624-- > product = Stream.fold Fold.product
627{-# INLINE product #-}
628product :: (Monad m, Num a) => SerialT m a -> m a
629product = foldl' (*) 1
631-- | Fold a stream of monoid elements by appending them.
633-- > mconcat = Stream.fold Fold.mconcat
636{-# INLINE mconcat #-}
637mconcat :: (Monad m, Monoid a) => SerialT m a -> m a
638mconcat = foldr mappend mempty
642-- minimum = 'minimumBy' compare
643 -- minimum = Stream.fold Fold.minimum
646-- Determine the minimum element in a stream.
649{-# INLINE minimum #-}
650minimum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
651minimum m = D.minimum (toStreamD m)
653-- | Determine the minimum element in a stream using the supplied comparison
656-- > minimumBy = Stream.fold Fold.minimumBy
659{-# INLINE minimumBy #-}
660minimumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
661minimumBy cmp m = D.minimumBy cmp (toStreamD m)
665-- maximum = 'maximumBy' compare
666-- maximum = Stream.fold Fold.maximum
669-- Determine the maximum element in a stream.
672{-# INLINE maximum #-}
673maximum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
674maximum m = D.maximum (toStreamD m)
676-- | Determine the maximum element in a stream using the supplied comparison
679-- > maximumBy = Stream.fold Fold.maximumBy
682{-# INLINE maximumBy #-}
683maximumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
684maximumBy cmp m = D.maximumBy cmp (toStreamD m)
686-- | Ensures that all the elements of the stream are identical and then returns
687-- that unique element.
691the :: (Eq a, Monad m) => SerialT m a -> m (Maybe a)
692the m = D.the (toStreamD m)
694------------------------------------------------------------------------------
696------------------------------------------------------------------------------
698-- | Lookup the element at the given index.
702(!!) :: Monad m => SerialT m a -> Int -> m (Maybe a)
703m !! i = toStreamD m D.!! i
705-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
706-- first pair where the key equals the given value @a@.
708-- > lookup = snd <$> Stream.find ((==) . fst)
709-- > lookup = Stream.fold Fold.lookup
713lookup :: (Monad m, Eq a) => a -> SerialT m (a, b) -> m (Maybe b)
714lookup a m = D.lookup a (toStreamD m)
716-- | Like 'findM' but with a non-monadic predicate.
718-- > find p = findM (return . p)
719-- > find = Stream.fold Fold.find
723find :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe a)
724find p m = D.find p (toStreamD m)
726-- | Returns the first element that satisfies the given predicate.
728-- > findM = Stream.fold Fold.findM
732findM :: Monad m => (a -> m Bool) -> SerialT m a -> m (Maybe a)
733findM p m = D.findM p (toStreamD m)
735-- | Returns the first index that satisfies the given predicate.
737-- > findIndex = Stream.fold Fold.findIndex
740{-# INLINE findIndex #-}
741findIndex :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe Int)
742findIndex p = head . findIndices p
744-- | Returns the first index where a given value is found in the stream.
746-- > elemIndex a = Stream.findIndex (== a)
749{-# INLINE elemIndex #-}
750elemIndex :: (Monad m, Eq a) => a -> SerialT m a -> m (Maybe Int)
751elemIndex a = findIndex (== a)
753------------------------------------------------------------------------------
755------------------------------------------------------------------------------
759-- toList = Stream.foldr (:) []
762-- Convert a stream into a list in the underlying monad. The list can be
763-- consumed lazily in a lazy monad (e.g. 'Identity'). In a strict monad (e.g.
764-- IO) the whole list is generated and buffered before it can be consumed.
766-- /Warning!/ working on large lists accumulated as buffers in memory could be
767-- very inefficient, consider using "Streamly.Array" instead.
771toList :: Monad m => SerialT m a -> m [a]
772toList = IsStream.toList
776-- toListRev = Stream.foldl' (flip (:)) []
779-- Convert a stream into a list in reverse order in the underlying monad.
781-- /Warning!/ working on large lists accumulated as buffers in memory could be
782-- very inefficient, consider using "Streamly.Array" instead.
785{-# INLINE toListRev #-}
786toListRev :: Monad m => SerialT m a -> m [a]
787toListRev = D.toListRev . toStreamD
791-- toHandle h = D.mapM_ $ hPutStrLn h
794-- Write a stream of Strings to an IO Handle.
797{-# DEPRECATED toHandle
798 "Please use Streamly.FileSystem.Handle module (see the changelog)" #-}
799toHandle :: MonadIO m => IO.Handle -> SerialT m String -> m ()
804 single a = liftIO (IO.hPutStrLn h a)
805 yieldk a r = liftIO (IO.hPutStrLn h a) >> go r
806 in IsStream.foldStream defState yieldk single stop m1
808-- | Convert a stream to a pure stream.
811-- toStream = Stream.foldr Stream.cons Stream.nil
816{-# INLINE toStream #-}
817toStream :: Monad m => SerialT m a -> m (SerialT n a)
818toStream = foldr IsStream.cons IsStream.nil
820-- | Convert a stream to a pure stream in reverse order.
823-- toStreamRev = Stream.foldl' (flip Stream.cons) Stream.nil
828{-# INLINE toStreamRev #-}
829toStreamRev :: Monad m => SerialT m a -> m (SerialT n a)
830toStreamRev = foldl' (flip IsStream.cons) IsStream.nil
832------------------------------------------------------------------------------
833-- Concurrent Application
834------------------------------------------------------------------------------
836-- | Parallel fold application operator; applies a fold function @t m a -> m b@
837-- to a stream @t m a@ concurrently; The the input stream is evaluated
838-- asynchronously in an independent thread yielding elements to a buffer and
839-- the folding action runs in another thread consuming the input from the
842-- If you read the signature as @(t m a -> m b) -> (t m a -> m b)@ you can look
843-- at it as a transformation that converts a fold function to a buffered
844-- concurrent fold function.
846-- The @.@ at the end of the operator is a mnemonic for termination of the
849-- In the example below, each stage introduces a delay of 1 sec but output is
850-- printed every second because both stages are concurrent.
852-- >>> import Control.Concurrent (threadDelay)
853-- >>> import Streamly.Prelude ((|$.))
855-- Stream.foldlM' (\_ a -> threadDelay 1000000 >> print a) (return ())
856-- |$. Stream.replicateM 3 (threadDelay 1000000 >> return 1)
864-- /Since: 0.3.0 ("Streamly")/
868(|$.) :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
869-- (|$.) f = f . Async.mkAsync
870(|$.) f = f . mkParallel
878{-# INLINE foldAsync #-}
879foldAsync :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
882-- | Same as '|$.' but with arguments reversed.
884-- > (|&.) = flip (|$.)
888-- /Since: 0.3.0 ("Streamly")/
892(|&.) :: (IsStream t, MonadAsync m) => t m a -> (t m a -> m b) -> m b
897------------------------------------------------------------------------------
899------------------------------------------------------------------------------
901-- | Returns 'True' if the first stream is the same as or a prefix of the
902-- second. A stream is a prefix of itself.
904-- >>> Stream.isPrefixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
908{-# INLINE isPrefixOf #-}
909isPrefixOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
910isPrefixOf m1 m2 = D.isPrefixOf (toStreamD m1) (toStreamD m2)
912-- | Returns 'True' if the first stream is an infix of the second. A stream is
913-- considered an infix of itself.
915-- > Stream.isInfixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
918-- Space: @O(n)@ worst case where @n@ is the length of the infix.
922-- /Requires 'Storable' constraint/
924{-# INLINE isInfixOf #-}
925isInfixOf :: (MonadIO m, Eq a, Enum a, Storable a, Unbox a)
926 => SerialT m a -> SerialT m a -> m Bool
927isInfixOf infx stream = do
928 arr <- fold A.write infx
929 -- XXX can use breakOnSeq instead (when available)
930 r <- null $ drop 1 $ splitOnSeq arr FL.drain stream
933-- Note: isPrefixOf uses the prefix stream only once. In contrast, isSuffixOf
934-- may use the suffix stream many times. To run in optimal memory we do not
935-- want to buffer the suffix stream in memory therefore we need an ability to
936-- clone (or consume it multiple times) the suffix stream without any side
937-- effects so that multiple potential suffix matches can proceed in parallel
938-- without buffering the suffix stream. For example, we may create the suffix
939-- stream from a file handle, however, if we evaluate the stream multiple
940-- times, once for each match, we will need a different file handle each time
941-- which may exhaust the file descriptors. Instead, we want to share the same
942-- underlying file descriptor, use pread on it to generate the stream and clone
943-- the stream for each match. Therefore the suffix stream should be built in
944-- such a way that it can be consumed multiple times without any problems.
946-- XXX Can be implemented with better space/time complexity.
947-- Space: @O(n)@ worst case where @n@ is the length of the suffix.
949-- | Returns 'True' if the first stream is a suffix of the second. A stream is
950-- considered a suffix of itself.
952-- >>> Stream.isSuffixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
955-- Space: @O(n)@, buffers entire input stream and the suffix.
959-- /Suboptimal/ - Help wanted.
961{-# INLINE isSuffixOf #-}
962isSuffixOf :: (Monad m, Eq a) => SerialT m a -> SerialT m a -> m Bool
963isSuffixOf suffix stream = reverse suffix `isPrefixOf` reverse stream
965-- | Returns 'True' if all the elements of the first stream occur, in order, in
966-- the second stream. The elements do not have to occur consecutively. A stream
967-- is a subsequence of itself.
969-- >>> Stream.isSubsequenceOf (Stream.fromList "hlo") (Stream.fromList "hello" :: SerialT IO Char)
973{-# INLINE isSubsequenceOf #-}
974isSubsequenceOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
975isSubsequenceOf m1 m2 = D.isSubsequenceOf (toStreamD m1) (toStreamD m2)
977-- Note: If we want to return a Maybe value to know whether the
978-- suffix/infix was present or not along with the stripped stream then
979-- we need to buffer the whole input stream.
981-- | @stripPrefix prefix stream@ strips @prefix@ from @stream@ if it is a
982-- prefix of stream. Returns 'Nothing' if the stream does not start with the
983-- given prefix, stripped stream otherwise. Returns @Just nil@ when the prefix
984-- is the same as the stream.
986-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropPrefix".
991{-# INLINE stripPrefix #-}
993 :: (Eq a, IsStream t, Monad m)
994 => t m a -> t m a -> m (Maybe (t m a))
995stripPrefix m1 m2 = fmap fromStreamD <$>
996 D.stripPrefix (toStreamD m1) (toStreamD m2)
998-- | Drops the given suffix from a stream. Returns 'Nothing' if the stream does
999-- not end with the given suffix. Returns @Just nil@ when the suffix is the
1000-- same as the stream.
1002-- It may be more efficient to convert the stream to an Array and use
1003-- stripSuffix on that especially if the elements have a Storable or Prim
1006-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropSuffix".
1008-- Space: @O(n)@, buffers the entire input stream as well as the suffix
1011{-# INLINE stripSuffix #-}
1014 => SerialT m a -> SerialT m a -> m (Maybe (SerialT m a))
1015stripSuffix m1 m2 = fmap reverse <$> stripPrefix (reverse m1) (reverse m2)
1017------------------------------------------------------------------------------
1019------------------------------------------------------------------------------
1021-- | Compare two streams for equality using an equality function.
1024{-# INLINABLE eqBy #-}
1025eqBy :: (IsStream t, Monad m) => (a -> b -> Bool) -> t m a -> t m b -> m Bool
1028-- | Compare two streams lexicographically using a comparison function.
1031{-# INLINABLE cmpBy #-}
1033 :: (IsStream t, Monad m)
1034 => (a -> b -> Ordering) -> t m a -> t m b -> m Ordering
1035cmpBy = 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