1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE ExistentialQuantification #-}
4{-# LANGUAGE FlexibleContexts #-}
5{-# LANGUAGE RankNTypes #-}
6{-# LANGUAGE RecordWildCards #-}
7{-# LANGUAGE ScopedTypeVariables #-}
10-- Module : Streamly.Fold
11-- Copyright : (c) 2019 Composewell Technologies
12-- (c) 2013 Gabriel Gonzalez
14-- Maintainer : harendra.kumar@gmail.com
15-- Stability : experimental
18-- A left fold consumes a stream and reduces it to a single value. The fold
19-- operations in "Streamly.Prelude" cannot be combined such that multiple of
20-- them can run on the same stream. This module provides a 'Fold' type that
21-- represents a left fold. Multiple such folds can be combined using
22-- combinators; a stream can then be supplied to the combined fold and it would
23-- distribute the input to constituent folds according to the composition.
24-- For example, an applicative composition distributes the same input to
25-- the constituent folds and then combines the fold outputs. Similarly, a
26-- partitioning combinator can divide the input among constituent folds.
27-- All the combinators in this module are of true streaming nature, stream
28-- elements are not unnecessarily buffered in memory, guaranteeing a constant
31-- Consider this module as the consumer side dual of the "Streamly.Prelude"
32-- module. "Streamly.Prelude" provides combinators that can combine stream
33-- sources in interesting ways whereas this module provides combinators that
34-- combine stream consumers in interesting ways. In other words,
35-- "Streamly.Prelude" provides stream merging capabilities while
36-- "Streamly.Fold" provides stream splitting capabilities.
38-- > import qualified Streamly.Fold as FL
40-- Also see the "Streamly.Sink" module that provides specialized left folds
41-- that discard the outputs.
43-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
49 -- A 'Fold' can be run over a stream using the 'runFold' combinator in
50 -- "Streamly.Prelude":
52 -- >>> S.runFold FL.sum (S.enumerateFromTo 1 100)
76 -- ** Full Folds (Monoidal)
81 -- ** Full Folds (To Containers)
82 -- | Avoid using these folds in scalable or performance critical
83 -- applications, they buffer all the input in GC memory which can be
84 -- detrimental to performance if the input is large.
86 -- , toStream -- experimental
87 -- , toStreamRev -- experimental
90 -- , toListRev -- experimental
107 -- XXX these are slower than right folds even when full input is used
114 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
115 -- output side, folds have an input side as well as an output side. In the
116 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
117 -- Transformations can be applied either on the input side or on the output
118 -- side. The 'Functor' instance of a fold maps on the output of the fold:
120 -- >>> S.runFold (fmap show FL.sum) (S.enumerateFromTo 1 100)
123 -- However, the input side or contravariant transformations are more
124 -- interesting for folds. The following sections describe the input
125 -- transformation operations on a fold. The names of the operations are
126 -- consistent with their covariant counterparts in "Streamly.Prelude", the
127 -- only difference is that they are prefixed with 'l' which stands for
128 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
129 -- the type variable @a@ is on the left side.
131 -- ** Covariant Operations
148 -- ** Mapping Filters
152 -- ** Scanning Filters
157 -- | Insertion adds more elements to the stream.
180 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
181 -- of the stream to each fold and combines the results using a function.
185 -- |-------Fold m a b--------|
186 -- ---stream m a---| |---m (b,c,...)
187 -- |-------Fold m a c--------|
192 -- To compute the average of numbers in a stream without going throught he
195 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
196 -- >>> S.runFold avg (S.enumerateFromTo 1.0 100.0)
199 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
200 -- the input to both the folds and combines the outputs using Monoid or
201 -- Semigroup instances of the output types:
203 -- >>> import Data.Monoid (Sum)
204 -- >>> S.runFold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
205 -- Just (Sum {getSum = 101.0})
207 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
214 -- Direct items in the input stream to different folds using a binary
222 -- | Direct values in the input stream to different folds using an n-ary
231 -- | In an input stream of key value pairs fold values for different keys
232 -- in individual output buckets using the given fold.
239 -- These can be expressed using lmap/lmapM and unzip
246 -- , duplicate -- experimental
250import Control.Monad (void)
251import Data.Map.Strict (Map)
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 qualified Data.Map.Strict as Map
262import qualified Prelude
264import Streamly.Fold.Types (Fold(..), lmap)
265import Streamly.Pipe.Types (Pipe (..), PipeState(..))
266import Streamly.Strict
268import qualified Streamly.Pipe.Types as Pipe
270------------------------------------------------------------------------------
271-- Transformations on fold inputs
272------------------------------------------------------------------------------
274-- | Flatten the monadic output of a fold to pure output.
277{-# INLINE sequence #-}
278sequence :: Monad m => Fold m a (m b) -> Fold m a b
279sequence (Fold step initial extract) = Fold step initial extract'
285-- | Map a monadic function on the output of a fold.
289mapM :: Monad m => (b -> m c) -> Fold m a b -> Fold m a c
290mapM f = sequence . fmap f
292------------------------------------------------------------------------------
293-- Transformations on fold inputs
294------------------------------------------------------------------------------
298-- | Apply a transformation on a 'Fold' using a 'Pipe'.
301{-# INLINE _transform #-}
302_transform :: Monad m => Pipe m a b -> Fold m b c -> Fold m a c
303_transform (Pipe pstep1 pstep2 pinitial) (Fold fstep finitial fextract) =
304 Fold step initial extract
308 initial = Tuple' <$> return pinitial <*> finitial
309 step (Tuple' ps fs) x = do
315 go acc (Pipe.Yield b (Consume ps')) = do
317 return (Tuple' ps' acc')
319 go acc (Pipe.Yield b (Produce ps')) = do
324 go acc (Pipe.Continue (Consume ps')) = return (Tuple' ps' acc)
326 go acc (Pipe.Continue (Produce ps')) = do
330 extract (Tuple' _ fs) = fextract fs
332------------------------------------------------------------------------------
334------------------------------------------------------------------------------
336-- | @_Fold1 step@ returns a new 'Fold' using just a step function that has the
337-- same type for the accumulator and the element. The result type is the
338-- accumulator type wrapped in 'Maybe'. The initial accumulator is retrieved
339-- from the 'Foldable', the result is 'None' for empty containers.
340{-# INLINABLE _Fold1 #-}
341_Fold1 :: Monad m => (a -> a -> a) -> Fold m a (Maybe a)
342_Fold1 step = Fold step_ (return Nothing') fromStrictMaybe
344 step_ mx a = return $ Just' $
349------------------------------------------------------------------------------
351------------------------------------------------------------------------------
353------------------------------------------------------------------------------
355------------------------------------------------------------------------------
357-- | A fold that drains all its input, running the effects and discarding the
361{-# INLINABLE drain #-}
362drain :: Monad m => Fold m a ()
363drain = Fold step begin done
370-- > drainBy f = lmapM f drain
372-- Drain all input after passing it through a monadic function. This is the
373-- dual of mapM_ on stream producers.
376{-# INLINABLE drainBy #-}
377drainBy :: Monad m => (a -> m b) -> Fold m a ()
378drainBy f = Fold (const (void . f)) (return ()) return
380-- | Extract the last element of the input stream, if any.
383{-# INLINABLE last #-}
384last :: Monad m => Fold m a (Maybe a)
385last = _Fold1 (flip const)
387------------------------------------------------------------------------------
389------------------------------------------------------------------------------
391-- | Like 'length', except with a more general 'Num' return value
394{-# INLINABLE genericLength #-}
395genericLength :: (Monad m, Num b) => Fold m a b
396genericLength = Fold (\n _ -> return $ n + 1) (return 0) return
398-- | Determine the length of the input stream.
401{-# INLINABLE length #-}
402length :: Monad m => Fold m a Int
403length = genericLength
405-- | Determine the sum of all elements of a stream of numbers. Returns additive
406-- identity (@0@) when the stream is empty. Note that this is not numerically
407-- stable for floating point numbers.
411sum :: (Monad m, Num a) => Fold m a a
412sum = Fold (\x a -> return $ x + a) (return 0) return
414-- | Determine the product of all elements of a stream of numbers. Returns
415-- multiplicative identity (@1@) when the stream is empty.
418{-# INLINABLE product #-}
419product :: (Monad m, Num a) => Fold m a a
420product = Fold (\x a -> return $ x * a) (return 1) return
422------------------------------------------------------------------------------
424------------------------------------------------------------------------------
426-- | Determine the maximum element in a stream using the supplied comparison
430{-# INLINABLE maximumBy #-}
431maximumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
432maximumBy cmp = _Fold1 max'
434 max' x y = case cmp x y of
440-- maximum = 'maximumBy' compare
443-- Determine the maximum element in a stream.
446{-# INLINABLE maximum #-}
447maximum :: (Monad m, Ord a) => Fold m a (Maybe a)
450-- | Computes the minimum element with respect to the given comparison function
453{-# INLINABLE minimumBy #-}
454minimumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
455minimumBy cmp = _Fold1 min'
457 min' x y = case cmp x y of
461-- | Determine the minimum element in a stream using the supplied comparison
465{-# INLINABLE minimum #-}
466minimum :: (Monad m, Ord a) => Fold m a (Maybe a)
469------------------------------------------------------------------------------
470-- To Summary (Statistical)
471------------------------------------------------------------------------------
473-- | Compute a numerically stable arithmetic mean of all elements in the input
477{-# INLINABLE mean #-}
478mean :: (Monad m, Fractional a) => Fold m a a
479mean = Fold step (return begin) (return . done)
482 step (Tuple' x n) y = return $
484 in Tuple' (x + (y - x) / n') n'
485 done (Tuple' x _) = x
487-- | Compute a numerically stable (population) variance over all elements in
491{-# INLINABLE variance #-}
492variance :: (Monad m, Fractional a) => Fold m a a
493variance = Fold step (return begin) (return . done)
495 begin = Tuple3' 0 0 0
497 step (Tuple3' n mean_ m2) x = return $ Tuple3' n' mean' m2'
500 mean' = (n * mean_ + x) / (n + 1)
502 m2' = m2 + delta * delta * n / (n + 1)
504 done (Tuple3' n _ m2) = m2 / n
506-- | Compute a numerically stable (population) standard deviation over all
507-- elements in the input stream.
510{-# INLINABLE stdDev #-}
511stdDev :: (Monad m, Floating a) => Fold m a a
512stdDev = sqrt variance
514------------------------------------------------------------------------------
515-- Monoidal left folds
516------------------------------------------------------------------------------
518-- | Fold an input stream consisting of monoidal elements using 'mappend'
521-- > S.runFold FL.mconcat (S.map Sum $ S.enumerateFromTo 1 10)
524{-# INLINABLE mconcat #-}
525mconcat :: (Monad m, Monoid a) => Fold m a a
526mconcat = Fold (\x a -> return $ mappend x a) (return mempty) return
529-- > foldMap f = map f mconcat
531-- Make a fold from a pure function that folds the output of the function
532-- using 'mappend' and 'mempty'.
534-- > S.runFold (FL.foldMap Sum) $ S.enumerateFromTo 1 10
537{-# INLINABLE foldMap #-}
538foldMap :: (Monad m, Monoid b) => (a -> b) -> Fold m a b
539foldMap f = lmap f mconcat
542-- > foldMapM f = mapM f mconcat
544-- Make a fold from a monadic function that folds the output of the function
545-- using 'mappend' and 'mempty'.
547-- > S.runFold (FL.foldMapM (return . Sum)) $ S.enumerateFromTo 1 10
550{-# INLINABLE foldMapM #-}
551foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b
552foldMapM act = Fold step begin done
555 begin = return mempty
558 return $! mappend m m'
560------------------------------------------------------------------------------
562------------------------------------------------------------------------------
564-- | Folds the input stream to a list.
566-- /Warning!/ working on large lists accumulated as buffers in memory could be
567-- very inefficient, consider using "Streamly.Array" instead.
571-- id . (x1 :) . (x2 :) . (x3 :) . ... . (xn :) $ []
572{-# INLINABLE toList #-}
573toList :: Monad m => Fold m a [a]
574toList = Fold (\f x -> return $ f . (x :))
578-- This is more efficient than 'toList'. toList is exactly the same as
579-- reversing the list after toListRev.
581-- | Buffers the input stream to a list in the reverse order of the input.
583-- /Warning!/ working on large lists accumulated as buffers in memory could be
584-- very inefficient, consider using "Streamly.Array" instead.
588-- xn : ... : x2 : x1 : []
589{-# INLINABLE _toListRev #-}
590_toListRev :: Monad m => Fold m a [a]
591_toListRev = Fold (\xs x -> return $ x:xs) (return []) return
593------------------------------------------------------------------------------
595------------------------------------------------------------------------------
597------------------------------------------------------------------------------
599------------------------------------------------------------------------------
601-- | Like 'index', except with a more general 'Integral' argument
604{-# INLINABLE genericIndex #-}
605genericIndex :: (Integral i, Monad m) => i -> Fold m a (Maybe a)
606genericIndex i = Fold step (return $ Left' 0) done
619-- | Lookup the element at the given index.
622{-# INLINABLE index #-}
623index :: Monad m => Int -> Fold m a (Maybe a)
626-- | Extract the first element of the stream, if any.
629{-# INLINABLE head #-}
630head :: Monad m => Fold m a (Maybe a)
633-- | Returns the first element that satisfies the given predicate.
636{-# INLINABLE find #-}
637find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
638find predicate = Fold step (return Nothing') fromStrictMaybe
642 Nothing' -> if predicate a
647-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
648-- first pair where the key equals the given value @a@.
651{-# INLINABLE lookup #-}
652lookup :: (Eq a, Monad m) => a -> Fold m (a,b) (Maybe b)
653lookup a0 = Fold step (return Nothing') fromStrictMaybe
655 step x (a,b) = return $
657 Nothing' -> if a == a0
662-- | Convert strict 'Either'' to lazy 'Maybe'
663{-# INLINABLE hush #-}
664hush :: Either' a b -> Maybe b
665hush (Left' _) = Nothing
666hush (Right' b) = Just b
668-- | Returns the first index that satisfies the given predicate.
671{-# INLINABLE findIndex #-}
672findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
673findIndex predicate = Fold step (return $ Left' 0) (return . hush)
683-- | Returns the first index where a given value is found in the stream.
686{-# INLINABLE elemIndex #-}
687elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)
688elemIndex a = findIndex (a ==)
690------------------------------------------------------------------------------
692------------------------------------------------------------------------------
694-- | Return 'True' if the input stream is empty.
697{-# INLINABLE null #-}
698null :: Monad m => Fold m a Bool
699null = Fold (\_ _ -> return False) (return True) return
702-- > any p = lmap p or
704-- | Returns 'True' if any of the elements of a stream satisfies a predicate.
708any :: Monad m => (a -> Bool) -> Fold m a Bool
709any predicate = Fold (\x a -> return $ x || predicate a) (return False) return
711-- | Return 'True' if the given element is present in the stream.
714{-# INLINABLE elem #-}
715elem :: (Eq a, Monad m) => a -> Fold m a Bool
719-- > all p = lmap p and
721-- | Returns 'True' if all elements of a stream satisfy a predicate.
725all :: Monad m => (a -> Bool) -> Fold m a Bool
726all predicate = Fold (\x a -> return $ x && predicate a) (return True) return
728-- | Returns 'True' if the given element is not present in the stream.
731{-# INLINABLE notElem #-}
732notElem :: (Eq a, Monad m) => a -> Fold m a Bool
733notElem a = all (a /=)
735-- | Returns 'True' if all elements are 'True', 'False' otherwise
739and :: Monad m => Fold m Bool Bool
740and = Fold (\x a -> return $ x && a) (return True) return
742-- | Returns 'True' if any element is 'True', 'False' otherwise
746or :: Monad m => Fold m Bool Bool
747or = Fold (\x a -> return $ x || a) (return False) return
749------------------------------------------------------------------------------
751------------------------------------------------------------------------------
753-- | Distribute one copy of the stream to each fold and zip the results.
756-- |-------Fold m a b--------|
757-- ---stream m a---| |---m (b,c)
758-- |-------Fold m a c--------|
760-- >>> S.runFold (FL.tee FL.sum FL.length) (S.enumerateFromTo 1.0 100.0)
765tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b,c)
766tee f1 f2 = (,) <$> f1 <*> f2
768{-# INLINE foldNil #-}
769foldNil :: Monad m => Fold m a [b]
770foldNil = Fold step begin done where
775{-# INLINE foldCons #-}
776foldCons :: Monad m => Fold m a b -> Fold m a [b] -> Fold m a [b]
777foldCons (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
782 begin = Tuple' <$> beginL <*> beginR
783 step (Tuple' xL xR) a = Tuple' <$> stepL xL a <*> stepR xR a
784 done (Tuple' xL xR) = (:) <$> (doneL xL) <*> (doneR xR)
786-- XXX use "List" instead of "[]"?, use Array for output to scale it to a large
787-- number of consumers? For polymorphic case a vector could be helpful. For
788-- Storables we can use arrays. Will need separate APIs for those.
790-- | Distribute one copy of the stream to each fold and collect the results in
795-- |-------Fold m a b--------|
796-- ---stream m a---| |---m [b]
797-- |-------Fold m a b--------|
802-- >>> S.runFold (FL.distribute [FL.sum, FL.length]) (S.enumerateFromTo 1 5)
805-- This is the consumer side dual of the producer side 'sequence' operation.
808{-# INLINE distribute #-}
809distribute :: Monad m => [Fold m a b] -> Fold m a [b]
810distribute [] = foldNil
811distribute (x:xs) = foldCons x (distribute xs)
813------------------------------------------------------------------------------
815------------------------------------------------------------------------------
817-- | Partition the input over two folds using an 'Either' partitioning
822-- |-------Fold b x--------|
823-- -----stream m a --> (Either b c)----| |----(x,y)
824-- |-------Fold c y--------|
827-- Send input to either fold randomly:
829-- >>> import System.Random (randomIO)
830-- >>> randomly a = randomIO >>= \x -> return $ if x then Left a else Right a
831-- >>> S.runFold (FL.partitionByM randomly FL.length FL.length) (S.enumerateFromTo 1 100)
834-- Send input to the two folds in a proportion of 2:1:
837-- import Data.IORef (newIORef, readIORef, writeIORef)
838-- proportionately m n = do
839-- ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
842-- writeIORef ref $ tail r
846-- f <- proportionately 2 1
847-- r <- S.runFold (FL.partitionByM f FL.length FL.length) (S.enumerateFromTo (1 :: Int) 100)
854-- This is the consumer side dual of the producer side 'mergeBy' operation.
857{-# INLINE partitionByM #-}
858partitionByM :: Monad m
859 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
860partitionByM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
866 begin = Tuple' <$> beginL <*> beginR
867 step (Tuple' xL xR) a = do
870 Left b -> Tuple' <$> stepL xL b <*> return xR
871 Right c -> Tuple' <$> return xL <*> stepR xR c
872 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
874-- Note: we could use (a -> Bool) instead of (a -> Either b c), but the latter
875-- makes the signature clearer as to which case belongs to which fold.
876-- XXX need to check the performance in both cases.
878-- | Same as 'partitionByM' but with a pure partition function.
880-- Count even and odd numbers in a stream:
883-- >>> let f = FL.partitionBy (\\n -> if even n then Left n else Right n)
884-- (fmap (("Even " ++) . show) FL.length)
885-- (fmap (("Odd " ++) . show) FL.length)
886-- in S.runFold f (S.enumerateFromTo 1 100)
887-- ("Even 50","Odd 50")
891{-# INLINE partitionBy #-}
892partitionBy :: Monad m
893 => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
894partitionBy f = partitionByM (return . f)
896-- | Compose two folds such that the combined fold accepts a stream of 'Either'
897-- and routes the 'Left' values to the first fold and 'Right' values to the
900-- > partition = partitionBy id
903{-# INLINE partition #-}
905 => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)
906partition = partitionBy id
909-- | Send one item to each fold in a round-robin fashion. This is the consumer
910-- side dual of producer side 'mergeN' operation.
912-- partitionN :: Monad m => [Fold m a b] -> Fold m a [b]
913-- partitionN fs = Fold step begin done
916-- TODO Demultiplex an input element into a number of typed variants. We want
917-- to statically restrict the target values within a set of predefined types,
918-- an enumeration of a GADT. We also want to make sure that the Map contains
919-- only those types and the full set of those types.
921-- TODO Instead of the input Map it should probably be a lookup-table using an
922-- array and not in GC memory. The same applies to the output Map as well.
923-- However, that would only be helpful if we have a very large data structure,
924-- need to measure and see how it scales.
926-- This is the consumer side dual of the producer side 'mux' operation (XXX to
929-- | Split the input stream based on a key field and fold each split using a
930-- specific fold collecting the results in a map from the keys to the results.
931-- Useful for cases like protocol handlers to handle different type of packets
932-- using different handlers.
937-- -----stream m a-----Map-----|
944{-# INLINE demuxWith #-}
945demuxWith :: (Monad m, Ord k)
946 => (a -> k) -> Map k (Fold m a b) -> Fold m a (Map k b)
947demuxWith f kv = Fold step initial extract
953 -- XXX should we raise an exception in Nothing case?
954 -- Ideally we should enforce that it is a total map over k so that look
956 -- XXX we could use a monadic update function for a single lookup and
957 -- update in the map.
959 in case Map.lookup k mp of
961 Just (Fold step' acc extract') -> do
962 !r <- acc >>= \x -> step' x a
963 return $ Map.insert k (Fold step' (return r) extract') mp
964 extract = Prelude.mapM (\(Fold _ acc e) -> acc >>= e)
966-- | Fold a stream of key value pairs using a map of specific folds for each
967-- key into a map from keys to the results of fold outputs of the corresponding
971-- > let table = Data.Map.fromList [(\"SUM", FL.sum), (\"PRODUCT", FL.product)]
972-- input = S.fromList [(\"SUM",1),(\"PRODUCT",2),(\"SUM",3),(\"PRODUCT",4)]
973-- in S.runFold (FL.demux table) input
980demux :: (Monad m, Ord k)
981 => Map k (Fold m a b) -> Fold m (k, a) (Map k b)
982demux fs = demuxWith fst (Map.map (lmap snd) fs)
984-- | Split the input stream based on a key field and fold each split using a
985-- specific fold without collecting the results. Useful for cases like protocol
986-- handlers to handle different type of packets.
990-- |-------Fold m a ()
991-- -----stream m a-----Map-----|
992-- |-------Fold m a ()
1000-- demuxWith_ can be slightly faster than demuxWith because we do not need to
1001-- update the Map in this case. This may be significant only if the map is
1003{-# INLINE demuxWith_ #-}
1004demuxWith_ :: (Monad m, Ord k)
1005 => (a -> k) -> Map k (Fold m a b) -> Fold m a ()
1006demuxWith_ f kv = Fold step initial extract
1011 Prelude.mapM (\(Fold s i e) ->
1012 i >>= \r -> return (Fold s (return r) e)) kv
1014 -- XXX should we raise an exception in Nothing case?
1015 -- Ideally we should enforce that it is a total map over k so that look
1017 case Map.lookup (f a) mp of
1018 Nothing -> return mp
1019 Just (Fold step' acc _) -> do
1020 _ <- acc >>= \x -> step' x a
1022 extract mp = Prelude.mapM (\(Fold _ acc e) -> acc >>= e) mp >> return ()
1024-- | Given a stream of key value pairs and a map from keys to folds, fold the
1025-- values for each key using the corresponding folds, discarding the outputs.
1028-- > let prn = FL.drainBy print
1029-- > let table = Data.Map.fromList [(\"ONE", prn), (\"TWO", prn)]
1030-- input = S.fromList [(\"ONE",1),(\"TWO",2)]
1031-- in S.runFold (FL.demux_ table) input
1037{-# INLINE demux_ #-}
1038demux_ :: (Monad m, Ord k) => Map k (Fold m a ()) -> Fold m (k, a) ()
1039demux_ fs = demuxWith_ fst (Map.map (lmap snd) fs)
1041-- TODO If the data is large we may need a map/hashmap in pinned memory instead
1042-- of a regular Map. That may require a serializable constraint though. We can
1043-- have another API for that.
1045-- | Split the input stream based on a key field and fold each split using the
1046-- given fold. Useful for map/reduce, bucketizing the input in different bins
1047-- or for generating histograms.
1050-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1051-- in S.runFold (FL.classify FL.toListRev) input
1052-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1056{-# INLINE classifyWith #-}
1057classifyWith :: (Monad m, Ord k) => (a -> k) -> Fold m a b -> Fold m a (Map k b)
1058classifyWith f (Fold step initial extract) = Fold step' initial' extract'
1062 initial' = return Map.empty
1065 in case Map.lookup k kv of
1069 return $ Map.insert k r kv
1072 return $ Map.insert k r kv
1073 extract' = Prelude.mapM extract
1075-- | Given an input stream of key value pairs and a fold for values, fold all
1076-- the values belonging to each key. Useful for map/reduce, bucketizing the
1077-- input in different bins or for generating histograms.
1080-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1081-- in S.runFold (FL.classify FL.toListRev) input
1082-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1089-- > classify fld = classifyWith fst (lmap snd fld)
1091{-# INLINE classify #-}
1092classify :: (Monad m, Ord k) => Fold m a b -> Fold m (k, a) (Map k b)
1093classify fld = classifyWith fst (lmap snd fld)
1095------------------------------------------------------------------------------
1097------------------------------------------------------------------------------
1099-- | Like 'unzipWith' but with a monadic splitter function.
1102{-# INLINE unzipWithM #-}
1103unzipWithM :: Monad m
1104 => (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1105unzipWithM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
1106 Fold step begin done
1110 step (Tuple' xL xR) a = do
1112 Tuple' <$> stepL xL b <*> stepR xR c
1113 begin = Tuple' <$> beginL <*> beginR
1114 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
1116-- | Split elements in the input stream into two parts using a pure splitter
1117-- function, direct each part to a different fold and zip the results.
1120{-# INLINE unzipWith #-}
1122 => (a -> (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1123unzipWith f = unzipWithM (return . f)
1125-- | Send the elements of tuples in a stream of tuples through two different
1130-- |-------Fold m a x--------|
1131-- ---------stream of (a,b)--| |----m (x,y)
1132-- |-------Fold m b y--------|
1136-- This is the consumer side dual of the producer side 'zip' operation.
1140unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a,b) (x,y)
1143------------------------------------------------------------------------------
1145------------------------------------------------------------------------------
1148-- All the stream flattening transformations can also be applied to a fold
1151-- | This can be used to apply all the stream generation operations on folds.
1152lconcatMap ::(IsStream t, Monad m) => (a -> t m b)
1155lconcatMap s f1 f2 = undefined
1158-- All the grouping transformation that we apply to a stream can also be
1159-- applied to a fold input stream.
1162-- | Group the input stream into groups of elements between @low@ and @high@.
1163-- Collection starts in chunks of @low@ and then keeps doubling until we reach
1164-- @high@. Each chunk is folded using the provided fold function.
1166-- This could be useful, for example, when we are folding a stream of unknown
1167-- size to a stream of arrays and we want to minimize the number of
1172-- XXX we should be able to implement it with parsers/terminating folds.
1174{-# INLINE lchunksInRange #-}
1175lchunksInRange :: Monad m
1176 => Int -> Int -> Fold m a b -> Fold m b c -> Fold m a c
1177lchunksInRange low high (Fold step1 initial1 extract1)
1178 (Fold step2 initial2 extract2) = undefined
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