3-- Module : Streamly.Data.Fold
4-- Copyright : (c) 2019 Composewell Technologies
5-- License : BSD-3-Clause
6-- Maintainer : streamly@composewell.com
10-- Fast, composable stream consumers with ability to terminate, supporting
13-- Please refer to "Streamly.Internal.Data.Fold" for more functions that have
14-- not yet been released.
16module Streamly.Data.Fold
19 -- | To execute the code examples provided in this module in ghci, please
20 -- run the following commands first.
29 -- XXX Should we have a stream returning function in fold module?
46 -- | Folds that never terminate, these folds are much like strict left
47 -- folds. 'mconcat' is the fundamental accumulator. All other accumulators
48 -- can be expressed in terms of 'mconcat' using a suitable Monoid. Instead
49 -- of writing folds we could write Monoids and turn them into folds.
77 -- ** Non-Empty Accumulators
78 -- | Accumulators that do not have a default value, therefore, return
79 -- 'Nothing' on an empty stream.
86 -- ** Filtering Scanners
87 -- | Accumulators that are usually run as a scan using the 'scanMaybe'
97 -- ** Terminating Folds
117 -- * Incremental builders
118 -- | Mutable arrays ("Streamly.Data.MutArray") are basic builders. You can
119 -- use the 'Streamly.Data.MutArray.snoc' or
120 -- 'Streamly.Data.MutArray.writeAppend' operations to incrementally build
121 -- mutable arrays. The 'addOne' and 'addStream' combinators can be used to
122 -- incrementally build any type of structure using a fold, including arrays
123 -- or a stream of arrays.
125 -- Use pinned arrays if you are going to use the data for IO.
127 -- XXX should rename to "extract". can use "Fold.drive Stream.nil" instead,
133 -- XXX Can we use something like concatEffect to implement snocM?
141 -- | Combinators are modifiers of folds. In the type @Fold m a b@, @a@ is
142 -- the input type and @b@ is the output type. Transformations can be
143 -- applied either on the input side (contravariant) or on the output side
144 -- (covariant). Therefore, combinators are of one of the following general
147 -- * @... -> Fold m a b -> Fold m c b@ (input transformation)
148 -- * @... -> Fold m a b -> Fold m a c@ (output transformation)
150 -- The input side transformations are more interesting for folds. Most of
151 -- the following sections describe the input transformation operations on a
152 -- fold. When an operation makes sense on both input and output side we use
153 -- the prefix @l@ (for left) for input side operations and the prefix @r@
154 -- (for right) for output side operations.
156 -- ** Mapping on output
157 -- | The 'Functor' instance of a fold maps on the output of the fold:
159 -- >>> Stream.fold (fmap show Fold.sum) (Stream.enumerateFromTo 1 100)
164 -- ** Mapping on Input
168 -- ** Scanning and Filtering
175 -- -- ** Mapping Filters
194 -- ** Parallel Distribution
195 -- | For applicative composition using distribution see
196 -- "Streamly.Internal.Data.Fold.Tee".
205 -- | Direct items in the input stream to different folds using a binary
214 -- ** Key-value Collectors
220 -- ** Key-value Scanners
232 -- * Transforming the Monad
250 hiding (Foldable(..), filter, drop, dropWhile, take, takeWhile, zipWith,
251 map, mapM_, sequence, all, any,
252 notElem, head, last, tail,
253 reverse, iterate, init, and, or, lookup, (!!),
254 scanl, scanl1, replicate, concatMap, mconcat, unzip,
255 span, splitAt, break, mapM, maybe)
257import Streamly.Internal.Data.Fold
259#include "DocTestDataFold.hs"
263-- A 'Fold' is a consumer of a stream of values. A fold driver (such as
264-- 'Streamly.Data.Stream.fold') initializes the fold @accumulator@, runs the
265-- fold @step@ function in a loop, processing the input stream one element at a
266-- time and accumulating the result. The loop continues until the fold
267-- terminates, at which point the accumulated result is returned.
269-- For example, a 'sum' Fold represents a stream consumer that adds the values
270-- in the input stream:
272-- >>> Stream.fold Fold.sum $ Stream.fromList [1..100]
275-- Conceptually, a 'Fold' is a data type that mimics a strict left fold
276-- ('Data.List.foldl'). The above example is similar to a left fold using
277-- @(+)@ as the step and @0@ as the initial value of the accumulator:
279-- >>> Data.List.foldl' (+) 0 [1..100]
282-- 'Fold's have an early termination capability e.g. the 'one' fold terminates
283-- after consuming one element:
285-- >>> Stream.fold Fold.one $ Stream.fromList [1..]
288-- The above example is similar to the following right fold:
290-- >>> Prelude.foldr (\x _ -> Just x) Nothing [1..]
293-- 'Fold's can be combined together using combinators. For example, to create a
294-- fold that sums first two elements in a stream:
296-- >>> sumTwo = Fold.take 2 Fold.sum
297-- >>> Stream.fold sumTwo $ Stream.fromList [1..100]
300-- Folds can be combined to run in parallel on the same input. For example, to
301-- compute the average of numbers in a stream without going through the stream
304-- >>> avg = Fold.teeWith (/) Fold.sum (fmap fromIntegral Fold.length)
305-- >>> Stream.fold avg $ Stream.fromList [1.0..100.0]
308-- Folds can be combined so as to partition the input stream over multiple
309-- folds. For example, to count even and odd numbers in a stream:
311-- >>> split n = if even n then Left n else Right n
312-- >>> stream = fmap split $ Stream.fromList [1..100]
313-- >>> countEven = fmap (("Even " ++) . show) Fold.length
314-- >>> countOdd = fmap (("Odd " ++) . show) Fold.length
315-- >>> f = Fold.partition countEven countOdd
316-- >>> Stream.fold f stream
317-- ("Even 50","Odd 50")
319-- Terminating folds can be combined to parse the stream serially such that the
320-- first fold consumes the input until it terminates and the second fold
321-- consumes the rest of the input until it terminates:
323-- >>> f = Fold.splitWith (,) (Fold.take 8 Fold.toList) (Fold.takeEndBy (== '\n') Fold.toList)
324-- >>> Stream.fold f $ Stream.fromList "header: hello\n"
325-- ("header: ","hello\n")
327-- A 'Fold' can be applied repeatedly on a stream to transform it to a stream
328-- of fold results. To split a stream on newlines:
330-- >>> f = Fold.takeEndBy (== '\n') Fold.toList
331-- >>> Stream.fold Fold.toList $ Stream.foldMany f $ Stream.fromList "Hello there!\nHow are you\n"
332-- ["Hello there!\n","How are you\n"]
334-- Similarly, we can split the input of a fold too:
336-- >>> Stream.fold (Fold.many f Fold.toList) $ Stream.fromList "Hello there!\nHow are you\n"
337-- ["Hello there!\n","How are you\n"]
339-- = Folds vs. Streams
341-- We can often use streams or folds to achieve the same goal. However, streams
342-- are more efficient in composition of producers (e.g.
343-- 'Data.Stream.append' or 'Data.Stream.mergeBy') whereas folds are
344-- more efficient in composition of consumers (e.g. 'splitWith', 'partition'
347-- Streams are producers, transformations on streams happen on the output side:
351-- Stream.filter odd stream
353-- & Stream.fold Fold.sum
356-- >>> f $ Stream.fromList [1..100 :: Int]
359-- Folds are stream consumers with an input stream and an output value, stream
360-- transformations on folds happen on the input side:
369-- >>> Stream.fold f $ Stream.fromList [1..100 :: Int]
372-- Notice the similiarity in the definition of @f@ in both cases, the only
373-- difference is the composition by @&@ vs @$@ and the use @lmap@ vs @map@, the
374-- difference is due to output vs input side transformations.
376--------------------------------------------------------------------------------
378--------------------------------------------------------------------------------
380{-# DEPRECATED chunksOf "Please use 'groupsOf' instead" #-}
381{-# INLINE chunksOf #-}
382chunksOf :: Monad m => Int -> Fold m a b -> Fold m b c -> Fold m a c
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