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".
28 -- * Running a 'Parser'
29 -- "Streamly.Internal.Data.Parser".
36 -- * Stream Deconstruction
37 -- | foldr and foldl do not provide the remaining stream. 'uncons' is more
38 -- general, as it can be used to implement those as well. It allows to use
39 -- the stream one element at a time, and we have the remaining stream all
52 -- * Specific Fold Functions
53 -- | Folds as functions of the shape @t m a -> m b@.
55 -- These functions are good to run individually but they do not compose
56 -- well. Prefer writing folds as the 'Fold' data type. Use folds from
57 -- "Streamly.Internal.Data.Fold" instead of using the functions in this
60 -- This section can possibly be removed in future. Are these better in
61 -- some case compared to 'Fold'? When the input stream is in CPS style
62 -- (StreamK) we may want to rewrite the function call to CPS implementation
63 -- of the fold through these definitions. Will that be more efficient for
68 -- -- ** To Summary (Full Folds)
77 -- -- ** To Summary (Maybe) (Full Folds)
86 -- -- ** To Elements (Partial Folds)
90 -- -- | Folds that extract selected elements of a stream or their properties.
102 -- -- ** To Boolean (Partial Folds)
118 -- * Concurrent Folds
123 -- * Multi-Stream folds
128 -- finding subsequences
134 -- trimming sequences
152import Control.Monad.Catch (MonadThrow)
153import Control.Monad.IO.Class (MonadIO(..))
154import Data.Functor.Identity (Identity (..))
155import Foreign.Storable (Storable)
156import Streamly.Internal.Data.Parser (Parser (..))
157import Streamly.Internal.Data.SVar (MonadAsync, defState)
158import Streamly.Internal.Data.Stream.IsStream.Common
159 ( fold, fold_, drop, findIndices, reverse, splitOnSeq, take
161import Streamly.Internal.Data.Stream.Prelude (toStreamS)
162import Streamly.Internal.Data.Stream.StreamD (fromStreamD, toStreamD)
163import Streamly.Internal.Data.Stream.StreamK (IsStream)
164import Streamly.Internal.Data.Stream.Serial (SerialT)
166import qualified Streamly.Internal.Data.Array.Foreign.Type as A
167import qualified Streamly.Internal.Data.Fold as FL
168import qualified Streamly.Internal.Data.Stream.Parallel as Par
169import qualified Streamly.Internal.Data.Stream.Prelude as P
170import qualified Streamly.Internal.Data.Stream.StreamD as D
171import qualified Streamly.Internal.Data.Stream.StreamK as K
172import qualified Streamly.Internal.Data.Parser.ParserD as PRD
173import qualified Streamly.Internal.Data.Parser.ParserK.Type as PRK
174import qualified System.IO as IO
175#ifdef USE_STREAMK_ONLY
176import qualified Streamly.Internal.Data.Stream.StreamK as S
178import qualified Streamly.Internal.Data.Stream.StreamD as S
182 ( drop, take, takeWhile, foldr , foldl, mapM_, sequence, all, any, sum
183 , product, elem, notElem, maximum, minimum, head, last, tail, length
184 , null , reverse, init, and, or, lookup, foldr1, (!!) , splitAt, break
189-- >>> import Streamly.Prelude (SerialT)
190-- >>> import qualified Streamly.Prelude as Stream
191-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream
192-- >>> import qualified Streamly.Internal.Data.Parser as Parser
193-- >>> import qualified Streamly.Data.Fold as Fold
195------------------------------------------------------------------------------
197------------------------------------------------------------------------------
199-- | Decompose a stream into its head and tail. If the stream is empty, returns
200-- 'Nothing'. If the stream is non-empty, returns @Just (a, ma)@, where @a@ is
201-- the head of the stream and @ma@ its tail.
203-- This is a brute force primitive. Avoid using it as long as possible, use it
204-- when no other combinator can do the job. This can be used to do pretty much
205-- anything in an imperative manner, as it just breaks down the stream into
206-- individual elements and we can loop over them as we deem fit. For example,
207-- this can be used to convert a streamly stream into other stream types.
209-- All the folds in this module can be expressed in terms of 'uncons', however
210-- the specific implementations are generally more efficient.
214uncons :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (a, t m a))
215uncons m = K.uncons (K.adapt m)
217------------------------------------------------------------------------------
219------------------------------------------------------------------------------
221-- | Right associative/lazy pull fold. @foldrM build final stream@ constructs
222-- an output structure using the step function @build@. @build@ is invoked with
223-- the next input element and the remaining (lazy) tail of the output
224-- structure. It builds a lazy output expression using the two. When the "tail
225-- structure" in the output expression is evaluated it calls @build@ again thus
226-- lazily consuming the input @stream@ until either the output expression built
227-- by @build@ is free of the "tail" or the input is exhausted in which case
228-- @final@ is used as the terminating case for the output structure. For more
229-- details see the description in the previous section.
231-- Example, determine if any element is 'odd' in a stream:
233-- >>> Stream.foldrM (\x xs -> if odd x then return True else xs) (return False) $ Stream.fromList (2:4:5:undefined)
236-- /Since: 0.7.0 (signature changed)/
238-- /Since: 0.2.0 (signature changed)/
242foldrM :: Monad m => (a -> m b -> m b) -> m b -> SerialT m a -> m b
245-- | Right fold, lazy for lazy monads and pure streams, and strict for strict
248-- Please avoid using this routine in strict monads like IO unless you need a
249-- strict right fold. This is provided only for use in lazy monads (e.g.
250-- Identity) or pure streams. Note that with this signature it is not possible
251-- to implement a lazy foldr when the monad @m@ is strict. In that case it
252-- would be strict in its accumulator and therefore would necessarily consume
257foldr :: Monad m => (a -> b -> b) -> b -> SerialT m a -> m b
260-- XXX This seems to be of limited use as it cannot be used to construct
261-- recursive structures and for reduction foldl1' is better.
263-- | Lazy right fold for non-empty streams, using first element as the starting
264-- value. Returns 'Nothing' if the stream is empty.
268{-# DEPRECATED foldr1 "Use foldrM instead." #-}
269foldr1 :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
270foldr1 f m = S.foldr1 f (toStreamS m)
272------------------------------------------------------------------------------
274------------------------------------------------------------------------------
276-- | Strict left fold with an extraction function. Like the standard strict
277-- left fold, but applies a user supplied extraction function (the third
278-- argument) to the folded value at the end. This is designed to work with the
279-- @foldl@ library. The suffix @x@ is a mnemonic for extraction.
282{-# DEPRECATED foldx "Please use foldl' followed by fmap instead." #-}
284foldx :: Monad m => (x -> a -> x) -> x -> (x -> b) -> SerialT m a -> m b
287-- | Left associative/strict push fold. @foldl' reduce initial stream@ invokes
288-- @reduce@ with the accumulator and the next input in the input stream, using
289-- @initial@ as the initial value of the current value of the accumulator. When
290-- the input is exhausted the current value of the accumulator is returned.
291-- Make sure to use a strict data structure for accumulator to not build
292-- unnecessary lazy expressions unless that's what you want. See the previous
293-- section for more details.
297foldl' :: Monad m => (b -> a -> b) -> b -> SerialT m a -> m b
300-- | Strict left fold, for non-empty streams, using first element as the
301-- starting value. Returns 'Nothing' if the stream is empty.
304{-# INLINE foldl1' #-}
305foldl1' :: Monad m => (a -> a -> a) -> SerialT m a -> m (Maybe a)
309 Nothing -> return Nothing
311 res <- foldl' step h t
314-- | Like 'foldx', but with a monadic step function.
317{-# DEPRECATED foldxM "Please use foldlM' followed by fmap instead." #-}
319foldxM :: Monad m => (x -> a -> m x) -> m x -> (x -> m b) -> SerialT m a -> m b
322-- | Like 'foldl'' but with a monadic step function.
326-- /Since: 0.8.0 (signature change)/
327{-# INLINE foldlM' #-}
328foldlM' :: Monad m => (b -> a -> m b) -> m b -> SerialT m a -> m b
329foldlM' step begin m = S.foldlM' step begin $ toStreamS m
331------------------------------------------------------------------------------
333------------------------------------------------------------------------------
336-- | Drain a stream to a 'Sink'.
337{-# INLINE runSink #-}
338runSink :: Monad m => Sink m a -> SerialT m a -> m ()
339runSink = fold . toFold
342------------------------------------------------------------------------------
344------------------------------------------------------------------------------
346-- | Parse a stream using the supplied ParserD 'PRD.Parser'.
350{-# INLINE_NORMAL parseD #-}
351parseD :: MonadThrow m => PRD.Parser m a b -> SerialT m a -> m b
352parseD p = D.parse p . toStreamD
354-- | Parse a stream using the supplied ParserK 'PRK.Parser'.
358parseK :: MonadThrow m => PRK.Parser m a b -> SerialT m a -> m b
361-- | Parse a stream using the supplied 'Parser'.
363-- Unlike folds, parsers may not always result in a valid output, they may
364-- result in an error. For example:
366-- >>> Stream.parse (Parser.takeEQ 1 Fold.drain) Stream.nil
367-- *** Exception: ParseError "takeEQ: Expecting exactly 1 elements, input terminated on 0"
372-- fold f = Stream.parse (Parser.fromFold f)
375-- @parse p@ is not the same as @head . parseMany p@ on an empty stream.
379{-# INLINE [3] parse #-}
380parse :: MonadThrow m => Parser m a b -> SerialT m a -> m b
381parse = parseD . PRK.fromParserK
383{-# INLINE_NORMAL parseD_ #-}
384parseD_ :: MonadThrow m => PRD.Parser m a b -> SerialT m a -> m (b, SerialT m a)
385parseD_ parser strm = do
386 (b, strmD) <- D.parse_ parser (toStreamD strm)
387 return $! (b, fromStreamD strmD)
389-- | Parse a stream using the supplied 'Parser'.
393{-# INLINE [3] parse_ #-}
394parse_ :: MonadThrow m => Parser m a b -> SerialT m a -> m (b, SerialT m a)
395parse_ = parseD_ . PRK.fromParserK
397------------------------------------------------------------------------------
398-- Specific Fold Functions
399------------------------------------------------------------------------------
401-- XXX this can utilize parallel mapping if we implement it as drain . mapM
403-- > mapM_ = Stream.drain . Stream.mapM
405-- Apply a monadic action to each element of the stream and discard the output
406-- of the action. This is not really a pure transformation operation but a
407-- transformation followed by fold.
411mapM_ :: Monad m => (a -> m b) -> SerialT m a -> m ()
412mapM_ f m = S.mapM_ f $ toStreamS m
415-- > drain = mapM_ (\_ -> return ())
416-- > drain = Stream.fold Fold.drain
418-- Run a stream, discarding the results. By default it interprets the stream
419-- as 'SerialT', to run other types of streams use the type adapting
420-- combinators for example @Stream.drain . 'fromAsync'@.
424drain :: Monad m => SerialT m a -> m ()
428-- > drainN n = Stream.drain . Stream.take n
429-- > drainN n = Stream.fold (Fold.take n Fold.drain)
431-- Run maximum up to @n@ iterations of a stream.
435drainN :: Monad m => Int -> SerialT m a -> m ()
436drainN n = drain . take n
439-- > runN n = runStream . take n
441-- Run maximum up to @n@ iterations of a stream.
444{-# DEPRECATED runN "Please use \"drainN\" instead" #-}
446runN :: Monad m => Int -> SerialT m a -> m ()
450-- > drainWhile p = Stream.drain . Stream.takeWhile p
452-- Run a stream as long as the predicate holds true.
455{-# INLINE drainWhile #-}
456drainWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
457drainWhile p = drain . takeWhile p
460-- > runWhile p = runStream . takeWhile p
462-- Run a stream as long as the predicate holds true.
465{-# DEPRECATED runWhile "Please use \"drainWhile\" instead" #-}
466{-# INLINE runWhile #-}
467runWhile :: Monad m => (a -> Bool) -> SerialT m a -> m ()
470-- | Run a stream, discarding the results. By default it interprets the stream
471-- as 'SerialT', to run other types of streams use the type adapting
472-- combinators for example @runStream . 'fromAsync'@.
475{-# DEPRECATED runStream "Please use \"drain\" instead" #-}
476{-# INLINE runStream #-}
477runStream :: Monad m => SerialT m a -> m ()
480-- | Determine whether the stream is empty.
482-- > null = Stream.fold Fold.null
486null :: Monad m => SerialT m a -> m Bool
487null = S.null . toStreamS
489-- | Extract the first element of the stream, if any.
492-- > head = Stream.fold Fold.head
496head :: Monad m => SerialT m a -> m (Maybe a)
497head = S.head . toStreamS
499-- | Extract the first element of the stream, if any, otherwise use the
500-- supplied default value. It can help avoid one branch in high performance
504{-# INLINE headElse #-}
505headElse :: Monad m => a -> SerialT m a -> m a
506headElse x = D.headElse x . toStreamD
509-- > tail = fmap (fmap snd) . Stream.uncons
511-- Extract all but the first element of the stream, if any.
515tail :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
516tail m = K.tail (K.adapt m)
518-- | Extract all but the last element of the stream, if any.
522init :: (IsStream t, Monad m) => SerialT m a -> m (Maybe (t m a))
523init m = K.init (K.adapt m)
525-- | Extract the last element of the stream, if any.
527-- > last xs = xs !! (Stream.length xs - 1)
528-- > last = Stream.fold Fold.last
532last :: Monad m => SerialT m a -> m (Maybe a)
533last m = S.last $ toStreamS m
535-- | Determine whether an element is present in the stream.
537-- > elem = Stream.fold Fold.elem
541elem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
542elem e m = S.elem e (toStreamS m)
544-- | Determine whether an element is not present in the stream.
546-- > notElem = Stream.fold Fold.length
549{-# INLINE notElem #-}
550notElem :: (Monad m, Eq a) => a -> SerialT m a -> m Bool
551notElem e m = S.notElem e (toStreamS m)
553-- | Determine the length of the stream.
557length :: Monad m => SerialT m a -> m Int
558length = foldl' (\n _ -> n + 1) 0
560-- | Determine whether all elements of a stream satisfy a predicate.
562-- > all = Stream.fold Fold.all
566all :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
567all p m = S.all p (toStreamS m)
569-- | Determine whether any of the elements of a stream satisfy a predicate.
571-- > any = Stream.fold Fold.any
575any :: Monad m => (a -> Bool) -> SerialT m a -> m Bool
576any p m = S.any p (toStreamS m)
578-- | Determines if all elements of a boolean stream are True.
580-- > and = Stream.fold Fold.and
584and :: Monad m => SerialT m Bool -> m Bool
587-- | Determines whether at least one element of a boolean stream is True.
589-- > or = Stream.fold Fold.or
593or :: Monad m => SerialT m Bool -> m Bool
596-- | Determine the sum of all elements of a stream of numbers. Returns @0@ when
597-- the stream is empty. Note that this is not numerically stable for floating
600-- > sum = Stream.fold Fold.sum
604sum :: (Monad m, Num a) => SerialT m a -> m a
607-- | Determine the product of all elements of a stream of numbers. Returns @1@
608-- when the stream is empty.
610-- > product = Stream.fold Fold.product
613{-# INLINE product #-}
614product :: (Monad m, Num a) => SerialT m a -> m a
615product = foldl' (*) 1
617-- | Fold a stream of monoid elements by appending them.
619-- > mconcat = Stream.fold Fold.mconcat
622{-# INLINE mconcat #-}
623mconcat :: (Monad m, Monoid a) => SerialT m a -> m a
624mconcat = foldr mappend mempty
628-- minimum = 'minimumBy' compare
629 -- minimum = Stream.fold Fold.minimum
632-- Determine the minimum element in a stream.
635{-# INLINE minimum #-}
636minimum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
637minimum m = S.minimum (toStreamS m)
639-- | Determine the minimum element in a stream using the supplied comparison
642-- > minimumBy = Stream.fold Fold.minimumBy
645{-# INLINE minimumBy #-}
646minimumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
647minimumBy cmp m = S.minimumBy cmp (toStreamS m)
651-- maximum = 'maximumBy' compare
652-- maximum = Stream.fold Fold.maximum
655-- Determine the maximum element in a stream.
658{-# INLINE maximum #-}
659maximum :: (Monad m, Ord a) => SerialT m a -> m (Maybe a)
662-- | Determine the maximum element in a stream using the supplied comparison
665-- > maximumBy = Stream.fold Fold.maximumBy
668{-# INLINE maximumBy #-}
669maximumBy :: Monad m => (a -> a -> Ordering) -> SerialT m a -> m (Maybe a)
670maximumBy cmp m = S.maximumBy cmp (toStreamS m)
672-- | Ensures that all the elements of the stream are identical and then returns
673-- that unique element.
677the :: (Eq a, Monad m) => SerialT m a -> m (Maybe a)
678the m = S.the (toStreamS m)
680------------------------------------------------------------------------------
682------------------------------------------------------------------------------
684-- | Lookup the element at the given index.
688(!!) :: Monad m => SerialT m a -> Int -> m (Maybe a)
689m !! i = toStreamS m S.!! i
691-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
692-- first pair where the key equals the given value @a@.
694-- > lookup = snd <$> Stream.find ((==) . fst)
695-- > lookup = Stream.fold Fold.lookup
699lookup :: (Monad m, Eq a) => a -> SerialT m (a, b) -> m (Maybe b)
700lookup a m = S.lookup a (toStreamS m)
702-- | Like 'findM' but with a non-monadic predicate.
704-- > find p = findM (return . p)
705-- > find = Stream.fold Fold.find
709find :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe a)
710find p m = S.find p (toStreamS m)
712-- | Returns the first element that satisfies the given predicate.
714-- > findM = Stream.fold Fold.findM
718findM :: Monad m => (a -> m Bool) -> SerialT m a -> m (Maybe a)
719findM p m = S.findM p (toStreamS m)
721-- | Returns the first index that satisfies the given predicate.
723-- > findIndex = Stream.fold Fold.findIndex
726{-# INLINE findIndex #-}
727findIndex :: Monad m => (a -> Bool) -> SerialT m a -> m (Maybe Int)
728findIndex p = head . findIndices p
730-- | Returns the first index where a given value is found in the stream.
732-- > elemIndex a = Stream.findIndex (== a)
735{-# INLINE elemIndex #-}
736elemIndex :: (Monad m, Eq a) => a -> SerialT m a -> m (Maybe Int)
737elemIndex a = findIndex (== a)
739------------------------------------------------------------------------------
741------------------------------------------------------------------------------
745-- toList = Stream.foldr (:) []
748-- Convert a stream into a list in the underlying monad. The list can be
749-- consumed lazily in a lazy monad (e.g. 'Identity'). In a strict monad (e.g.
750-- IO) the whole list is generated and buffered before it can be consumed.
752-- /Warning!/ working on large lists accumulated as buffers in memory could be
753-- very inefficient, consider using "Streamly.Array" instead.
757toList :: Monad m => SerialT m a -> m [a]
762-- toListRev = Stream.foldl' (flip (:)) []
765-- Convert a stream into a list in reverse order in the underlying monad.
767-- /Warning!/ working on large lists accumulated as buffers in memory could be
768-- very inefficient, consider using "Streamly.Array" instead.
771{-# INLINE toListRev #-}
772toListRev :: Monad m => SerialT m a -> m [a]
773toListRev = D.toListRev . toStreamD
777-- toHandle h = S.mapM_ $ hPutStrLn h
780-- Write a stream of Strings to an IO Handle.
783{-# DEPRECATED toHandle
784 "Please use Streamly.FileSystem.Handle module (see the changelog)" #-}
785toHandle :: MonadIO m => IO.Handle -> SerialT m String -> m ()
790 single a = liftIO (IO.hPutStrLn h a)
791 yieldk a r = liftIO (IO.hPutStrLn h a) >> go r
792 in K.foldStream defState yieldk single stop m1
794-- | Convert a stream to a pure stream.
797-- toStream = Stream.foldr Stream.cons Stream.nil
802{-# INLINE toStream #-}
803toStream :: Monad m => SerialT m a -> m (SerialT Identity a)
804toStream = foldr K.cons K.nil
806-- | Convert a stream to a pure stream in reverse order.
809-- toStreamRev = Stream.foldl' (flip Stream.cons) Stream.nil
814{-# INLINE toStreamRev #-}
815toStreamRev :: Monad m => SerialT m a -> m (SerialT Identity a)
816toStreamRev = foldl' (flip K.cons) K.nil
818------------------------------------------------------------------------------
819-- Concurrent Application
820------------------------------------------------------------------------------
822-- | Parallel fold application operator; applies a fold function @t m a -> m b@
823-- to a stream @t m a@ concurrently; The the input stream is evaluated
824-- asynchronously in an independent thread yielding elements to a buffer and
825-- the folding action runs in another thread consuming the input from the
828-- If you read the signature as @(t m a -> m b) -> (t m a -> m b)@ you can look
829-- at it as a transformation that converts a fold function to a buffered
830-- concurrent fold function.
832-- The @.@ at the end of the operator is a mnemonic for termination of the
835-- In the example below, each stage introduces a delay of 1 sec but output is
836-- printed every second because both stages are concurrent.
838-- >>> import Control.Concurrent (threadDelay)
839-- >>> import Streamly.Prelude ((|$.))
841-- Stream.foldlM' (\_ a -> threadDelay 1000000 >> print a) (return ())
842-- |$. Stream.replicateM 3 (threadDelay 1000000 >> return 1)
850-- /Since: 0.3.0 ("Streamly")/
854(|$.) :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
855-- (|$.) f = f . Async.mkAsync
856(|$.) f = f . Par.mkParallel
864{-# INLINE foldAsync #-}
865foldAsync :: (IsStream t, MonadAsync m) => (t m a -> m b) -> (t m a -> m b)
868-- | Same as '|$.' but with arguments reversed.
870-- > (|&.) = flip (|$.)
874-- /Since: 0.3.0 ("Streamly")/
878(|&.) :: (IsStream t, MonadAsync m) => t m a -> (t m a -> m b) -> m b
883------------------------------------------------------------------------------
885------------------------------------------------------------------------------
887-- | Returns 'True' if the first stream is the same as or a prefix of the
888-- second. A stream is a prefix of itself.
890-- >>> Stream.isPrefixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
894{-# INLINE isPrefixOf #-}
895isPrefixOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
896isPrefixOf m1 m2 = D.isPrefixOf (toStreamD m1) (toStreamD m2)
898-- | Returns 'True' if the first stream is an infix of the second. A stream is
899-- considered an infix of itself.
901-- > Stream.isInfixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
904-- Space: @O(n)@ worst case where @n@ is the length of the infix.
908-- /Requires 'Storable' constraint/
910{-# INLINE isInfixOf #-}
911isInfixOf :: (MonadIO m, Eq a, Enum a, Storable a)
912 => SerialT m a -> SerialT m a -> m Bool
913isInfixOf infx stream = do
914 arr <- fold A.write infx
915 -- XXX can use breakOnSeq instead (when available)
916 r <- null $ drop 1 $ splitOnSeq arr FL.drain stream
919-- Note: isPrefixOf uses the prefix stream only once. In contrast, isSuffixOf
920-- may use the suffix stream many times. To run in optimal memory we do not
921-- want to buffer the suffix stream in memory therefore we need an ability to
922-- clone (or consume it multiple times) the suffix stream without any side
923-- effects so that multiple potential suffix matches can proceed in parallel
924-- without buffering the suffix stream. For example, we may create the suffix
925-- stream from a file handle, however, if we evaluate the stream multiple
926-- times, once for each match, we will need a different file handle each time
927-- which may exhaust the file descriptors. Instead, we want to share the same
928-- underlying file descriptor, use pread on it to generate the stream and clone
929-- the stream for each match. Therefore the suffix stream should be built in
930-- such a way that it can be consumed multiple times without any problems.
932-- XXX Can be implemented with better space/time complexity.
933-- Space: @O(n)@ worst case where @n@ is the length of the suffix.
935-- | Returns 'True' if the first stream is a suffix of the second. A stream is
936-- considered a suffix of itself.
938-- >>> Stream.isSuffixOf (Stream.fromList "hello") (Stream.fromList "hello" :: SerialT IO Char)
941-- Space: @O(n)@, buffers entire input stream and the suffix.
945-- /Suboptimal/ - Help wanted.
947{-# INLINE isSuffixOf #-}
948isSuffixOf :: (Monad m, Eq a) => SerialT m a -> SerialT m a -> m Bool
949isSuffixOf suffix stream = reverse suffix `isPrefixOf` reverse stream
951-- | Returns 'True' if all the elements of the first stream occur, in order, in
952-- the second stream. The elements do not have to occur consecutively. A stream
953-- is a subsequence of itself.
955-- >>> Stream.isSubsequenceOf (Stream.fromList "hlo") (Stream.fromList "hello" :: SerialT IO Char)
959{-# INLINE isSubsequenceOf #-}
960isSubsequenceOf :: (Eq a, IsStream t, Monad m) => t m a -> t m a -> m Bool
961isSubsequenceOf m1 m2 = D.isSubsequenceOf (toStreamD m1) (toStreamD m2)
963-- Note: If we want to return a Maybe value to know whether the
964-- suffix/infix was present or not along with the stripped stream then
965-- we need to buffer the whole input stream.
967-- | @stripPrefix prefix stream@ strips @prefix@ from @stream@ if it is a
968-- prefix of stream. Returns 'Nothing' if the stream does not start with the
969-- given prefix, stripped stream otherwise. Returns @Just nil@ when the prefix
970-- is the same as the stream.
972-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropPrefix".
977{-# INLINE stripPrefix #-}
979 :: (Eq a, IsStream t, Monad m)
980 => t m a -> t m a -> m (Maybe (t m a))
981stripPrefix m1 m2 = fmap fromStreamD <$>
982 D.stripPrefix (toStreamD m1) (toStreamD m2)
984-- | Drops the given suffix from a stream. Returns 'Nothing' if the stream does
985-- not end with the given suffix. Returns @Just nil@ when the suffix is the
986-- same as the stream.
988-- It may be more efficient to convert the stream to an Array and use
989-- stripSuffix on that especially if the elements have a Storable or Prim
992-- See also "Streamly.Internal.Data.Stream.IsStream.Nesting.dropSuffix".
994-- Space: @O(n)@, buffers the entire input stream as well as the suffix
997{-# INLINE stripSuffix #-}
1000 => SerialT m a -> SerialT m a -> m (Maybe (SerialT m a))
1001stripSuffix m1 m2 = fmap reverse <$> stripPrefix (reverse m1) (reverse m2)
1003------------------------------------------------------------------------------
1005------------------------------------------------------------------------------
1007-- | Compare two streams for equality using an equality function.
1010{-# INLINABLE eqBy #-}
1011eqBy :: (IsStream t, Monad m) => (a -> b -> Bool) -> t m a -> t m b -> m Bool
1014-- | Compare two streams lexicographically using a comparison function.
1017{-# INLINABLE cmpBy #-}
1019 :: (IsStream t, Monad m)
1020 => (a -> b -> Ordering) -> t m a -> t m b -> m Ordering
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