git.iko.soy/streamly
on 0e98baf help sign in
streamly/src/Streamly/Data/Fold.hs
246 lines 7.1 kB history raw
1-- |
2-- Module : Streamly.Data.Fold
3-- Copyright : (c) 2019 Composewell Technologies
4-- License : BSD3
5-- Maintainer : harendra@composewell.com
6-- Stability : experimental
7-- Portability : GHC
8--
9-- A left fold consumes a stream and reduces it to a single value. The fold
10-- operations in "Streamly.Prelude" cannot be combined such that multiple of
11-- them can run on the same stream. This module provides a 'Fold' type that
12-- represents a left fold. Multiple such folds can be combined using
13-- combinators; a stream can then be supplied to the combined fold and it would
14-- distribute the input to constituent folds according to the composition.
15-- For example, an applicative composition distributes the same input to
16-- the constituent folds and then combines the fold outputs. Similarly, a
17-- partitioning combinator can divide the input among constituent folds.
18-- All the combinators in this module are of true streaming nature, stream
19-- elements are not unnecessarily buffered in memory, guaranteeing a constant
20-- memory consumption.
21--
22-- Consider this module as the consumer side dual of the "Streamly.Prelude"
23-- module. "Streamly.Prelude" provides combinators that can combine stream
24-- sources in interesting ways whereas this module provides combinators that
25-- combine stream consumers in interesting ways. In other words,
26-- "Streamly.Prelude" provides stream merging capabilities while
27-- "Streamly.Internal.Data.Fold" provides stream splitting capabilities.
28--
29-- > import qualified Streamly.Internal.Data.Fold as FL
31-- Also see the "Streamly.Internal.Data.Sink" module that provides specialized left folds
32-- that discard the outputs.
33--
34-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
36module Streamly.Data.Fold
37 (
38 -- * Fold Type
39 -- |
40 -- A 'Fold' can be run over a stream using the 'runFold' combinator in
41 -- "Streamly.Prelude":
42 --
43 -- >>> S.runFold FL.sum (S.enumerateFromTo 1 100)
44 -- 5050
46 Fold -- (..)
48 -- , tail
49 -- , init
51 -- ** Full Folds
52 , drain
53 , drainBy
54 , last
55 , length
56 , sum
57 , product
58 , maximumBy
59 , maximum
60 , minimumBy
61 , minimum
62 -- , the
63 , mean
64 , variance
65 , stdDev
67 -- ** Full Folds (Monoidal)
68 , mconcat
69 , foldMap
70 , foldMapM
72 -- ** Full Folds (To Containers)
73 -- | Avoid using these folds in scalable or performance critical
74 -- applications, they buffer all the input in GC memory which can be
75 -- detrimental to performance if the input is large.
77 , toList
79 -- ** Partial Folds
80 -- , drainN
81 -- , drainWhile
82 -- , lastN
83 -- , (!!)
84 -- , genericIndex
85 , index
86 , head
87 -- , findM
88 , find
89 , lookup
90 , findIndex
91 , elemIndex
92 , null
93 , elem
94 , notElem
95 -- XXX these are slower than right folds even when full input is used
96 , all
97 , any
98 , and
99 , or
101 -- * Transformations
102 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
103 -- output side, folds have an input side as well as an output side. In the
104 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
105 -- Transformations can be applied either on the input side or on the output
106 -- side. The 'Functor' instance of a fold maps on the output of the fold:
107 --
108 -- >>> S.runFold (fmap show FL.sum) (S.enumerateFromTo 1 100)
109 -- "5050"
110 --
111 -- However, the input side or contravariant transformations are more
112 -- interesting for folds. The following sections describe the input
113 -- transformation operations on a fold. The names of the operations are
114 -- consistent with their covariant counterparts in "Streamly.Prelude", the
115 -- only difference is that they are prefixed with 'l' which stands for
116 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
117 -- the type variable @a@ is on the left side.
119 -- ** Covariant Operations
120 , sequence
121 , mapM
123 -- ** Mapping
124 --, transform
125 -- , lmap
126 --, lsequence
127 -- , lmapM
129 -- -- ** Filtering
130 -- , lfilter
131 -- , lfilterM
132 -- , ldeleteBy
133 -- , luniq
135 {-
136 -- ** Mapping Filters
137 , lmapMaybe
138 , lmapMaybeM
140 -- ** Scanning Filters
141 , lfindIndices
142 , lelemIndices
144 -- ** Insertion
145 -- | Insertion adds more elements to the stream.
147 , linsertBy
148 , lintersperseM
150 -- ** Reordering
151 , lreverse
152 -}
154 {-
155 -- * Parsing
156 -- ** Trimming
157 , ltake
158 -- , lrunFor -- time
159 , ltakeWhile
160 , ltakeWhileM
161 , ldrop
162 , ldropWhile
163 , ldropWhileM
164 -}
166 -- * Distributing
167 -- |
168 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
169 -- of the stream to each fold and combines the results using a function.
170 --
171 -- @
172 --
173 -- |-------Fold m a b--------|
174 -- ---stream m a---| |---m (b,c,...)
175 -- |-------Fold m a c--------|
176 -- | |
177 -- ...
178 -- @
179 --
180 -- To compute the average of numbers in a stream without going throught he
181 -- stream twice:
182 --
183 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
184 -- >>> S.runFold avg (S.enumerateFromTo 1.0 100.0)
185 -- 50.5
186 --
187 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
188 -- the input to both the folds and combines the outputs using Monoid or
189 -- Semigroup instances of the output types:
190 --
191 -- >>> import Data.Monoid (Sum)
192 -- >>> S.runFold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
193 -- Just (Sum {getSum = 101.0})
194 --
195 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
197 , tee
198 , distribute
200 -- * Partitioning
201 -- |
202 -- Direct items in the input stream to different folds using a binary
203 -- fold selector.
205 -- , partitionByM
206 -- , partitionBy
207 , partition
209 -- * Demultiplexing
210 -- | Direct values in the input stream to different folds using an n-ary
211 -- fold selector.
213 , demux
214 -- , demuxWith
215 , demux_
216 -- , demuxWith_
218 -- * Classifying
219 -- | In an input stream of key value pairs fold values for different keys
220 -- in individual output buckets using the given fold.
222 , classify
223 -- , classifyWith
225 -- * Unzipping
226 , unzip
227 -- These can be expressed using lmap/lmapM and unzip
228 -- , unzipWith
229 -- , unzipWithM
231 -- -- * Nested Folds
232 -- , concatMap
233 -- , chunksOf
234 -- , duplicate -- experimental
235 )
236where
238import Prelude
239 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
240 foldl, map, mapM_, sequence, all, any, sum, product, elem,
241 notElem, maximum, minimum, head, last, tail, length, null,
242 reverse, iterate, init, and, or, lookup, foldr1, (!!),
243 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
244 span, splitAt, break, mapM)
246import Streamly.Internal.Data.Fold