1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE ExistentialQuantification #-}
4{-# LANGUAGE FlexibleContexts #-}
5{-# LANGUAGE RankNTypes #-}
6{-# LANGUAGE RecordWildCards #-}
7{-# LANGUAGE ScopedTypeVariables #-}
10-- Module : Streamly.Internal.Data.Fold
11-- Copyright : (c) 2019 Composewell Technologies
12-- (c) 2013 Gabriel Gonzalez
14-- Maintainer : harendra.kumar@gmail.com
15-- Stability : experimental
18-- Also see the "Streamly.Internal.Data.Sink" module that provides specialized left folds
19-- that discard the outputs.
21-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
23module Streamly.Internal.Data.Fold
27 -- A 'Fold' can be run over a stream using the 'runFold' combinator in
28 -- "Streamly.Prelude":
30 -- >>> S.runFold FL.sum (S.enumerateFromTo 1 100)
55 -- , rollingHashFirstN
58 -- ** Full Folds (Monoidal)
63 -- ** Full Folds (To Containers)
64 -- | Avoid using these folds in scalable or performance critical
65 -- applications, they buffer all the input in GC memory which can be
66 -- detrimental to performance if the input is large.
69 , toListRevF -- experimental
87 -- XXX these are slower than right folds even when full input is used
94 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
95 -- output side, folds have an input side as well as an output side. In the
96 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
97 -- Transformations can be applied either on the input side or on the output
98 -- side. The 'Functor' instance of a fold maps on the output of the fold:
100 -- >>> S.runFold (fmap show FL.sum) (S.enumerateFromTo 1 100)
103 -- However, the input side or contravariant transformations are more
104 -- interesting for folds. The following sections describe the input
105 -- transformation operations on a fold. The names of the operations are
106 -- consistent with their covariant counterparts in "Streamly.Prelude", the
107 -- only difference is that they are prefixed with 'l' which stands for
108 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
109 -- the type variable @a@ is on the left side.
111 -- ** Covariant Operations
128 -- ** Mapping Filters
132 -- ** Scanning Filters
137 -- | Insertion adds more elements to the stream.
163 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
164 -- of the stream to each fold and combines the results using a function.
168 -- |-------Fold m a b--------|
169 -- ---stream m a---| |---m (b,c,...)
170 -- |-------Fold m a c--------|
175 -- To compute the average of numbers in a stream without going throught he
178 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
179 -- >>> S.runFold avg (S.enumerateFromTo 1.0 100.0)
182 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
183 -- the input to both the folds and combines the outputs using Monoid or
184 -- Semigroup instances of the output types:
186 -- >>> import Data.Monoid (Sum)
187 -- >>> S.runFold (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
188 -- Just (Sum {getSum = 101.0})
190 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
197 -- Direct items in the input stream to different folds using a binary
205 -- | Direct values in the input stream to different folds using an n-ary
214 -- | In an input stream of key value pairs fold values for different keys
215 -- in individual output buckets using the given fold.
222 -- These can be expressed using lmap/lmapM and unzip
233 , duplicate -- experimental
237import Control.Monad (void)
238import Data.Map.Strict (Map)
241 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
242 foldl, map, mapM_, sequence, all, any, sum, product, elem,
243 notElem, maximum, minimum, head, last, tail, length, null,
244 reverse, iterate, init, and, or, lookup, foldr1, (!!),
245 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
246 span, splitAt, break, mapM)
248import qualified Data.Map.Strict as Map
249import qualified Prelude
251import Streamly.Internal.Data.Pipe.Types (Pipe (..), PipeState(..))
252import Streamly.Internal.Data.Fold.Types
253import Streamly.Internal.Data.Strict
255import qualified Streamly.Internal.Data.Pipe.Types as Pipe
257------------------------------------------------------------------------------
258-- Transformations on fold inputs
259------------------------------------------------------------------------------
261-- | Flatten the monadic output of a fold to pure output.
264{-# INLINE sequence #-}
265sequence :: Monad m => Fold m a (m b) -> Fold m a b
266sequence (Fold step initial extract) = Fold step initial extract'
272-- | Map a monadic function on the output of a fold.
276mapM :: Monad m => (b -> m c) -> Fold m a b -> Fold m a c
277mapM f = sequence . fmap f
279------------------------------------------------------------------------------
280-- Transformations on fold inputs
281------------------------------------------------------------------------------
285-- | Apply a transformation on a 'Fold' using a 'Pipe'.
288{-# INLINE transform #-}
289transform :: Monad m => Pipe m a b -> Fold m b c -> Fold m a c
290transform (Pipe pstep1 pstep2 pinitial) (Fold fstep finitial fextract) =
291 Fold step initial extract
295 initial = Tuple' <$> return pinitial <*> finitial
296 step (Tuple' ps fs) x = do
302 go acc (Pipe.Yield b (Consume ps')) = do
304 return (Tuple' ps' acc')
306 go acc (Pipe.Yield b (Produce ps')) = do
311 go acc (Pipe.Continue (Consume ps')) = return (Tuple' ps' acc)
313 go acc (Pipe.Continue (Produce ps')) = do
317 extract (Tuple' _ fs) = fextract fs
319------------------------------------------------------------------------------
321------------------------------------------------------------------------------
323-- | @_Fold1 step@ returns a new 'Fold' using just a step function that has the
324-- same type for the accumulator and the element. The result type is the
325-- accumulator type wrapped in 'Maybe'. The initial accumulator is retrieved
326-- from the 'Foldable', the result is 'None' for empty containers.
327{-# INLINABLE _Fold1 #-}
328_Fold1 :: Monad m => (a -> a -> a) -> Fold m a (Maybe a)
329_Fold1 step = Fold step_ (return Nothing') fromStrictMaybe
331 step_ mx a = return $ Just' $
336------------------------------------------------------------------------------
338------------------------------------------------------------------------------
340------------------------------------------------------------------------------
342------------------------------------------------------------------------------
344-- | A fold that drains all its input, running the effects and discarding the
348{-# INLINABLE drain #-}
349drain :: Monad m => Fold m a ()
350drain = Fold step begin done
357-- > drainBy f = lmapM f drain
359-- Drain all input after passing it through a monadic function. This is the
360-- dual of mapM_ on stream producers.
363{-# INLINABLE drainBy #-}
364drainBy :: Monad m => (a -> m b) -> Fold m a ()
365drainBy f = Fold (const (void . f)) (return ()) return
367-- | Extract the last element of the input stream, if any.
370{-# INLINABLE last #-}
371last :: Monad m => Fold m a (Maybe a)
372last = _Fold1 (flip const)
374------------------------------------------------------------------------------
376------------------------------------------------------------------------------
378-- | Like 'length', except with a more general 'Num' return value
381{-# INLINABLE genericLength #-}
382genericLength :: (Monad m, Num b) => Fold m a b
383genericLength = Fold (\n _ -> return $ n + 1) (return 0) return
385-- | Determine the length of the input stream.
388{-# INLINABLE length #-}
389length :: Monad m => Fold m a Int
390length = genericLength
392-- | Determine the sum of all elements of a stream of numbers. Returns additive
393-- identity (@0@) when the stream is empty. Note that this is not numerically
394-- stable for floating point numbers.
398sum :: (Monad m, Num a) => Fold m a a
399sum = Fold (\x a -> return $ x + a) (return 0) return
401-- | Determine the product of all elements of a stream of numbers. Returns
402-- multiplicative identity (@1@) when the stream is empty.
405{-# INLINABLE product #-}
406product :: (Monad m, Num a) => Fold m a a
407product = Fold (\x a -> return $ x * a) (return 1) return
409------------------------------------------------------------------------------
411------------------------------------------------------------------------------
413-- | Determine the maximum element in a stream using the supplied comparison
417{-# INLINABLE maximumBy #-}
418maximumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
419maximumBy cmp = _Fold1 max'
421 max' x y = case cmp x y of
427-- maximum = 'maximumBy' compare
430-- Determine the maximum element in a stream.
433{-# INLINABLE maximum #-}
434maximum :: (Monad m, Ord a) => Fold m a (Maybe a)
437-- | Computes the minimum element with respect to the given comparison function
440{-# INLINABLE minimumBy #-}
441minimumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
442minimumBy cmp = _Fold1 min'
444 min' x y = case cmp x y of
448-- | Determine the minimum element in a stream using the supplied comparison
452{-# INLINABLE minimum #-}
453minimum :: (Monad m, Ord a) => Fold m a (Maybe a)
456------------------------------------------------------------------------------
457-- To Summary (Statistical)
458------------------------------------------------------------------------------
460-- | Compute a numerically stable arithmetic mean of all elements in the input
464{-# INLINABLE mean #-}
465mean :: (Monad m, Fractional a) => Fold m a a
466mean = Fold step (return begin) (return . done)
469 step (Tuple' x n) y = return $
471 in Tuple' (x + (y - x) / n') n'
472 done (Tuple' x _) = x
474-- | Compute a numerically stable (population) variance over all elements in
478{-# INLINABLE variance #-}
479variance :: (Monad m, Fractional a) => Fold m a a
480variance = Fold step (return begin) (return . done)
482 begin = Tuple3' 0 0 0
484 step (Tuple3' n mean_ m2) x = return $ Tuple3' n' mean' m2'
487 mean' = (n * mean_ + x) / (n + 1)
489 m2' = m2 + delta * delta * n / (n + 1)
491 done (Tuple3' n _ m2) = m2 / n
493-- | Compute a numerically stable (population) standard deviation over all
494-- elements in the input stream.
497{-# INLINABLE stdDev #-}
498stdDev :: (Monad m, Floating a) => Fold m a a
499stdDev = sqrt variance
501-- | Compute an 'Int' sized polynomial rolling hash
503-- > H = salt * k ^ n + c1 * k ^ (n - 1) + c2 * k ^ (n - 2) + ... + cn * k ^ 0
505-- Where @c1@, @c2@, @cn@ are the elements in the input stream and @k@ is a
508-- This hash is often used in Rabin-Karp string search algorithm.
510-- See https://en.wikipedia.org/wiki/Rolling_hash
513{-# INLINABLE rollingHashWithSalt #-}
514rollingHashWithSalt :: (Monad m, Enum a) => Int -> Fold m a Int
515rollingHashWithSalt salt = Fold step initial extract
518 initial = return salt
519 step cksum a = return $ cksum * k + fromEnum a
522-- | A default salt used in the implementation of 'rollingHash'.
523{-# INLINE defaultSalt #-}
525#if WORD_SIZE_IN_BITS == 64
526defaultSalt = 0xdc36d1615b7400a4
528defaultSalt = 0x087fc72c
531-- | Compute an 'Int' sized polynomial rolling hash of a stream.
533-- > rollingHash = rollingHashWithSalt defaultSalt
536{-# INLINABLE rollingHash #-}
537rollingHash :: (Monad m, Enum a) => Fold m a Int
538rollingHash = rollingHashWithSalt defaultSalt
540------------------------------------------------------------------------------
541-- Monoidal left folds
542------------------------------------------------------------------------------
544-- | Fold an input stream consisting of monoidal elements using 'mappend'
547-- > S.runFold FL.mconcat (S.map Sum $ S.enumerateFromTo 1 10)
550{-# INLINABLE mconcat #-}
551mconcat :: (Monad m, Monoid a) => Fold m a a
552mconcat = Fold (\x a -> return $ mappend x a) (return mempty) return
555-- > foldMap f = map f mconcat
557-- Make a fold from a pure function that folds the output of the function
558-- using 'mappend' and 'mempty'.
560-- > S.runFold (FL.foldMap Sum) $ S.enumerateFromTo 1 10
563{-# INLINABLE foldMap #-}
564foldMap :: (Monad m, Monoid b) => (a -> b) -> Fold m a b
565foldMap f = lmap f mconcat
568-- > foldMapM f = mapM f mconcat
570-- Make a fold from a monadic function that folds the output of the function
571-- using 'mappend' and 'mempty'.
573-- > S.runFold (FL.foldMapM (return . Sum)) $ S.enumerateFromTo 1 10
576{-# INLINABLE foldMapM #-}
577foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b
578foldMapM act = Fold step begin done
581 begin = return mempty
584 return $! mappend m m'
586------------------------------------------------------------------------------
588------------------------------------------------------------------------------
590-- | Folds the input stream to a list.
592-- /Warning!/ working on large lists accumulated as buffers in memory could be
593-- very inefficient, consider using "Streamly.Array" instead.
597-- id . (x1 :) . (x2 :) . (x3 :) . ... . (xn :) $ []
598{-# INLINABLE toList #-}
599toList :: Monad m => Fold m a [a]
600toList = Fold (\f x -> return $ f . (x :))
604------------------------------------------------------------------------------
606------------------------------------------------------------------------------
608------------------------------------------------------------------------------
610------------------------------------------------------------------------------
612-- | Like 'index', except with a more general 'Integral' argument
615{-# INLINABLE genericIndex #-}
616genericIndex :: (Integral i, Monad m) => i -> Fold m a (Maybe a)
617genericIndex i = Fold step (return $ Left' 0) done
630-- | Lookup the element at the given index.
633{-# INLINABLE index #-}
634index :: Monad m => Int -> Fold m a (Maybe a)
637-- | Extract the first element of the stream, if any.
640{-# INLINABLE head #-}
641head :: Monad m => Fold m a (Maybe a)
644-- | Returns the first element that satisfies the given predicate.
647{-# INLINABLE find #-}
648find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
649find predicate = Fold step (return Nothing') fromStrictMaybe
653 Nothing' -> if predicate a
658-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
659-- first pair where the key equals the given value @a@.
662{-# INLINABLE lookup #-}
663lookup :: (Eq a, Monad m) => a -> Fold m (a,b) (Maybe b)
664lookup a0 = Fold step (return Nothing') fromStrictMaybe
666 step x (a,b) = return $
668 Nothing' -> if a == a0
673-- | Convert strict 'Either'' to lazy 'Maybe'
674{-# INLINABLE hush #-}
675hush :: Either' a b -> Maybe b
676hush (Left' _) = Nothing
677hush (Right' b) = Just b
679-- | Returns the first index that satisfies the given predicate.
682{-# INLINABLE findIndex #-}
683findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
684findIndex predicate = Fold step (return $ Left' 0) (return . hush)
694-- | Returns the first index where a given value is found in the stream.
697{-# INLINABLE elemIndex #-}
698elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)
699elemIndex a = findIndex (a ==)
701------------------------------------------------------------------------------
703------------------------------------------------------------------------------
705-- | Return 'True' if the input stream is empty.
708{-# INLINABLE null #-}
709null :: Monad m => Fold m a Bool
710null = Fold (\_ _ -> return False) (return True) return
713-- > any p = lmap p or
715-- | Returns 'True' if any of the elements of a stream satisfies a predicate.
719any :: Monad m => (a -> Bool) -> Fold m a Bool
720any predicate = Fold (\x a -> return $ x || predicate a) (return False) return
722-- | Return 'True' if the given element is present in the stream.
725{-# INLINABLE elem #-}
726elem :: (Eq a, Monad m) => a -> Fold m a Bool
730-- > all p = lmap p and
732-- | Returns 'True' if all elements of a stream satisfy a predicate.
736all :: Monad m => (a -> Bool) -> Fold m a Bool
737all predicate = Fold (\x a -> return $ x && predicate a) (return True) return
739-- | Returns 'True' if the given element is not present in the stream.
742{-# INLINABLE notElem #-}
743notElem :: (Eq a, Monad m) => a -> Fold m a Bool
744notElem a = all (a /=)
746-- | Returns 'True' if all elements are 'True', 'False' otherwise
750and :: Monad m => Fold m Bool Bool
751and = Fold (\x a -> return $ x && a) (return True) return
753-- | Returns 'True' if any element is 'True', 'False' otherwise
757or :: Monad m => Fold m Bool Bool
758or = Fold (\x a -> return $ x || a) (return False) return
760------------------------------------------------------------------------------
762------------------------------------------------------------------------------
764-- | Distribute one copy of the stream to each fold and zip the results.
767-- |-------Fold m a b--------|
768-- ---stream m a---| |---m (b,c)
769-- |-------Fold m a c--------|
771-- >>> S.runFold (FL.tee FL.sum FL.length) (S.enumerateFromTo 1.0 100.0)
776tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b,c)
777tee f1 f2 = (,) <$> f1 <*> f2
779{-# INLINE foldNil #-}
780foldNil :: Monad m => Fold m a [b]
781foldNil = Fold step begin done where
786{-# INLINE foldCons #-}
787foldCons :: Monad m => Fold m a b -> Fold m a [b] -> Fold m a [b]
788foldCons (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
793 begin = Tuple' <$> beginL <*> beginR
794 step (Tuple' xL xR) a = Tuple' <$> stepL xL a <*> stepR xR a
795 done (Tuple' xL xR) = (:) <$> (doneL xL) <*> (doneR xR)
797-- XXX use "List" instead of "[]"?, use Array for output to scale it to a large
798-- number of consumers? For polymorphic case a vector could be helpful. For
799-- Storables we can use arrays. Will need separate APIs for those.
801-- | Distribute one copy of the stream to each fold and collect the results in
806-- |-------Fold m a b--------|
807-- ---stream m a---| |---m [b]
808-- |-------Fold m a b--------|
813-- >>> S.runFold (FL.distribute [FL.sum, FL.length]) (S.enumerateFromTo 1 5)
816-- This is the consumer side dual of the producer side 'sequence' operation.
819{-# INLINE distribute #-}
820distribute :: Monad m => [Fold m a b] -> Fold m a [b]
821distribute [] = foldNil
822distribute (x:xs) = foldCons x (distribute xs)
824------------------------------------------------------------------------------
826------------------------------------------------------------------------------
828-- | Partition the input over two folds using an 'Either' partitioning
833-- |-------Fold b x--------|
834-- -----stream m a --> (Either b c)----| |----(x,y)
835-- |-------Fold c y--------|
838-- Send input to either fold randomly:
840-- >>> import System.Random (randomIO)
841-- >>> randomly a = randomIO >>= \x -> return $ if x then Left a else Right a
842-- >>> S.runFold (FL.partitionByM randomly FL.length FL.length) (S.enumerateFromTo 1 100)
845-- Send input to the two folds in a proportion of 2:1:
848-- import Data.IORef (newIORef, readIORef, writeIORef)
849-- proportionately m n = do
850-- ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
853-- writeIORef ref $ tail r
857-- f <- proportionately 2 1
858-- r <- S.runFold (FL.partitionByM f FL.length FL.length) (S.enumerateFromTo (1 :: Int) 100)
865-- This is the consumer side dual of the producer side 'mergeBy' operation.
868{-# INLINE partitionByM #-}
869partitionByM :: Monad m
870 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
871partitionByM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
877 begin = Tuple' <$> beginL <*> beginR
878 step (Tuple' xL xR) a = do
881 Left b -> Tuple' <$> stepL xL b <*> return xR
882 Right c -> Tuple' <$> return xL <*> stepR xR c
883 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
885-- Note: we could use (a -> Bool) instead of (a -> Either b c), but the latter
886-- makes the signature clearer as to which case belongs to which fold.
887-- XXX need to check the performance in both cases.
889-- | Same as 'partitionByM' but with a pure partition function.
891-- Count even and odd numbers in a stream:
894-- >>> let f = FL.partitionBy (\\n -> if even n then Left n else Right n)
895-- (fmap (("Even " ++) . show) FL.length)
896-- (fmap (("Odd " ++) . show) FL.length)
897-- in S.runFold f (S.enumerateFromTo 1 100)
898-- ("Even 50","Odd 50")
902{-# INLINE partitionBy #-}
903partitionBy :: Monad m
904 => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
905partitionBy f = partitionByM (return . f)
907-- | Compose two folds such that the combined fold accepts a stream of 'Either'
908-- and routes the 'Left' values to the first fold and 'Right' values to the
911-- > partition = partitionBy id
914{-# INLINE partition #-}
916 => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)
917partition = partitionBy id
920-- | Send one item to each fold in a round-robin fashion. This is the consumer
921-- side dual of producer side 'mergeN' operation.
923-- partitionN :: Monad m => [Fold m a b] -> Fold m a [b]
924-- partitionN fs = Fold step begin done
927-- TODO Demultiplex an input element into a number of typed variants. We want
928-- to statically restrict the target values within a set of predefined types,
929-- an enumeration of a GADT. We also want to make sure that the Map contains
930-- only those types and the full set of those types.
932-- TODO Instead of the input Map it should probably be a lookup-table using an
933-- array and not in GC memory. The same applies to the output Map as well.
934-- However, that would only be helpful if we have a very large data structure,
935-- need to measure and see how it scales.
937-- This is the consumer side dual of the producer side 'mux' operation (XXX to
940-- | Split the input stream based on a key field and fold each split using a
941-- specific fold collecting the results in a map from the keys to the results.
942-- Useful for cases like protocol handlers to handle different type of packets
943-- using different handlers.
948-- -----stream m a-----Map-----|
955{-# INLINE demuxWith #-}
956demuxWith :: (Monad m, Ord k)
957 => (a -> (k, a')) -> Map k (Fold m a' b) -> Fold m a (Map k b)
958demuxWith f kv = Fold step initial extract
963 step mp a = case f a of
964 (k, a') -> Map.alterF twiddle k mp
965 -- XXX should we raise an exception in Nothing case?
966 -- Ideally we should enforce that it is a total map over k so that look
968 -- XXX we could use a monadic update function for a single lookup and
969 -- update in the map.
971 twiddle Nothing = pure Nothing
972 twiddle (Just (Fold step' acc extract')) = do
973 !r <- acc >>= \x -> step' x a'
974 pure . Just $ Fold step' (return r) extract'
975 extract = Prelude.mapM (\(Fold _ acc e) -> acc >>= e)
977-- | Fold a stream of key value pairs using a map of specific folds for each
978-- key into a map from keys to the results of fold outputs of the corresponding
982-- > let table = Data.Map.fromList [(\"SUM", FL.sum), (\"PRODUCT", FL.product)]
983-- input = S.fromList [(\"SUM",1),(\"PRODUCT",2),(\"SUM",3),(\"PRODUCT",4)]
984-- in S.runFold (FL.demux table) input
991demux :: (Monad m, Ord k)
992 => Map k (Fold m a b) -> Fold m (k, a) (Map k b)
995-- | Split the input stream based on a key field and fold each split using a
996-- specific fold without collecting the results. Useful for cases like protocol
997-- handlers to handle different type of packets.
1001-- |-------Fold m a ()
1002-- -----stream m a-----Map-----|
1003-- |-------Fold m a ()
1011-- demuxWith_ can be slightly faster than demuxWith because we do not need to
1012-- update the Map in this case. This may be significant only if the map is
1014{-# INLINE demuxWith_ #-}
1015demuxWith_ :: (Monad m, Ord k)
1016 => (a -> (k, a')) -> Map k (Fold m a' b) -> Fold m a ()
1017demuxWith_ f kv = Fold step initial extract
1022 Prelude.mapM (\(Fold s i e) ->
1023 i >>= \r -> return (Fold s (return r) e)) kv
1025 -- XXX should we raise an exception in Nothing case?
1026 -- Ideally we should enforce that it is a total map over k so that look
1029 = case Map.lookup k mp of
1030 Nothing -> return mp
1031 Just (Fold step' acc _) -> do
1032 _ <- acc >>= \x -> step' x a'
1034 extract mp = Prelude.mapM_ (\(Fold _ acc e) -> acc >>= e) mp
1036-- | Given a stream of key value pairs and a map from keys to folds, fold the
1037-- values for each key using the corresponding folds, discarding the outputs.
1040-- > let prn = FL.drainBy print
1041-- > let table = Data.Map.fromList [(\"ONE", prn), (\"TWO", prn)]
1042-- input = S.fromList [(\"ONE",1),(\"TWO",2)]
1043-- in S.runFold (FL.demux_ table) input
1049{-# INLINE demux_ #-}
1050demux_ :: (Monad m, Ord k) => Map k (Fold m a ()) -> Fold m (k, a) ()
1051demux_ = demuxWith_ id
1053-- TODO If the data is large we may need a map/hashmap in pinned memory instead
1054-- of a regular Map. That may require a serializable constraint though. We can
1055-- have another API for that.
1057-- | Split the input stream based on a key field and fold each split using the
1058-- given fold. Useful for map/reduce, bucketizing the input in different bins
1059-- or for generating histograms.
1062-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1063-- in S.runFold (FL.classify FL.toList) input
1064-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1068{-# INLINE classifyWith #-}
1069classifyWith :: (Monad m, Ord k) => (a -> k) -> Fold m a b -> Fold m a (Map k b)
1070classifyWith f (Fold step initial extract) = Fold step' initial' extract'
1074 initial' = return Map.empty
1077 in case Map.lookup k kv of
1081 return $ Map.insert k r kv
1084 return $ Map.insert k r kv
1085 extract' = Prelude.mapM extract
1087-- | Given an input stream of key value pairs and a fold for values, fold all
1088-- the values belonging to each key. Useful for map/reduce, bucketizing the
1089-- input in different bins or for generating histograms.
1092-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1093-- in S.runFold (FL.classify FL.toList) input
1094-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1101-- > classify fld = classifyWith fst (lmap snd fld)
1103{-# INLINE classify #-}
1104classify :: (Monad m, Ord k) => Fold m a b -> Fold m (k, a) (Map k b)
1105classify fld = classifyWith fst (lmap snd fld)
1107------------------------------------------------------------------------------
1109------------------------------------------------------------------------------
1111-- | Like 'unzipWith' but with a monadic splitter function.
1114{-# INLINE unzipWithM #-}
1115unzipWithM :: Monad m
1116 => (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1117unzipWithM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
1118 Fold step begin done
1122 step (Tuple' xL xR) a = do
1124 Tuple' <$> stepL xL b <*> stepR xR c
1125 begin = Tuple' <$> beginL <*> beginR
1126 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
1128-- | Split elements in the input stream into two parts using a pure splitter
1129-- function, direct each part to a different fold and zip the results.
1132{-# INLINE unzipWith #-}
1134 => (a -> (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1135unzipWith f = unzipWithM (return . f)
1137-- | Send the elements of tuples in a stream of tuples through two different
1142-- |-------Fold m a x--------|
1143-- ---------stream of (a,b)--| |----m (x,y)
1144-- |-------Fold m b y--------|
1148-- This is the consumer side dual of the producer side 'zip' operation.
1152unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a,b) (x,y)
1155------------------------------------------------------------------------------
1157------------------------------------------------------------------------------
1160-- All the stream flattening transformations can also be applied to a fold
1163-- | This can be used to apply all the stream generation operations on folds.
1164lconcatMap ::(IsStream t, Monad m) => (a -> t m b)
1167lconcatMap s f1 f2 = undefined
1170-- All the grouping transformation that we apply to a stream can also be
1171-- applied to a fold input stream.
1174-- | Group the input stream into groups of elements between @low@ and @high@.
1175-- Collection starts in chunks of @low@ and then keeps doubling until we reach
1176-- @high@. Each chunk is folded using the provided fold function.
1178-- This could be useful, for example, when we are folding a stream of unknown
1179-- size to a stream of arrays and we want to minimize the number of
1184-- XXX we should be able to implement it with parsers/terminating folds.
1186{-# INLINE lchunksInRange #-}
1187lchunksInRange :: Monad m
1188 => Int -> Int -> Fold m a b -> Fold m b c -> Fold m a c
1189lchunksInRange low high (Fold step1 initial1 extract1)
1190 (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