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
13-- Please refer to "Streamly.Internal.Data.Fold" for more functions that have
14-- not yet been released.
16module Streamly.Data.Fold
19 -- | To execute the code examples provided in this module in ghci, please
20 -- run the following commands first.
29 -- XXX Should we have a stream returning function in fold module?
46 -- | Folds that never terminate, these folds are much like strict left
47 -- folds. 'mconcat' is the fundamental accumulator. All other accumulators
48 -- can be expressed in terms of 'mconcat' using a suitable Monoid. Instead
49 -- of writing folds we could write Monoids and turn them into folds.
77 -- ** Non-Empty Accumulators
78 -- | Accumulators that do not have a default value, therefore, return
79 -- 'Nothing' on an empty stream.
86 -- ** Filtering Scanners
87 -- | Accumulators that are usually run as a scan using the 'scanMaybe'
97 -- ** Terminating Folds
117 -- * Incremental builders
118 -- | Mutable arrays ("Streamly.Data.MutArray") are basic builders. You can
119 -- use the 'Streamly.Data.MutArray.snoc' or
120 -- 'Streamly.Data.MutArray.writeAppend' operations to incrementally build
121 -- mutable arrays. The 'addOne' and 'addStream' combinators can be used to
122 -- incrementally build any type of structure using a fold, including arrays
123 -- or a stream of arrays.
125 -- Use pinned arrays if you are going to use the data for IO.
127 -- XXX should rename to "extract". can use "Fold.drive Stream.nil" instead,
133 -- XXX Can we use something like concatEffect to implement snocM?
141 -- | Combinators are modifiers of folds. In the type @Fold m a b@, @a@ is
142 -- the input type and @b@ is the output type. Transformations can be
143 -- applied either on the input side (contravariant) or on the output side
144 -- (covariant). Therefore, combinators are of one of the following general
147 -- * @... -> Fold m a b -> Fold m c b@ (input transformation)
148 -- * @... -> Fold m a b -> Fold m a c@ (output transformation)
150 -- The input side transformations are more interesting for folds. Most of
151 -- the following sections describe the input transformation operations on a
152 -- fold. When an operation makes sense on both input and output side we use
153 -- the prefix @l@ (for left) for input side operations and the prefix @r@
154 -- (for right) for output side operations.
156 -- ** Mapping on output
157 -- | The 'Functor' instance of a fold maps on the output of the fold:
159 -- >>> Stream.fold (fmap show Fold.sum) (Stream.enumerateFromTo 1 100)
164 -- ** Mapping on Input
168 -- ** Scanning and Filtering
175 -- -- ** Mapping Filters
194 -- ** Parallel Distribution
195 -- | For applicative composition using distribution see
196 -- "Streamly.Internal.Data.Fold.Tee".
205 -- | Direct items in the input stream to different folds using a binary
214 -- ** Key-value Collectors
220 -- ** Key-value Scanners
232 -- * Transforming the Monad
250 hiding (Foldable(..), filter, drop, dropWhile, take, takeWhile, zipWith,
251 map, mapM_, sequence, all, any,
252 notElem, head, last, tail,
253 reverse, iterate, init, and, or, lookup, (!!),
254 scanl, scanl1, replicate, concatMap, mconcat, unzip,
255 span, splitAt, break, mapM, maybe)
257import Streamly.Internal.Data.Fold
258import Streamly.Internal.Data.Fold.Container
260#include "DocTestDataFold.hs"
264-- A 'Fold' is a consumer of a stream of values. A fold driver (such as
265-- 'Streamly.Data.Stream.fold') initializes the fold @accumulator@, runs the
266-- fold @step@ function in a loop, processing the input stream one element at a
267-- time and accumulating the result. The loop continues until the fold
268-- terminates, at which point the accumulated result is returned.
270-- For example, a 'sum' Fold represents a stream consumer that adds the values
271-- in the input stream:
273-- >>> Stream.fold Fold.sum $ Stream.fromList [1..100]
276-- Conceptually, a 'Fold' is a data type that mimics a strict left fold
277-- ('Data.List.foldl'). The above example is similar to a left fold using
278-- @(+)@ as the step and @0@ as the initial value of the accumulator:
280-- >>> Data.List.foldl' (+) 0 [1..100]
283-- 'Fold's have an early termination capability e.g. the 'one' fold terminates
284-- after consuming one element:
286-- >>> Stream.fold Fold.one $ Stream.fromList [1..]
289-- The above example is similar to the following right fold:
291-- >>> Prelude.foldr (\x _ -> Just x) Nothing [1..]
294-- 'Fold's can be combined together using combinators. For example, to create a
295-- fold that sums first two elements in a stream:
297-- >>> sumTwo = Fold.take 2 Fold.sum
298-- >>> Stream.fold sumTwo $ Stream.fromList [1..100]
301-- Folds can be combined to run in parallel on the same input. For example, to
302-- compute the average of numbers in a stream without going through the stream
305-- >>> avg = Fold.teeWith (/) Fold.sum (fmap fromIntegral Fold.length)
306-- >>> Stream.fold avg $ Stream.fromList [1.0..100.0]
309-- Folds can be combined so as to partition the input stream over multiple
310-- folds. For example, to count even and odd numbers in a stream:
312-- >>> split n = if even n then Left n else Right n
313-- >>> stream = fmap split $ Stream.fromList [1..100]
314-- >>> countEven = fmap (("Even " ++) . show) Fold.length
315-- >>> countOdd = fmap (("Odd " ++) . show) Fold.length
316-- >>> f = Fold.partition countEven countOdd
317-- >>> Stream.fold f stream
318-- ("Even 50","Odd 50")
320-- Terminating folds can be combined to parse the stream serially such that the
321-- first fold consumes the input until it terminates and the second fold
322-- consumes the rest of the input until it terminates:
324-- >>> f = Fold.splitWith (,) (Fold.take 8 Fold.toList) (Fold.takeEndBy (== '\n') Fold.toList)
325-- >>> Stream.fold f $ Stream.fromList "header: hello\n"
326-- ("header: ","hello\n")
328-- A 'Fold' can be applied repeatedly on a stream to transform it to a stream
329-- of fold results. To split a stream on newlines:
331-- >>> f = Fold.takeEndBy (== '\n') Fold.toList
332-- >>> Stream.fold Fold.toList $ Stream.foldMany f $ Stream.fromList "Hello there!\nHow are you\n"
333-- ["Hello there!\n","How are you\n"]
335-- Similarly, we can split the input of a fold too:
337-- >>> Stream.fold (Fold.many f Fold.toList) $ Stream.fromList "Hello there!\nHow are you\n"
338-- ["Hello there!\n","How are you\n"]
340-- = Folds vs. Streams
342-- We can often use streams or folds to achieve the same goal. However, streams
343-- are more efficient in composition of producers (e.g.
344-- 'Data.Stream.append' or 'Data.Stream.mergeBy') whereas folds are
345-- more efficient in composition of consumers (e.g. 'splitWith', 'partition'
348-- Streams are producers, transformations on streams happen on the output side:
352-- Stream.filter odd stream
354-- & Stream.fold Fold.sum
357-- >>> f $ Stream.fromList [1..100 :: Int]
360-- Folds are stream consumers with an input stream and an output value, stream
361-- transformations on folds happen on the input side:
370-- >>> Stream.fold f $ Stream.fromList [1..100 :: Int]
373-- Notice the similiarity in the definition of @f@ in both cases, the only
374-- difference is the composition by @&@ vs @$@ and the use @lmap@ vs @map@, the
375-- difference is due to output vs input side transformations.
377--------------------------------------------------------------------------------
379--------------------------------------------------------------------------------
381{-# DEPRECATED chunksOf "Please use 'groupsOf' instead" #-}
382{-# INLINE chunksOf #-}
383chunksOf :: 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