2-- Module : Streamly.Internal.Data.Stream.Reduce
3-- Copyright : (c) 2017 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- Reduce streams by streams, folds or parsers.
11module Streamly.Internal.Data.Stream.Reduce
13 -- * Reduce By Streams
20 -- Reduce a stream by folding or parsing chunks of the stream. Functions
21 -- generally ending in these shapes:
24 -- f (Fold m a b) -> Stream m a -> Stream m b
25 -- f (Parser a m b) -> Stream m a -> Stream m b
29 -- | Apply folds on a stream.
39 -- | Element unaware grouping.
43 -- XXX Implement these as folds or parsers instead.
48 -- * Reduce By Parsers
50 -- | Apply parsers on a stream.
60import Control.Monad.IO.Class (MonadIO(..))
61import Streamly.Internal.Data.Array.Type (Array)
62import Streamly.Internal.Data.Fold.Type (Fold (..))
63import Streamly.Internal.Data.Parser (Parser (..))
64import Streamly.Internal.Data.Parser (ParseError)
65import Streamly.Internal.Data.Refold.Type (Refold (..))
66import Streamly.Internal.Data.Stream.Bottom (foldManyPost)
67import Streamly.Internal.Data.Stream.Type (Stream, fromStreamD, toStreamD)
68import Streamly.Internal.Data.Unbox (Unbox)
70import qualified Streamly.Internal.Data.Array.Type as Array
71import qualified Streamly.Internal.Data.Parser as ParserD
72import qualified Streamly.Internal.Data.Stream as D
74import Prelude hiding (concatMap, map)
78-- >>> import Prelude hiding (zipWith, concatMap, concat)
79-- >>> import Streamly.Internal.Data.Stream as Stream
80-- >>> import qualified Streamly.Data.Fold as Fold
81-- >>> import qualified Streamly.Internal.Data.Fold as Fold
82-- >>> import qualified Streamly.Internal.Data.Unfold as Unfold
83-- >>> import qualified Streamly.Internal.Data.Parser as Parser
84-- >>> import qualified Streamly.Data.Array as Array
86------------------------------------------------------------------------------
88------------------------------------------------------------------------------
90-- | Drop prefix from the input stream if present.
95{-# INLINE dropPrefix #-}
98 Stream m a -> Stream m a -> Stream m a
99dropPrefix = error "Not implemented yet!"
101-- | Drop all matching infix from the input stream if present. Infix stream
102-- may be consumed multiple times.
104-- Space: @O(n)@ where n is the length of the infix.
107{-# INLINE dropInfix #-}
109 -- (Monad m, Eq a) =>
110 Stream m a -> Stream m a -> Stream m a
111dropInfix = error "Not implemented yet!"
113-- | Drop suffix from the input stream if present. Suffix stream may be
114-- consumed multiple times.
116-- Space: @O(n)@ where n is the length of the suffix.
119{-# INLINE dropSuffix #-}
121 -- (Monad m, Eq a) =>
122 Stream m a -> Stream m a -> Stream m a
123dropSuffix = error "Not implemented yet!"
125------------------------------------------------------------------------------
127------------------------------------------------------------------------------
129-- | Apply a 'Fold' repeatedly on a stream and emit the results in the
130-- output stream. Unlike 'foldManyPost' it evaluates the fold after the stream,
131-- therefore, an empty input stream results in an empty output stream.
135-- >>> foldMany f = Stream.parseMany (Parser.fromFold f)
137-- Example, empty stream:
139-- >>> f = Fold.take 2 Fold.sum
140-- >>> fmany = Stream.fold Fold.toList . Stream.foldMany f
141-- >>> fmany $ Stream.fromList []
144-- Example, last fold empty:
146-- >>> fmany $ Stream.fromList [1..4]
149-- Example, last fold non-empty:
151-- >>> fmany $ Stream.fromList [1..5]
154-- Note that using a closed fold e.g. @Fold.take 0@, would result in an
155-- infinite stream on a non-empty input stream.
157{-# INLINE foldMany #-}
163foldMany f m = fromStreamD $ D.foldMany f (toStreamD m)
165-- | Like 'foldMany' but using the 'Refold' type instead of 'Fold'.
168{-# INLINE refoldMany #-}
169refoldMany :: Monad m =>
170 Refold m c a b -> m c -> Stream m a -> Stream m b
171refoldMany f action = fromStreamD . D.refoldMany f action . toStreamD
173-- | Apply a stream of folds to an input stream and emit the results in the
178{-# INLINE foldSequence #-}
181 Stream m (Fold m a b)
184foldSequence _f _m = undefined
186-- | Iterate a fold generator on a stream. The initial value @b@ is used to
187-- generate the first fold, the fold is applied on the stream and the result of
188-- the fold is used to generate the next fold and so on.
190-- >>> import Data.Monoid (Sum(..))
191-- >>> f x = return (Fold.take 2 (Fold.sconcat x))
192-- >>> s = fmap Sum $ Stream.fromList [1..10]
193-- >>> Stream.fold Fold.toList $ fmap getSum $ Stream.foldIterateM f (pure 0) s
196-- This is the streaming equivalent of monad like sequenced application of
197-- folds where next fold is dependent on the previous fold.
201{-# INLINE foldIterateM #-}
203 Monad m => (b -> m (Fold m a b)) -> m b -> Stream m a -> Stream m b
204foldIterateM f i m = fromStreamD $ D.foldIterateM f i (toStreamD m)
206-- | Like 'foldIterateM' but using the 'Refold' type instead. This could be
207-- much more efficient due to stream fusion.
210{-# INLINE refoldIterateM #-}
211refoldIterateM :: Monad m =>
212 Refold m b a b -> m b -> Stream m a -> Stream m b
213refoldIterateM c i m = fromStreamD $ D.refoldIterateM c i (toStreamD m)
215-- | Binary BFS style reduce, folds a level entirely using the supplied fold
216-- function, collecting the outputs as next level of the tree, then repeats the
217-- same process on the next level. The last elements of a previously folded
218-- level are folded first.
219{-# INLINE reduceIterateBfs #-}
220reduceIterateBfs :: Monad m =>
221 (a -> a -> m a) -> Stream m a -> m (Maybe a)
222reduceIterateBfs f stream = D.reduceIterateBfs f (toStreamD stream)
224------------------------------------------------------------------------------
226------------------------------------------------------------------------------
228-- Implement this as a fold or a parser instead.
229-- This can be implemented easily using Rabin Karp
230-- | Split post any one of the given patterns.
233{-# INLINE splitOnSuffixSeqAny #-}
234splitOnSuffixSeqAny :: -- (Monad m, Unboxed a, Integral a) =>
235 [Array a] -> Fold m a b -> Stream m a -> Stream m b
236splitOnSuffixSeqAny _subseq _f _m = undefined
237 -- D.fromStreamD $ D.splitPostAny f subseq (D.toStreamD m)
239-- | Split on a prefixed separator element, dropping the separator. The
240-- supplied 'Fold' is applied on the split segments.
243-- > splitOnPrefix' p xs = Stream.toList $ Stream.splitOnPrefix p (Fold.toList) (Stream.fromList xs)
244-- > splitOnPrefix' (== '.') ".a.b"
248-- An empty stream results in an empty output stream:
250-- > splitOnPrefix' (== '.') ""
254-- An empty segment consisting of only a prefix is folded to the default output
258-- > splitOnPrefix' (== '.') "."
261-- > splitOnPrefix' (== '.') ".a.b."
264-- > splitOnPrefix' (== '.') ".a..b"
269-- A prefix is optional at the beginning of the stream:
272-- > splitOnPrefix' (== '.') "a"
275-- > splitOnPrefix' (== '.') "a.b"
279-- 'splitOnPrefix' is an inverse of 'intercalatePrefix' with a single element:
281-- > Stream.intercalatePrefix (Stream.fromPure '.') Unfold.fromList . Stream.splitOnPrefix (== '.') Fold.toList === id
283-- Assuming the input stream does not contain the separator:
285-- > Stream.splitOnPrefix (== '.') Fold.toList . Stream.intercalatePrefix (Stream.fromPure '.') Unfold.fromList === id
288{-# INLINE splitOnPrefix #-}
289splitOnPrefix :: -- (IsStream t, MonadCatch m) =>
290 (a -> Bool) -> Fold m a b -> Stream m a -> Stream m b
291splitOnPrefix _predicate _f = undefined
292 -- parseMany (Parser.sliceBeginBy predicate f)
294-- Int list examples for splitOn:
296-- >>> splitList [] [1,2,3,3,4]
297-- > [[1],[2],[3],[3],[4]]
299-- >>> splitList [5] [1,2,3,3,4]
302-- >>> splitList [1] [1,2,3,3,4]
305-- >>> splitList [4] [1,2,3,3,4]
308-- >>> splitList [2] [1,2,3,3,4]
311-- >>> splitList [3] [1,2,3,3,4]
314-- >>> splitList [3,3] [1,2,3,3,4]
317-- >>> splitList [1,2,3,3,4] [1,2,3,3,4]
320-- This can be implemented easily using Rabin Karp
321-- | Split on any one of the given patterns.
325{-# INLINE splitOnAny #-}
326splitOnAny :: -- (Monad m, Unboxed a, Integral a) =>
327 [Array a] -> Fold m a b -> Stream m a -> Stream m b
328splitOnAny _subseq _f _m =
329 undefined -- D.fromStreamD $ D.splitOnAny f subseq (D.toStreamD m)
331------------------------------------------------------------------------------
333------------------------------------------------------------------------------
335-- | Apply a 'Parser' repeatedly on a stream and emit the parsed values in the
340-- >>> s = Stream.fromList [1..10]
341-- >>> parser = Parser.takeBetween 0 2 Fold.sum
342-- >>> Stream.fold Fold.toList $ Stream.parseMany parser s
343-- [Right 3,Right 7,Right 11,Right 15,Right 19]
345-- This is the streaming equivalent of the 'Streamly.Data.Parser.many' parse
348-- Known Issues: When the parser fails there is no way to get the remaining
351{-# INLINE parseMany #-}
356 -> Stream m (Either ParseError b)
358 fromStreamD $ D.parseManyD p (toStreamD m)
360-- | Same as parseMany but for StreamD streams.
364{-# INLINE parseManyD #-}
367 => ParserD.Parser a m b
369 -> Stream m (Either ParseError b)
371 fromStreamD $ D.parseManyD p (toStreamD m)
373-- | Apply a stream of parsers to an input stream and emit the results in the
378{-# INLINE parseSequence #-}
381 Stream m (Parser a m b)
384parseSequence _f _m = undefined
386-- XXX Change the parser arguments' order
388-- | @parseManyTill collect test stream@ tries the parser @test@ on the input,
389-- if @test@ fails it backtracks and tries @collect@, after @collect@ succeeds
390-- @test@ is tried again and so on. The parser stops when @test@ succeeds. The
391-- output of @test@ is discarded and the output of @collect@ is emitted in the
392-- output stream. The parser fails if @collect@ fails.
396{-# INLINE parseManyTill #-}
403parseManyTill = undefined
405-- | Iterate a parser generating function on a stream. The initial value @b@ is
406-- used to generate the first parser, the parser is applied on the stream and
407-- the result is used to generate the next parser and so on.
409-- >>> import Data.Monoid (Sum(..))
410-- >>> s = Stream.fromList [1..10]
411-- >>> Stream.fold Fold.toList $ fmap getSum $ Stream.catRights $ Stream.parseIterate (\b -> Parser.takeBetween 0 2 (Fold.sconcat b)) (Sum 0) $ fmap Sum s
414-- This is the streaming equivalent of monad like sequenced application of
415-- parsers where next parser is dependent on the previous parser.
419{-# INLINE parseIterate #-}
422 => (b -> Parser a m b)
425 -> Stream m (Either ParseError b)
426parseIterate f i m = fromStreamD $
427 D.parseIterateD f i (toStreamD m)
429------------------------------------------------------------------------------
431------------------------------------------------------------------------------
433-- | @chunksOf n stream@ groups the elements in the input stream into arrays of
436-- Same as the following but may be more efficient:
438-- >>> chunksOf n = Stream.foldMany (Array.writeN n)
441{-# INLINE chunksOf #-}
442chunksOf :: (MonadIO m, Unbox a)
443 => Int -> Stream m a -> Stream m (Array a)
444chunksOf n = fromStreamD . Array.chunksOf n . toStreamD
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