2-- Module : Streamly.Data.Fold
3-- Copyright : (c) 2019 Composewell Technologies
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- 'Fold' type represents an effectful action that consumes a value from an
10-- input stream and combines it with a single final value often called an
11-- accumulator, returning the resulting output accumulator. Values from a
12-- stream can be /pushed/ to the fold and consumed one at a time. It can also
13-- be called a consumer of stream or a sink. It is a data representation of
14-- the standard 'Streamly.Prelude.foldl'' function. A 'Fold' can be turned
15-- into an effect (@m b@) using 'Streamly.Prelude.fold' by supplying it the
18-- Using this representation multiple folds can be combined efficiently using
19-- combinators; a stream can then be supplied to the combined fold and it would
20-- distribute the input to constituent folds according to the composition. For
21-- example, an applicative composition distributes the same input to the
22-- constituent folds and then combines the resulting fold outputs. Similarly,
23-- a partitioning combinator divides the input among constituent folds.
27-- 'Fold' representation is more efficient than using streams when splitting
28-- streams. @Fold m a b@ can be considered roughly equivalent to a fold action
29-- @m b -> t m a -> m b@ (where @t@ is a stream type and @m@ is a 'Monad').
30-- Instead of using a 'Fold' type one could just use a fold action of the shape
31-- @m b -> t m a -> m b@ for folding streams. However, multiple such actions
32-- cannot be composed into a single fold function in an efficient manner.
33-- Using the 'Fold' type we can efficiently split the stream across mutliple
34-- folds because it allows the compiler to perform stream fusion optimizations.
36-- On the other hand, transformation operations (e.g. 'Streamly.Prelude.map')
37-- on stream types can be as efficient as transformations on 'Fold' (e.g.
38-- 'Streamly.Internal.Data.Fold.lmap').
40-- = Left folds vs Right Folds
42-- The folds in this module are left folds, therefore, even partial folds, e.g.
43-- @head@ in this module, would drain the whole stream. On the other hand, the
44-- partial folds in "Streamly.Prelude" module are lazy right folds and would
45-- terminate as soon as the result is determined. However, the folds in this
46-- module can be composed but the folds in "Streamly.Prelude" cannot be
51-- > import qualified Streamly.Data.Fold as FL
53-- More, not yet exposed, fold combinators can be found in
54-- "Streamly.Internal.Data.Fold".
56-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
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)
89 -- ** Full Folds (Monoidal)
94 -- ** Full Folds (To Containers)
95 -- | Avoid using these folds in scalable or performance critical
96 -- applications, they buffer all the input in GC memory which can be
97 -- detrimental to performance if the input is large.
117 -- XXX these are slower than right folds even when full input is used
124 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
125 -- output side, folds have an input side as well as an output side. In the
126 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
127 -- Transformations can be applied either on the input side or on the output
128 -- side. The 'Functor' instance of a fold maps on the output of the fold:
130 -- >>> S.fold (fmap show FL.sum) (S.enumerateFromTo 1 100)
133 -- However, the input side or contravariant transformations are more
134 -- interesting for folds. The following sections describe the input
135 -- transformation operations on a fold. The names of the operations are
136 -- consistent with their covariant counterparts in "Streamly.Prelude", the
137 -- only difference is that they are prefixed with 'l' which stands for
138 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
139 -- the type variable @a@ is on the left side.
141 -- ** Covariant Operations
158 -- ** Mapping Filters
162 -- ** Scanning Filters
167 -- | Insertion adds more elements to the stream.
190 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
191 -- of the stream to each fold and combines the results using a function.
195 -- |-------Fold m a b--------|
196 -- ---stream m a---| |---m (b,c,...)
197 -- |-------Fold m a c--------|
202 -- To compute the average of numbers in a stream without going through the
205 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
206 -- >>> S.fold avg (S.enumerateFromTo 1.0 100.0)
209 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
210 -- the input to both the folds and combines the outputs using Monoid or
211 -- Semigroup instances of the output types:
213 -- >>> import Data.Monoid (Sum)
214 -- >>> S.fold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
215 -- Just (Sum {getSum = 101.0})
217 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
224 -- Direct items in the input stream to different folds using a binary
233 -- | Direct values in the input stream to different folds using an n-ary
242 -- | In an input stream of key value pairs fold values for different keys
243 -- in individual output buckets using the given fold.
251 -- These can be expressed using lmap/lmapM and unzip
258 -- , duplicate -- experimental
263 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
264 foldl, map, mapM_, sequence, all, any, sum, product, elem,
265 notElem, maximum, minimum, head, last, tail, length, null,
266 reverse, iterate, init, and, or, lookup, foldr1, (!!),
267 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
268 span, splitAt, break, mapM)
270import 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