2-- Module : Streamly.Internal.Data.Stream.Expand
3-- Copyright : (c) 2017 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- Expand a stream by combining two or more streams or by combining streams
12module Streamly.Internal.Data.Stream.Expand
14 -- * Binary Combinators (Linear)
15 -- | Functions ending in the shape:
17 -- @Stream m a -> Stream m a -> Stream m a@.
19 -- The functions in this section have a linear or flat n-ary combining
20 -- characterstics. It means that when combined @n@ times (e.g. @a `serial`
21 -- b `serial` c ...@) the resulting expression will have an @O(n)@
22 -- complexity (instead O(n^2) for pair wise combinators described in the
23 -- next section. These functions can be used efficiently with
24 -- 'concatMapWith' et. al. combinators that combine streams in a linear
25 -- fashion (contrast with 'mergeMapWith' which combines streams as a
29 -- * Binary Combinators (Pair Wise)
30 -- | Like the functions in the section above these functions also combine
31 -- two streams into a single stream but when used @n@ times linearly they
32 -- exhibit O(n^2) complexity. They are best combined in a binary tree
33 -- fashion using 'mergeMapWith' giving a @n * log n@ complexity. Avoid
34 -- using these with 'concatMapWith' when combining a large or infinite
45 , interleaveFstSuffix2
63 -- * Combine Streams and Unfolds
65 -- Expand a stream by repeatedly using an unfold and merging the resulting
66 -- streams. Functions generally ending in the shape:
68 -- @Unfold m a b -> Stream m a -> Stream m b@
70 -- ** Unfold and combine streams
71 -- | Unfold and flatten streams.
72 , unfoldMany -- XXX Rename to unfoldAppend
77 -- | Insert effects between streams. Like unfoldMany but intersperses an
78 -- effect between the streams. A special case of gintercalate.
84 -- | Insert Streams between Streams.
85 -- Like unfoldMany but intersperses streams from another source between
86 -- the streams from the first source.
92 -- * Combine Streams of Streams
93 -- | Map and serially append streams. 'concatMapM' is a generalization of
94 -- the binary append operation to append many streams.
101 -- | Map and flatten a stream like 'concatMap' but using a custom binary
102 -- stream merging combinator instead of just appending the streams. The
103 -- merging occurs sequentially, it works efficiently for 'serial', 'async',
104 -- 'ahead' like merge operations where we consume one stream before the
105 -- next or in case of 'wAsync' or 'parallel' where we consume all streams
106 -- simultaneously anyway.
108 -- However, in cases where the merging consumes streams in a round robin
109 -- fashion, a pair wise merging using 'mergeMapWith' would be more
110 -- efficient. These cases include operations like 'mergeBy' or 'zipWith'.
117 -- | See the notes about suitable merge functions in the 'concatMapWith'
122 -- | Map and flatten Trees of Streams
125 , unfoldIterateBfsRev
133 -- More experimental ops
134 , concatIterateBfsRev
135 , concatIterateLeftsWith
136 , concatIterateScanWith
143import Streamly.Internal.Data.Stream.Bottom
144 ( concatEffect, concatMapM, concatMap, smapM, zipWith, zipWithM)
145import Streamly.Internal.Data.Stream.Type
146 ( Stream, fromStreamD, fromStreamK, toStreamD, toStreamK
147 , bindWith, concatMapWith, cons, nil)
148import Streamly.Internal.Data.Unfold.Type (Unfold)
150import qualified Streamly.Internal.Data.Stream as D
151import qualified Streamly.Internal.Data.StreamK as K (mergeBy, mergeByM)
152import qualified Streamly.Internal.Data.Stream.StreamK.Type as K
154import Prelude hiding (concat, concatMap, zipWith)
158-- >>> import Data.Either (either)
159-- >>> import Data.IORef
160-- >>> import Streamly.Internal.Data.Stream (Stream)
161-- >>> import Prelude hiding (zipWith, concatMap, concat)
162-- >>> import qualified Streamly.Data.Array as Array
163-- >>> import qualified Streamly.Internal.Data.Fold as Fold
164-- >>> import qualified Streamly.Internal.Data.Stream as Stream
165-- >>> import qualified Streamly.Internal.Data.Unfold as Unfold
166-- >>> import qualified Streamly.Internal.Data.Parser as Parser
167-- >>> import qualified Streamly.Internal.FileSystem.Dir as Dir
170------------------------------------------------------------------------------
172------------------------------------------------------------------------------
176-- | This is fused version of 'append'. It could be up to 100x faster than
177-- 'append' when combining two fusible streams. However, it slows down
178-- quadratically with the number of streams being appended. Therefore, it is
179-- suitable for ad-hoc append of a few streams, and should not be used with
180-- 'concatMapWith' or 'mergeMapWith'.
184{-# INLINE append2 #-}
185append2 ::Monad m => Stream m b -> Stream m b -> Stream m b
186append2 m1 m2 = fromStreamD $ D.append (toStreamD m1) (toStreamD m2)
190-- | Appends two streams sequentially, yielding all elements from the first
191-- stream, and then all elements from the second stream.
193-- >>> s1 = Stream.fromList [1,2]
194-- >>> s2 = Stream.fromList [3,4]
195-- >>> Stream.fold Fold.toList $ s1 `Stream.append` s2
198-- This has O(n) append performance where @n@ is the number of streams. It can
199-- be used to efficiently fold an infinite lazy container of streams
200-- 'concatMapWith' et. al.
202-- See 'append2' for a fusible alternative.
206append :: Stream m a -> Stream m a -> Stream m a
209------------------------------------------------------------------------------
211------------------------------------------------------------------------------
215-- | Interleaves two streams, yielding one element from each stream
216-- alternately. When one stream stops the rest of the other stream is used in
219-- When joining many streams in a left associative manner earlier streams will
220-- get exponential priority than the ones joining later. Because of exponential
221-- weighting it can be used with 'concatMapWith' even on a large number of
224-- See 'interleave2' for a fusible alternative.
227{-# INLINE interleave #-}
228interleave :: Stream m a -> Stream m a -> Stream m a
229interleave s1 s2 = fromStreamK $ K.interleave (toStreamK s1) (toStreamK s2)
231{-# INLINE interleave2 #-}
232interleave2 :: Monad m => Stream m a -> Stream m a -> Stream m a
233interleave2 s1 s2 = fromStreamD $ D.interleave (toStreamD s1) (toStreamD s2)
235-- | Like `interleave` but stops interleaving as soon as the first stream
238-- See 'interleaveFst2' for a fusible alternative.
241{-# INLINE interleaveFst #-}
242interleaveFst :: Stream m a -> Stream m a -> Stream m a
244 fromStreamK $ K.interleaveFst (toStreamK s1) (toStreamK s2)
246-- | Like `interleave` but stops interleaving as soon as any of the two streams
249-- See 'interleaveMin2' for a fusible alternative.
252{-# INLINE interleaveMin #-}
253interleaveMin :: Stream m a -> Stream m a -> Stream m a
255 fromStreamK $ K.interleaveMin (toStreamK s1) (toStreamK s2)
257{-# INLINE interleaveMin2 #-}
258interleaveMin2 :: Monad m => Stream m a -> Stream m a -> Stream m a
259interleaveMin2 s1 s2 =
260 fromStreamD $ D.interleaveMin (toStreamD s1) (toStreamD s2)
262-- | Interleaves the outputs of two streams, yielding elements from each stream
263-- alternately, starting from the first stream. As soon as the first stream
264-- finishes, the output stops, discarding the remaining part of the second
265-- stream. In this case, the last element in the resulting stream would be from
266-- the second stream. If the second stream finishes early then the first stream
267-- still continues to yield elements until it finishes.
269-- >>> :set -XOverloadedStrings
270-- >>> import Data.Functor.Identity (Identity)
271-- >>> Stream.interleaveFstSuffix2 "abc" ",,,," :: Stream Identity Char
273-- >>> Stream.interleaveFstSuffix2 "abc" "," :: Stream Identity Char
276-- 'interleaveFstSuffix2' is a dual of 'interleaveFst2'.
278-- Do not use at scale in concatMapWith.
281{-# INLINE interleaveFstSuffix2 #-}
282interleaveFstSuffix2 :: Monad m => Stream m b -> Stream m b -> Stream m b
283interleaveFstSuffix2 m1 m2 =
284 fromStreamD $ D.interleaveFstSuffix (toStreamD m1) (toStreamD m2)
286-- | Interleaves the outputs of two streams, yielding elements from each stream
287-- alternately, starting from the first stream and ending at the first stream.
288-- If the second stream is longer than the first, elements from the second
289-- stream are infixed with elements from the first stream. If the first stream
290-- is longer then it continues yielding elements even after the second stream
293-- >>> :set -XOverloadedStrings
294-- >>> import Data.Functor.Identity (Identity)
295-- >>> Stream.interleaveFst2 "abc" ",,,," :: Stream Identity Char
297-- >>> Stream.interleaveFst2 "abc" "," :: Stream Identity Char
300-- 'interleaveFst2' is a dual of 'interleaveFstSuffix2'.
302-- Do not use at scale in concatMapWith.
305{-# INLINE interleaveFst2 #-}
306interleaveFst2 :: Monad m => Stream m b -> Stream m b -> Stream m b
307interleaveFst2 m1 m2 =
308 fromStreamD $ D.interleaveFst (toStreamD m1) (toStreamD m2)
310------------------------------------------------------------------------------
312------------------------------------------------------------------------------
314-- | Schedule the execution of two streams in a fair round-robin manner,
315-- executing each stream once, alternately. Execution of a stream may not
316-- necessarily result in an output, a stream may chose to @Skip@ producing an
317-- element until later giving the other stream a chance to run. Therefore, this
318-- combinator fairly interleaves the execution of two streams rather than
319-- fairly interleaving the output of the two streams. This can be useful in
320-- co-operative multitasking without using explicit threads. This can be used
321-- as an alternative to `async`.
323-- Do not use at scale in concatMapWith.
326{-# INLINE roundrobin #-}
327roundrobin :: Monad m => Stream m b -> Stream m b -> Stream m b
328roundrobin m1 m2 = fromStreamD $ D.roundRobin (toStreamD m1) (toStreamD m2)
330------------------------------------------------------------------------------
331-- Merging (sorted streams)
332------------------------------------------------------------------------------
334-- | Merge two streams using a comparison function. The head elements of both
335-- the streams are compared and the smaller of the two elements is emitted, if
336-- both elements are equal then the element from the first stream is used
339-- If the streams are sorted in ascending order, the resulting stream would
340-- also remain sorted in ascending order.
342-- >>> s1 = Stream.fromList [1,3,5]
343-- >>> s2 = Stream.fromList [2,4,6,8]
344-- >>> Stream.fold Fold.toList $ Stream.mergeBy compare s1 s2
347-- See 'mergeByM2' for a fusible alternative.
350{-# INLINE mergeBy #-}
351mergeBy :: (a -> a -> Ordering) -> Stream m a -> Stream m a -> Stream m a
352mergeBy f m1 m2 = fromStreamK $ K.mergeBy f (toStreamK m1) (toStreamK m2)
354-- | Like 'mergeBy' but with a monadic comparison function.
356-- Merge two streams randomly:
359-- > randomly _ _ = randomIO >>= \x -> return $ if x then LT else GT
360-- > Stream.toList $ Stream.mergeByM randomly (Stream.fromList [1,1,1,1]) (Stream.fromList [2,2,2,2])
364-- Merge two streams in a proportion of 2:1:
368-- let s1 = Stream.fromList [1,1,1,1,1,1]
369-- s2 = Stream.fromList [2,2,2]
370-- let proportionately m n = do
371-- ref <- newIORef $ cycle $ Prelude.concat [Prelude.replicate m LT, Prelude.replicate n GT]
372-- return $ \_ _ -> do
374-- writeIORef ref $ Prelude.tail r
375-- return $ Prelude.head r
376-- f <- proportionately 2 1
377-- xs <- Stream.fold Fold.toList $ Stream.mergeByM f s1 s2
380-- [1,1,2,1,1,2,1,1,2]
382-- See 'mergeByM2' for a fusible alternative.
385{-# INLINE mergeByM #-}
388 => (a -> a -> m Ordering) -> Stream m a -> Stream m a -> Stream m a
389mergeByM f m1 m2 = fromStreamK $ K.mergeByM f (toStreamK m1) (toStreamK m2)
391-- | Like 'mergeByM' but much faster, works best when merging statically known
392-- number of streams. When merging more than two streams try to merge pairs and
393-- pair of pairs in a tree like structure.'mergeByM' works better with variable
394-- number of streams being merged using 'mergeMapWith'.
397{-# INLINE mergeByM2 #-}
400 => (a -> a -> m Ordering) -> Stream m a -> Stream m a -> Stream m a
402 fromStreamD $ D.mergeByM f (toStreamD m1) (toStreamD m2)
404-- | Like 'mergeByM' but stops merging as soon as any of the two streams stops.
407{-# INLINABLE mergeMinBy #-}
408mergeMinBy :: -- Monad m =>
409 (a -> a -> m Ordering) -> Stream m a -> Stream m a -> Stream m a
410mergeMinBy _f _m1 _m2 = undefined
411 -- fromStreamD $ D.mergeMinBy f (toStreamD m1) (toStreamD m2)
413-- | Like 'mergeByM' but stops merging as soon as the first stream stops.
416{-# INLINABLE mergeFstBy #-}
417mergeFstBy :: -- Monad m =>
418 (a -> a -> m Ordering) -> Stream m a -> Stream m a -> Stream m a
419mergeFstBy _f _m1 _m2 = undefined
420 -- fromStreamK $ D.mergeFstBy f (toStreamD m1) (toStreamD m2)
422------------------------------------------------------------------------------
423-- Combine N Streams - unfoldMany
424------------------------------------------------------------------------------
426-- | Like 'concatMap' but uses an 'Unfold' for stream generation. Unlike
427-- 'concatMap' this can fuse the 'Unfold' code with the inner loop and
428-- therefore provide many times better performance.
430{-# INLINE unfoldMany #-}
431unfoldMany ::Monad m => Unfold m a b -> Stream m a -> Stream m b
432unfoldMany u m = fromStreamD $ D.unfoldMany u (toStreamD m)
434-- | This does not pair streams like mergeMapWith, instead, it goes through
435-- each stream one by one and yields one element from each stream. After it
436-- goes to the last stream it reverses the traversal to come back to the first
437-- stream yielding elements from each stream on its way back to the first
440-- >>> lists = Stream.fromList [[1,1],[2,2],[3,3],[4,4],[5,5]]
441-- >>> interleaved = Stream.unfoldInterleave Unfold.fromList lists
442-- >>> Stream.fold Fold.toList interleaved
443-- [1,2,3,4,5,5,4,3,2,1]
445-- Note that this is order of magnitude more efficient than "mergeMapWith
446-- wSerial" because of fusion.
449{-# INLINE unfoldInterleave #-}
450unfoldInterleave ::Monad m => Unfold m a b -> Stream m a -> Stream m b
451unfoldInterleave u m =
452 fromStreamD $ D.unfoldInterleave u (toStreamD m)
454-- | 'unfoldInterleave' switches to the next stream whenever a value from a
455-- stream is yielded, it does not switch on a 'Skip'. So if a stream keeps
456-- skipping for long time other streams won't get a chance to run.
457-- 'unfoldRoundRobin' switches on Skip as well. So it basically schedules each
458-- stream fairly irrespective of whether it produces a value or not.
460{-# INLINE unfoldRoundRobin #-}
461unfoldRoundRobin ::Monad m => Unfold m a b -> Stream m a -> Stream m b
462unfoldRoundRobin u m =
463 fromStreamD $ D.unfoldRoundRobin u (toStreamD m)
465------------------------------------------------------------------------------
466-- Combine N Streams - interpose
467------------------------------------------------------------------------------
469-- > interpose x unf str = gintercalate unf str UF.identity (repeat x)
471-- | Unfold the elements of a stream, intersperse the given element between the
472-- unfolded streams and then concat them into a single stream.
474-- >>> unwords = Stream.interpose ' '
477{-# INLINE interpose #-}
479 => c -> Unfold m b c -> Stream m b -> Stream m c
481 fromStreamD $ D.interpose x unf (toStreamD str)
483-- interposeSuffix x unf str = gintercalateSuffix unf str UF.identity (repeat x)
485-- | Unfold the elements of a stream, append the given element after each
486-- unfolded stream and then concat them into a single stream.
488-- >>> unlines = Stream.interposeSuffix '\n'
491{-# INLINE interposeSuffix #-}
492interposeSuffix :: Monad m
493 => c -> Unfold m b c -> Stream m b -> Stream m c
494interposeSuffix x unf str =
495 fromStreamD $ D.interposeSuffix x unf (toStreamD str)
497------------------------------------------------------------------------------
498-- Combine N Streams - intercalate
499------------------------------------------------------------------------------
501-- XXX we can swap the order of arguments to gintercalate so that the
502-- definition of unfoldMany becomes simpler? The first stream should be
503-- infixed inside the second one. However, if we change the order in
504-- "interleave" as well similarly, then that will make it a bit unintuitive.
506-- > unfoldMany unf str =
507-- > gintercalate unf str (UF.nilM (\_ -> return ())) (repeat ())
509-- | 'interleaveFst' followed by unfold and concat.
512{-# INLINE gintercalate #-}
515 => Unfold m a c -> Stream m a -> Unfold m b c -> Stream m b -> Stream m c
516gintercalate unf1 str1 unf2 str2 =
517 fromStreamD $ D.gintercalate
518 unf1 (toStreamD str1)
519 unf2 (toStreamD str2)
521-- > intercalate unf seed str = gintercalate unf str unf (repeatM seed)
523-- | 'intersperse' followed by unfold and concat.
525-- >>> intercalate u a = Stream.unfoldMany u . Stream.intersperse a
526-- >>> intersperse = Stream.intercalate Unfold.identity
527-- >>> unwords = Stream.intercalate Unfold.fromList " "
529-- >>> input = Stream.fromList ["abc", "def", "ghi"]
530-- >>> Stream.fold Fold.toList $ Stream.intercalate Unfold.fromList " " input
533{-# INLINE intercalate #-}
534intercalate :: Monad m
535 => Unfold m b c -> b -> Stream m b -> Stream m c
536intercalate unf seed str = fromStreamD $
537 D.unfoldMany unf $ D.intersperse seed (toStreamD str)
539-- | 'interleaveFstSuffix2' followed by unfold and concat.
542{-# INLINE gintercalateSuffix #-}
545 => Unfold m a c -> Stream m a -> Unfold m b c -> Stream m b -> Stream m c
546gintercalateSuffix unf1 str1 unf2 str2 =
547 fromStreamD $ D.gintercalateSuffix
548 unf1 (toStreamD str1)
549 unf2 (toStreamD str2)
551-- > intercalateSuffix unf seed str = gintercalateSuffix unf str unf (repeatM seed)
553-- | 'intersperseMSuffix' followed by unfold and concat.
555-- >>> intercalateSuffix u a = Stream.unfoldMany u . Stream.intersperseMSuffix a
556-- >>> intersperseMSuffix = Stream.intercalateSuffix Unfold.identity
557-- >>> unlines = Stream.intercalateSuffix Unfold.fromList "\n"
559-- >>> input = Stream.fromList ["abc", "def", "ghi"]
560-- >>> Stream.fold Fold.toList $ Stream.intercalateSuffix Unfold.fromList "\n" input
563{-# INLINE intercalateSuffix #-}
564intercalateSuffix :: Monad m
565 => Unfold m b c -> b -> Stream m b -> Stream m c
566intercalateSuffix unf seed =
567 fromStreamD . D.intercalateSuffix unf seed . toStreamD
569------------------------------------------------------------------------------
570-- Combine N Streams - concatMap
571------------------------------------------------------------------------------
573-- | Flatten a stream of streams to a single stream.
575-- >>> concat = Stream.concatMap id
579concat :: Monad m => Stream m (Stream m a) -> Stream m a
582------------------------------------------------------------------------------
583-- Combine N Streams - concatMap
584------------------------------------------------------------------------------
586-- | Like 'concatMapWith' but carries a state which can be used to share
587-- information across multiple steps of concat.
589-- >>> concatSmapMWith combine f initial = Stream.concatMapWith combine id . Stream.smapM f initial
593{-# INLINE concatSmapMWith #-}
596 => (Stream m b -> Stream m b -> Stream m b)
597 -> (s -> a -> m (s, Stream m b))
601concatSmapMWith combine f initial =
602 concatMapWith combine id . smapM f initial
604-- XXX Implement a StreamD version for fusion.
606-- | Combine streams in pairs using a binary combinator, the resulting streams
607-- are then combined again in pairs recursively until we get to a single
608-- combined stream. The composition would thus form a binary tree.
610-- For example, you can sort a stream using merge sort like this:
612-- >>> s = Stream.fromList [5,1,7,9,2]
613-- >>> generate = Stream.fromPure
614-- >>> combine = Stream.mergeBy compare
615-- >>> Stream.fold Fold.toList $ Stream.mergeMapWith combine generate s
618-- Note that if the stream length is not a power of 2, the binary tree composed
619-- by mergeMapWith would not be balanced, which may or may not be important
620-- depending on what you are trying to achieve.
622-- /Caution: the stream of streams must be finite/
628{-# INLINE mergeMapWith #-}
630 (Stream m b -> Stream m b -> Stream m b)
634mergeMapWith par f m =
637 (\s1 s2 -> toStreamK $ fromStreamK s1 `par` fromStreamK s2)
641------------------------------------------------------------------------------
642-- concatIterate - Map and flatten Trees of Streams
643------------------------------------------------------------------------------
645-- | Yield an input element in the output stream, map a stream generator on it
646-- and repeat the process on the resulting stream. Resulting streams are
647-- flattened using the 'concatMapWith' combinator. This can be used for a depth
648-- first style (DFS) traversal of a tree like structure.
650-- Example, list a directory tree using DFS:
652-- >>> f = either Dir.readEitherPaths (const Stream.nil)
653-- >>> input = Stream.fromPure (Left ".")
654-- >>> ls = Stream.concatIterateWith Stream.append f input
656-- Note that 'iterateM' is a special case of 'concatIterateWith':
658-- >>> iterateM f = Stream.concatIterateWith Stream.append (Stream.fromEffect . f) . Stream.fromEffect
664{-# INLINE concatIterateWith #-}
666 (Stream m a -> Stream m a -> Stream m a)
670concatIterateWith combine f = iterateStream
674 iterateStream = concatMapWith combine generate
676 generate x = x `cons` iterateStream (f x)
678-- | Traverse the stream in depth first style (DFS). Map each element in the
679-- input stream to a stream and flatten, recursively map the resulting elements
680-- as well to a stream and flatten until no more streams are generated.
682-- Example, list a directory tree using DFS:
684-- >>> f = either (Just . Dir.readEitherPaths) (const Nothing)
685-- >>> input = Stream.fromPure (Left ".")
686-- >>> ls = Stream.concatIterateDfs f input
688-- This is equivalent to using @concatIterateWith Stream.append@.
691{-# INLINE concatIterateDfs #-}
692concatIterateDfs :: Monad m =>
693 (a -> Maybe (Stream m a))
696concatIterateDfs f stream =
698 $ D.concatIterateDfs (fmap toStreamD . f ) (toStreamD stream)
700-- | Similar to 'concatIterateDfs' except that it traverses the stream in
701-- breadth first style (BFS). First, all the elements in the input stream are
702-- emitted, and then their traversals are emitted.
704-- Example, list a directory tree using BFS:
706-- >>> f = either (Just . Dir.readEitherPaths) (const Nothing)
707-- >>> input = Stream.fromPure (Left ".")
708-- >>> ls = Stream.concatIterateBfs f input
711{-# INLINE concatIterateBfs #-}
712concatIterateBfs :: Monad m =>
713 (a -> Maybe (Stream m a))
716concatIterateBfs f stream =
718 $ D.concatIterateBfs (fmap toStreamD . f ) (toStreamD stream)
720-- | Same as 'concatIterateBfs' except that the traversal of the last
721-- element on a level is emitted first and then going backwards up to the first
722-- element (reversed ordering). This may be slightly faster than
723-- 'concatIterateBfs'.
725{-# INLINE concatIterateBfsRev #-}
726concatIterateBfsRev :: Monad m =>
727 (a -> Maybe (Stream m a))
730concatIterateBfsRev f stream =
732 $ D.concatIterateBfsRev (fmap toStreamD . f ) (toStreamD stream)
734-- | Like 'concatIterateWith' but uses the pairwise flattening combinator
735-- 'mergeMapWith' for flattening the resulting streams. This can be used for a
736-- balanced traversal of a tree like structure.
738-- Example, list a directory tree using balanced traversal:
740-- >>> f = either Dir.readEitherPaths (const Stream.nil)
741-- >>> input = Stream.fromPure (Left ".")
742-- >>> ls = Stream.mergeIterateWith Stream.interleave f input
748{-# INLINE mergeIterateWith #-}
750 (Stream m a -> Stream m a -> Stream m a)
754mergeIterateWith combine f = iterateStream
758 iterateStream = mergeMapWith combine generate
760 generate x = x `cons` iterateStream (f x)
762-- | Same as @concatIterateDfs@ but more efficient due to stream fusion.
764-- Example, list a directory tree using DFS:
766-- >>> f = Unfold.either Dir.eitherReaderPaths Unfold.nil
767-- >>> input = Stream.fromPure (Left ".")
768-- >>> ls = Stream.unfoldIterateDfs f input
771{-# INLINE unfoldIterateDfs #-}
772unfoldIterateDfs :: Monad m => Unfold m a a -> Stream m a -> Stream m a
773unfoldIterateDfs u = fromStreamD . D.unfoldIterateDfs u . toStreamD
775-- | Like 'unfoldIterateDfs' but uses breadth first style traversal.
778{-# INLINE unfoldIterateBfs #-}
779unfoldIterateBfs :: Monad m => Unfold m a a -> Stream m a -> Stream m a
780unfoldIterateBfs u = fromStreamD . D.unfoldIterateBfs u . toStreamD
782-- | Like 'unfoldIterateBfs' but processes the children in reverse order,
783-- therefore, may be slightly faster.
786{-# INLINE unfoldIterateBfsRev #-}
787unfoldIterateBfsRev :: Monad m => Unfold m a a -> Stream m a -> Stream m a
788unfoldIterateBfsRev u =
789 fromStreamD . D.unfoldIterateBfsRev u . toStreamD
791------------------------------------------------------------------------------
793------------------------------------------------------------------------------
795-- To traverse graphs we need a state to be carried around in the traversal.
796-- For example, we can use a hashmap to store the visited status of nodes.
798-- | Like 'iterateMap' but carries a state in the stream generation function.
799-- This can be used to traverse graph like structures, we can remember the
800-- visited nodes in the state to avoid cycles.
802-- Note that a combination of 'iterateMap' and 'usingState' can also be used to
803-- traverse graphs. However, this function provides a more localized state
804-- instead of using a global state.
810{-# INLINE concatIterateScanWith #-}
813 => (Stream m a -> Stream m a -> Stream m a)
814 -> (b -> a -> m (b, Stream m a))
818concatIterateScanWith combine f initial stream =
821 iterateStream (b, stream)
825 iterateStream (b, s) = pure $ concatMapWith combine (generate b) s
827 generate b a = a `cons` feedback b a
829 feedback b a = concatEffect $ f b a >>= iterateStream
831-- Next stream is to be generated by the return value of the previous stream. A
832-- general intuitive way of doing that could be to use an appending monad
833-- instance for streams where the result of the previous stream is used to
834-- generate the next one. In the first pass we can just emit the values in the
835-- stream and keep building a buffered list/stream, once done we can then
836-- process the buffered stream.
838{-# INLINE concatIterateScan #-}
842 -> (b -> m (Maybe (b, Stream m a)))
845concatIterateScan scanner generate initial =
847 $ D.concatIterateScan
848 scanner (fmap (fmap (fmap toStreamD)) . generate) initial
850------------------------------------------------------------------------------
852------------------------------------------------------------------------------
854-- Keep concating either streams as long as rights are generated, stop as soon
855-- as a left is generated and concat the left stream.
863 :: (forall x. t m x -> t m x -> t m x)
864 -> (a -> t m (Either (Stream m b) b))
867concatMapEitherWith = undefined
870-- XXX We should prefer using the Maybe stream returning signatures over this.
871-- This API should perhaps be removed in favor of those.
873-- | In an 'Either' stream iterate on 'Left's. This is a special case of
874-- 'concatIterateWith':
876-- >>> concatIterateLeftsWith combine f = Stream.concatIterateWith combine (either f (const Stream.nil))
878-- To traverse a directory tree:
880-- >>> input = Stream.fromPure (Left ".")
881-- >>> ls = Stream.concatIterateLeftsWith Stream.append Dir.readEither input
885{-# INLINE concatIterateLeftsWith #-}
886concatIterateLeftsWith
888 => (Stream m b -> Stream m b -> Stream m b)
892concatIterateLeftsWith combine f =
893 concatIterateWith combine (either f (const nil))
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