2-- Module : Streamly.Data.Fold
3-- Copyright : (c) 2019 Composewell Technologies
4-- License : BSD-3-Clause
5-- Maintainer : streamly@composewell.com
9-- A 'Fold' is a sink or a consumer of a stream of values. The 'Fold' type
10-- consists of an accumulator and an effectful action that absorbs a value into
13-- >>> import Data.Function ((&))
14-- >>> import qualified Streamly.Data.Fold as Fold
15-- >>> import qualified Streamly.Data.Stream as Stream
17-- For example, a 'sum' Fold represents adding the input to the accumulated
18-- sum. A fold driver e.g. 'Streamly.Prelude.fold' pushes values from a stream
19-- to the 'Fold' one at a time, reducing the stream to a single value.
21-- >>> Stream.fold Fold.sum $ Stream.fromList [1..100]
24-- Conceptually, a 'Fold' is a data type that can mimic a strict left fold
25-- ('Data.List.foldl') as well as lazy right fold ('Prelude.foldr'). The above
26-- example is similar to a left fold using @(+)@ as the step and @0@ as the
27-- initial value of the accumulator:
29-- >>> Data.List.foldl' (+) 0 [1..100]
32-- 'Fold's have an early termination capability e.g. the 'one' fold would
33-- terminate on an infinite stream:
35-- >>> Stream.fold Fold.one $ Stream.fromList [1..]
38-- The above example is similar to the following right fold:
40-- >>> Prelude.foldr (\x _ -> Just x) Nothing [1..]
43-- 'Fold's can be combined together using combinators. For example, to create a
44-- fold that sums first two elements in a stream:
46-- >>> sumTwo = Fold.take 2 Fold.sum
47-- >>> Stream.fold sumTwo $ Stream.fromList [1..100]
50-- Folds can be combined to run in parallel on the same input. For example, to
51-- compute the average of numbers in a stream without going through the stream
54-- >>> avg = Fold.teeWith (/) Fold.sum (fmap fromIntegral Fold.length)
55-- >>> Stream.fold avg $ Stream.fromList [1.0..100.0]
58-- Folds can be combined so as to partition the input stream over multiple
59-- folds. For example, to count even and odd numbers in a stream:
61-- >>> split n = if even n then Left n else Right n
62-- >>> stream = fmap split $ Stream.fromList [1..100]
63-- >>> countEven = fmap (("Even " ++) . show) Fold.length
64-- >>> countOdd = fmap (("Odd " ++) . show) Fold.length
65-- >>> f = Fold.partition countEven countOdd
66-- >>> Stream.fold f stream
67-- ("Even 50","Odd 50")
69-- Terminating folds can be combined to parse the stream serially such that the
70-- first fold consumes the input until it terminates and the second fold
71-- consumes the rest of the input until it terminates:
73-- >>> f = Fold.serialWith (,) (Fold.take 8 Fold.toList) (Fold.takeEndBy (== '\n') Fold.toList)
74-- >>> Stream.fold f $ Stream.fromList "header: hello\n"
75-- ("header: ","hello\n")
77-- A 'Fold' can be applied repeatedly on a stream to transform it to a stream
78-- of fold results. To split a stream on newlines:
80-- >>> f = Fold.takeEndBy (== '\n') Fold.toList
81-- >>> Stream.fold Fold.toList $ Stream.foldMany f $ Stream.fromList "Hello there!\nHow are you\n"
82-- ["Hello there!\n","How are you\n"]
84-- Similarly, we can split the input of a fold too:
86-- >>> Stream.fold (Fold.many f Fold.toList) $ Stream.fromList "Hello there!\nHow are you\n"
87-- ["Hello there!\n","How are you\n"]
89-- Please see "Streamly.Internal.Data.Fold" for additional @Pre-release@
94-- We can often use streams or folds to achieve the same goal. However, streams
95-- are more efficient in composition of producers (e.g.
96-- 'Streamly.Prelude.serial' or 'Streamly.Prelude.mergeBy') whereas folds are
97-- more efficient in composition of consumers (e.g. 'serialWith', 'partition'
100-- Streams are producers, transformations on streams happen on the output side:
104-- Stream.filter odd stream
106-- & Stream.fold Fold.sum
109-- >>> f $ Stream.fromList [1..100 :: Int]
112-- Folds are stream consumers with an input stream and an output value, stream
113-- transformations on folds happen on the input side:
122-- >>> Stream.fold f $ Stream.fromList [1..100 :: Int]
125-- Notice the similiarity in the definition of @f@ in both cases, the only
126-- difference is the composition by @&@ vs @$@ and the use @lmap@ vs @map@, the
127-- difference is due to output vs input side transformations.
129module Streamly.Data.Fold
142 -- | Folds that never terminate, these folds are much like strict left
143 -- folds. 'mconcat' is the fundamental accumulator. All other accumulators
144 -- can be expressed in terms of 'mconcat' using a suitable Monoid. Instead
145 -- of writing folds we could write Monoids and turn them into folds.
166 , rollingHashWithSalt
172 -- ** Terminating Folds
173 -- | These are much like lazy right folds.
190 -- | Combinators are modifiers of folds. In the type @Fold m a b@, @a@ is
191 -- the input type and @b@ is the output type. Transformations can be
192 -- applied either on the input side or on the output side. Therefore,
193 -- combinators are of one of the following general shapes:
195 -- * @... -> Fold m a b -> Fold m c b@ (input transformation)
196 -- * @... -> Fold m a b -> Fold m a c@ (output transformation)
198 -- Output transformations are also known as covariant transformations, and
199 -- input transformations are also known as contravariant transformations.
200 -- The input side transformations are more interesting for folds. Most of
201 -- the following sections describe the input transformation operations on a
202 -- fold. The names and signatures of the operations are consistent with
203 -- corresponding operations in "Streamly.Prelude". When an operation makes
204 -- sense on both input and output side we use the prefix @l@ (for left) for
205 -- input side operations and the prefix @r@ (for right) for output side
208 -- ** Mapping on output
209 -- | The 'Functor' instance of a fold maps on the output of the fold:
211 -- >>> Stream.fold (fmap show Fold.sum) (Stream.enumerateFromTo 1 100)
216 -- ** Mapping on Input
224 -- -- ** Mapping Filters
237 -- ** Parallel Distribution
238 -- | For applicative composition using distribution see
239 -- "Streamly.Internal.Data.Fold.Tee".
248 -- | Direct items in the input stream to different folds using a binary
278 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
279 foldl, map, mapM_, sequence, all, any, sum, product, elem,
280 notElem, maximum, minimum, head, last, tail, length, null,
281 reverse, iterate, init, and, or, lookup, foldr1, (!!),
282 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
283 span, splitAt, break, mapM)
285import Streamly.Internal.Data.Fold
288-- >>> import Data.Function ((&))
289-- >>> import qualified Streamly.Data.Fold as Fold
290-- >>> import qualified Streamly.Data.Stream as Stream
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