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-- Monoids allow modular folding in general. Most of the folds in this module
28-- can be expressed using 'mconcat' and a suitable 'Monoid'. Instead of writing
29-- folds we can write Monoids instead and turn them into folds.
33-- 'Fold' representation is more efficient than using streams when splitting
34-- streams. @Fold m a b@ can be considered roughly equivalent to a fold action
35-- @m b -> t m a -> m b@ (where @t@ is a stream type and @m@ is a 'Monad').
36-- Instead of using a 'Fold' type one could just use a fold action of the shape
37-- @m b -> t m a -> m b@ for folding streams. However, multiple such actions
38-- cannot be composed into a single fold function in an efficient manner.
39-- Using the 'Fold' type we can efficiently split the stream across mutliple
40-- folds because it allows the compiler to perform stream fusion optimizations.
42-- On the other hand, transformation operations (e.g. 'Streamly.Prelude.map')
43-- on stream types can be as efficient as transformations on 'Fold' (e.g.
44-- 'Streamly.Internal.Data.Fold.lmap').
46-- = Left folds vs Right Folds
48-- The folds in this module are left folds, therefore, even partial folds, e.g.
49-- @head@ in this module, would drain the whole stream. On the other hand, the
50-- partial folds in "Streamly.Prelude" module are lazy right folds and would
51-- terminate as soon as the result is determined. However, the folds in this
52-- module can be composed but the folds in "Streamly.Prelude" cannot be
57-- > import qualified Streamly.Data.Fold as FL
59-- More, not yet exposed, fold combinators can be found in
60-- "Streamly.Internal.Data.Fold".
62-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
64module Streamly.Data.Fold
68 -- A 'Fold' can be run over a stream using the 'Streamly.Prelude.fold'
71 -- >>> S.fold FL.sum (S.enumerateFromTo 1 100)
95 -- ** Full Folds (Monoidal)
100 -- ** Full Folds (To Containers)
101 -- | Avoid using these folds in scalable or performance critical
102 -- applications, they buffer all the input in GC memory which can be
103 -- detrimental to performance if the input is large.
123 -- XXX these are slower than right folds even when full input is used
130 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
131 -- output side, folds have an input side as well as an output side. In the
132 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
133 -- Transformations can be applied either on the input side or on the output
134 -- side. The 'Functor' instance of a fold maps on the output of the fold:
136 -- >>> S.fold (fmap show FL.sum) (S.enumerateFromTo 1 100)
139 -- However, the input side or contravariant transformations are more
140 -- interesting for folds. The following sections describe the input
141 -- transformation operations on a fold. The names of the operations are
142 -- consistent with their covariant counterparts in "Streamly.Prelude", the
143 -- only difference is that they are prefixed with 'l' which stands for
144 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
145 -- the type variable @a@ is on the left side.
147 -- ** Covariant Operations
164 -- ** Mapping Filters
168 -- ** Scanning Filters
173 -- | Insertion adds more elements to the stream.
196 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
197 -- of the stream to each fold and combines the results using a function.
201 -- |-------Fold m a b--------|
202 -- ---stream m a---| |---m (b,c,...)
203 -- |-------Fold m a c--------|
208 -- To compute the average of numbers in a stream without going through the
211 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
212 -- >>> S.fold avg (S.enumerateFromTo 1.0 100.0)
215 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
216 -- the input to both the folds and combines the outputs using Monoid or
217 -- Semigroup instances of the output types:
219 -- >>> import Data.Monoid (Sum)
220 -- >>> S.fold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
221 -- Just (Sum {getSum = 101.0})
223 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
230 -- Direct items in the input stream to different folds using a binary
239 -- | Direct values in the input stream to different folds using an n-ary
248 -- | In an input stream of key value pairs fold values for different keys
249 -- in individual output buckets using the given fold.
257 -- These can be expressed using lmap/lmapM and unzip
264 -- , duplicate -- experimental
269 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
270 foldl, map, mapM_, sequence, all, any, sum, product, elem,
271 notElem, maximum, minimum, head, last, tail, length, null,
272 reverse, iterate, init, and, or, lookup, foldr1, (!!),
273 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
274 span, splitAt, break, mapM)
276import 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