2-- Module : Streamly.Data.Fold
3-- Copyright : (c) 2019 Composewell Technologies
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- The 'Fold' type represents an effectful action that absorbs a value into an
10-- accumulator. For example, a 'sum' 'Fold' represents adding the input to the
11-- accumulated sum. A fold driver e.g. 'Streamly.Prelude.fold' pushes values
12-- from a stream to the 'Fold' one at a time, reducing the stream to a single
13-- value. Therefore, a fold can also be thought of as a sink or a stream
16-- A 'Fold' is in fact a data representation of a standard left fold ('foldl').
17-- Unlike the standard left folds, 'Fold's can terminate at any point e.g. the
18-- 'head' fold would terminate immediately after returning the head element.
20-- 'Fold's can be combined efficiently using combinators provided in this
21-- module; a stream supplied to the combined fold is provided to the
22-- constituent folds according to the behavior of the combinator. For example,
23-- the 'tee' combinator distributes the input stream to two folds and then
24-- combines the resulting fold outputs. Similarly, a 'partition' combinator
25-- divides the input among constituent folds.
27-- = Accumulators and Terminating Folds
29-- Folds in this module can be classified in two categories viz. accumulators
30-- and terminating folds. Accumulators do not have a terminating condition,
31-- they run forever and consume the entire stream, for example the 'length'
32-- fold. Terminating folds have a terminating condition and can terminate
33-- without consuming the entire stream, for example, the 'head' fold.
37-- Monoids allow generalized, modular folding. The accumulators in this module
38-- can be expressed using 'mconcat' and a suitable 'Monoid'. Instead of
39-- writing folds we can write Monoids and turn them into folds.
43-- 'Streamly.Prelude' module provides fold functions to directly fold streams
44-- e.g. Streamly.Prelude/'Streamly.Prelude.sum' serves the same purpose as
45-- Fold/'sum'. However, the functions in Streamly.Prelude cannot be
46-- efficiently combined together e.g. we cannot drive the input stream through
47-- @sum@ and @length@ fold functions simultaneously. Using the 'Fold' type we
48-- can efficiently split the stream across mutliple folds because it allows the
49-- compiler to perform stream fusion optimizations.
53-- > import qualified Streamly.Data.Fold as Fold
55-- More, not yet exposed, fold combinators can be found in
56-- "Streamly.Internal.Data.Fold".
58module Streamly.Data.Fold
62 -- A 'Fold' can be run over a stream using the 'Streamly.Prelude.fold'
65 -- >>> S.fold FL.sum (S.enumerateFromTo 1 100)
92 -- | Avoid using these folds in scalable or performance critical
93 -- applications, they buffer all the input in GC memory which can be
94 -- detrimental to performance if the input is large.
98 -- * Terminating Folds
119 -- * Output Transformations
120 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
121 -- output side, folds have an input side as well as an output side. In the
122 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
123 -- Transformations can be applied either on the input side or on the output
124 -- side. The 'Functor' instance of a fold maps on the output of the fold:
126 -- >>> S.fold (fmap show FL.sum) (S.enumerateFromTo 1 100)
129 -- Note: Output transformations are also known as covariant
135 -- * Input Transformations
136 -- The input side transformations are more interesting for folds. The
137 -- following sections describe the input transformation operations on a
138 -- fold. The names and signatures of the operations are consistent with
139 -- corresponding operations in "Streamly.Prelude".
141 -- Note: Input transformations are also known as contravariant
156 -- ** Mapping Filters
160 -- ** Scanning Filters
165 -- | Insertion adds more elements to the stream.
185 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
186 -- of the stream to each fold and combines the results using a function.
190 -- |-------Fold m a b--------|
191 -- ---stream m a---| |---m (b,c,...)
192 -- |-------Fold m a c--------|
197 -- To compute the average of numbers in a stream without going through the
200 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
201 -- >>> S.fold avg (S.enumerateFromTo 1.0 100.0)
204 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
205 -- the input to both the folds and combines the outputs using Monoid or
206 -- Semigroup instances of the output types:
208 -- >>> import Data.Monoid (Sum)
209 -- >>> S.fold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
210 -- Just (Sum {getSum = 101.0})
212 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
219 -- Direct items in the input stream to different folds using a binary
228 -- | Direct values in the input stream to different folds using an n-ary
237 -- | In an input stream of key value pairs fold values for different keys
238 -- in individual output buckets using the given fold.
246 -- These can be expressed using lmap/lmapM and unzip
253 -- , duplicate -- experimental
258 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
259 foldl, map, mapM_, sequence, all, any, sum, product, elem,
260 notElem, maximum, minimum, head, last, tail, length, null,
261 reverse, iterate, init, and, or, lookup, foldr1, (!!),
262 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
263 span, splitAt, break, mapM)
265import Streamly.Internal.Data.Fold
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