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').
42-- > import qualified Streamly.Data.Fold as FL
44-- More, not yet exposed, fold combinators can be found in
45-- "Streamly.Internal.Data.Fold".
47-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
49module Streamly.Data.Fold
53 -- A 'Fold' can be run over a stream using the 'Streamly.Prelude.fold'
56 -- >>> S.fold FL.sum (S.enumerateFromTo 1 100)
80 -- ** Full Folds (Monoidal)
85 -- ** Full Folds (To Containers)
86 -- | Avoid using these folds in scalable or performance critical
87 -- applications, they buffer all the input in GC memory which can be
88 -- detrimental to performance if the input is large.
108 -- XXX these are slower than right folds even when full input is used
115 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
116 -- output side, folds have an input side as well as an output side. In the
117 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
118 -- Transformations can be applied either on the input side or on the output
119 -- side. The 'Functor' instance of a fold maps on the output of the fold:
121 -- >>> S.fold (fmap show FL.sum) (S.enumerateFromTo 1 100)
124 -- However, the input side or contravariant transformations are more
125 -- interesting for folds. The following sections describe the input
126 -- transformation operations on a fold. The names of the operations are
127 -- consistent with their covariant counterparts in "Streamly.Prelude", the
128 -- only difference is that they are prefixed with 'l' which stands for
129 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
130 -- the type variable @a@ is on the left side.
132 -- ** Covariant Operations
149 -- ** Mapping Filters
153 -- ** Scanning Filters
158 -- | Insertion adds more elements to the stream.
181 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
182 -- of the stream to each fold and combines the results using a function.
186 -- |-------Fold m a b--------|
187 -- ---stream m a---| |---m (b,c,...)
188 -- |-------Fold m a c--------|
193 -- To compute the average of numbers in a stream without going through the
196 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
197 -- >>> S.fold avg (S.enumerateFromTo 1.0 100.0)
200 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
201 -- the input to both the folds and combines the outputs using Monoid or
202 -- Semigroup instances of the output types:
204 -- >>> import Data.Monoid (Sum)
205 -- >>> S.fold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
206 -- Just (Sum {getSum = 101.0})
208 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
215 -- Direct items in the input stream to different folds using a binary
224 -- | Direct values in the input stream to different folds using an n-ary
233 -- | In an input stream of key value pairs fold values for different keys
234 -- in individual output buckets using the given fold.
242 -- These can be expressed using lmap/lmapM and unzip
249 -- , duplicate -- experimental
254 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
255 foldl, map, mapM_, sequence, all, any, sum, product, elem,
256 notElem, maximum, minimum, head, last, tail, length, null,
257 reverse, iterate, init, and, or, lookup, foldr1, (!!),
258 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
259 span, splitAt, break, mapM)
261import 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