3-- Module : Streamly.Data.Fold
4-- Copyright : (c) 2019 Composewell Technologies
5-- License : BSD-3-Clause
6-- Maintainer : streamly@composewell.com
10-- Fast, composable stream consumers with ability to terminate, supporting
15-- This module provides elementary folds and fold combinators that can be used
16-- to consume a stream of data and reduce it to a final value, or transform it
17-- in a stateful manner using scans. A data stream can be reduced into a stream
18-- of folded data elements by folding segments of the stream. Fold combinators
19-- can be used to compose multiple folds in parallel or to create a pipeline of
20-- folds such that the next fold consumes the result of the previous fold. To
21-- run these folds on a stream see 'Streamly.Data.Stream.fold',
22-- 'Streamly.Data.Stream.scan', 'Streamly.Data.Stream.postscan',
23-- 'Streamly.Data.Stream.scanMaybe', 'Streamly.Data.Stream.foldMany' and other
24-- operations accepting 'Fold' type as argument "Streamly.Data.Stream".
26-- == Reducing a Stream
28-- A 'Fold' is a consumer of a stream of values. A fold driver (such as
29-- 'Streamly.Data.Stream.fold') initializes the fold @accumulator@, runs the
30-- fold @step@ function in a loop, processing the input stream one element at a
31-- time and accumulating the result. The loop continues until the fold
32-- terminates, at which point the accumulated result is returned.
34-- For example, a 'sum' Fold represents a stream consumer that adds the values
35-- in the input stream:
37-- >>> Stream.fold Fold.sum $ Stream.fromList [1..100]
40-- Conceptually, a 'Fold' is a data type that mimics a strict left fold
41-- ('Data.List.foldl'). The above example is similar to a left fold using
42-- @(+)@ as the step and @0@ as the initial value of the accumulator:
44-- >>> Data.List.foldl' (+) 0 [1..100]
47-- 'Fold's have an early termination capability e.g. the 'one' fold terminates
48-- after consuming one element:
50-- >>> Stream.fold Fold.one $ Stream.fromList [1..]
53-- The above example is similar to the following right fold:
55-- >>> Prelude.foldr (\x _ -> Just x) Nothing [1..]
58-- 'Fold's can be combined together using combinators. For example, to create a
59-- fold that sums first two elements in a stream:
61-- >>> sumTwo = Fold.take 2 Fold.sum
62-- >>> Stream.fold sumTwo $ Stream.fromList [1..100]
65-- == Parallel Composition
67-- Folds can be combined to run in parallel on the same input. For example, to
68-- compute the average of numbers in a stream without going through the stream
71-- >>> avg = Fold.teeWith (/) Fold.sum (fmap fromIntegral Fold.length)
72-- >>> Stream.fold avg $ Stream.fromList [1.0..100.0]
75-- Folds can be combined so as to partition the input stream over multiple
76-- folds. For example, to count even and odd numbers in a stream:
78-- >>> split n = if even n then Left n else Right n
79-- >>> stream = fmap split $ Stream.fromList [1..100]
80-- >>> countEven = fmap (("Even " ++) . show) Fold.length
81-- >>> countOdd = fmap (("Odd " ++) . show) Fold.length
82-- >>> f = Fold.partition countEven countOdd
83-- >>> Stream.fold f stream
84-- ("Even 50","Odd 50")
86-- == Sequential Composition
88-- Terminating folds can be combined to parse the stream serially such that the
89-- first fold consumes the input until it terminates and the second fold
90-- consumes the rest of the input until it terminates:
92-- >>> f = Fold.splitWith (,) (Fold.take 8 Fold.toList) (Fold.takeEndBy (== '\n') Fold.toList)
93-- >>> Stream.fold f $ Stream.fromList "header: hello\n"
94-- ("header: ","hello\n")
96-- == Splitting a Stream
98-- A 'Fold' can be applied repeatedly on a stream to transform it to a stream
99-- of fold results. To split a stream on newlines:
101-- >>> f = Fold.takeEndBy (== '\n') Fold.toList
102-- >>> Stream.fold Fold.toList $ Stream.foldMany f $ Stream.fromList "Hello there!\nHow are you\n"
103-- ["Hello there!\n","How are you\n"]
105-- Similarly, we can split the input of a fold too:
107-- >>> Stream.fold (Fold.many f Fold.toList) $ Stream.fromList "Hello there!\nHow are you\n"
108-- ["Hello there!\n","How are you\n"]
110-- == Folds vs. Streams
112-- We can often use streams or folds to achieve the same goal. However, streams
113-- are more efficient in composition of producers (e.g.
114-- 'Data.Stream.append' or 'Data.Stream.mergeBy') whereas folds are
115-- more efficient in composition of consumers (e.g. 'splitWith', 'partition'
118-- Streams are producers, transformations on streams happen on the output side:
122-- Stream.filter odd stream
124-- & Stream.fold Fold.sum
127-- >>> f $ Stream.fromList [1..100 :: Int]
130-- Folds are stream consumers with an input stream and an output value, stream
131-- transformations on folds happen on the input side:
140-- >>> Stream.fold f $ Stream.fromList [1..100 :: Int]
143-- Notice the similiarity in the definition of @f@ in both cases, the only
144-- difference is the composition by @&@ vs @$@ and the use @lmap@ vs @map@, the
145-- difference is due to output vs input side transformations.
147-- == Fusion Limitations
149-- Folds support stream fusion for generating loops comparable to the speed of
150-- C. However, it has some limitations. For fusion to work, the folds must be
151-- inlined, folds must be statically known and not generated dynamically, folds
152-- should not be passed recursively.
154-- Another limitation is due to the quadratic complexity causing slowdown when
155-- too many nested compositions are used. Especially, the performance of the
156-- Applicative instance and splitting operations (e.g. 'splitWith') degrades
157-- quadratically (O(n^2)) when combined @n@ times, roughly 8 or less sequenced
158-- operations are fine. For these cases folds can be converted to parsers and
159-- then used as ParserK.
161-- == Experimental APIs
163-- Please refer to "Streamly.Internal.Data.Fold" for more functions that have
164-- not yet been released.
166module Streamly.Data.Fold
169 -- | To execute the code examples provided in this module in ghci, please
170 -- run the following commands first.
176 -- XXX Should we have a stream returning function in fold module?
193 -- | Folds that never terminate, these folds are much like strict left
194 -- folds. 'mconcat' is the fundamental accumulator. All other accumulators
195 -- can be expressed in terms of 'mconcat' using a suitable Monoid. Instead
196 -- of writing folds we could write Monoids and turn them into folds.
215 , rollingHashWithSalt
224 -- ** Non-Empty Accumulators
225 -- | Accumulators that do not have a default value, therefore, return
226 -- 'Nothing' on an empty stream.
233 -- ** Filtering Scanners
234 -- | Accumulators that are usually run as a scan using the 'scanMaybe'
244 -- ** Terminating Folds
264 -- * Incremental builders
265 -- | Mutable arrays ("Streamly.Data.MutArray") are basic builders. You can
266 -- use the 'Streamly.Data.MutArray.snoc' or
267 -- 'Streamly.Data.MutArray.writeAppend' operations to incrementally build
268 -- mutable arrays. The 'addOne' and 'addStream' combinators can be used to
269 -- incrementally build any type of structure using a fold, including arrays
270 -- or a stream of arrays.
272 -- Use pinned arrays if you are going to use the data for IO.
274 -- XXX should rename to "extract". can use "Fold.drive Stream.nil" instead,
280 -- XXX Can we use something like concatEffect to implement snocM?
288 -- | Combinators are modifiers of folds. In the type @Fold m a b@, @a@ is
289 -- the input type and @b@ is the output type. Transformations can be
290 -- applied either on the input side (contravariant) or on the output side
291 -- (covariant). Therefore, combinators are of one of the following general
294 -- * @... -> Fold m a b -> Fold m c b@ (input transformation)
295 -- * @... -> Fold m a b -> Fold m a c@ (output transformation)
297 -- The input side transformations are more interesting for folds. Most of
298 -- the following sections describe the input transformation operations on a
299 -- fold. When an operation makes sense on both input and output side we use
300 -- the prefix @l@ (for left) for input side operations and the prefix @r@
301 -- (for right) for output side operations.
303 -- ** Mapping on output
304 -- | The 'Functor' instance of a fold maps on the output of the fold:
306 -- >>> Stream.fold (fmap show Fold.sum) (Stream.enumerateFromTo 1 100)
311 -- ** Mapping on Input
315 -- ** Scanning and Filtering
322 -- -- ** Mapping Filters
341 -- ** Parallel Distribution
342 -- | For applicative composition using distribution see
343 -- "Streamly.Internal.Data.Fold.Tee".
352 -- | Direct items in the input stream to different folds using a binary
361 -- ** Key-value Collectors
367 -- ** Key-value Scanners
379 -- * Transforming the Monad
397 hiding (Foldable(..), filter, drop, dropWhile, take, takeWhile, zipWith,
398 map, mapM_, sequence, all, any,
399 notElem, head, last, tail,
400 reverse, iterate, init, and, or, lookup, (!!),
401 scanl, scanl1, replicate, concatMap, mconcat, unzip,
402 span, splitAt, break, mapM, maybe)
404import Streamly.Internal.Data.Fold
406#include "DocTestDataFold.hs"
408--------------------------------------------------------------------------------
410--------------------------------------------------------------------------------
412{-# DEPRECATED chunksOf "Please use 'groupsOf' instead" #-}
413{-# INLINE chunksOf #-}
414chunksOf :: Monad m => Int -> Fold m a b -> Fold m b c -> Fold m a c
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