1{-# OPTIONS_HADDOCK hide #-}
2{-# LANGUAGE BangPatterns #-}
4{-# LANGUAGE ExistentialQuantification #-}
5{-# LANGUAGE FlexibleContexts #-}
6{-# LANGUAGE RankNTypes #-}
7{-# LANGUAGE RecordWildCards #-}
8{-# LANGUAGE ScopedTypeVariables #-}
11-- Module : Streamly.Internal.Data.Fold
12-- Copyright : (c) 2019 Composewell Technologies
13-- (c) 2013 Gabriel Gonzalez
15-- Maintainer : streamly@composewell.com
16-- Stability : experimental
19-- Also see the "Streamly.Internal.Data.Sink" module that provides specialized left folds
20-- that discard the outputs.
22-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
24module Streamly.Internal.Data.Fold
35 -- * Fold Creation Utilities
58 -- , rollingHashFirstN
61 -- ** Full Folds (Monoidal)
66 -- ** Full Folds (To Containers)
69 , toListRevF -- experimental
87 -- XXX these are slower than right folds even when full input is used
95 -- ** Covariant Operations
112 -- ** Mapping Filters
116 -- ** Scanning Filters
121 -- | Insertion adds more elements to the stream.
170 -- These can be expressed using lmap/lmapM and unzip
181 , duplicate -- experimental
185import Control.Monad (void)
186import Data.Functor.Identity (Identity(..))
187import Data.Map.Strict (Map)
190 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
191 foldl, map, mapM_, sequence, all, any, sum, product, elem,
192 notElem, maximum, minimum, head, last, tail, length, null,
193 reverse, iterate, init, and, or, lookup, foldr1, (!!),
194 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
195 span, splitAt, break, mapM)
197import qualified Data.Map.Strict as Map
198import qualified Prelude
200import Streamly.Internal.Data.Pipe.Types (Pipe (..), PipeState(..))
201import Streamly.Internal.Data.Fold.Types
202import Streamly.Internal.Data.Strict
204import qualified Streamly.Internal.Data.Pipe.Types as Pipe
206------------------------------------------------------------------------------
208------------------------------------------------------------------------------
210-- | Make a fold using a pure step function, a pure initial state and
211-- a pure state extraction function.
216mkPure :: Monad m => (s -> a -> s) -> s -> (s -> b) -> Fold m a b
217mkPure step initial extract =
218 Fold (\s a -> return $ step s a) (return initial) (return . extract)
220-- | Make a fold using a pure step function and a pure initial state. The
221-- final state extracted is identical to the intermediate state.
225{-# INLINE mkPureId #-}
226mkPureId :: Monad m => (b -> a -> b) -> b -> Fold m a b
227mkPureId step initial = mkPure step initial id
229-- | Make a fold with an effectful step function and initial state, and a state
230-- extraction function.
234-- We can just use 'Fold' but it is provided for completeness.
239mkFold :: (s -> a -> m s) -> m s -> (s -> m b) -> Fold m a b
242-- | Make a fold with an effectful step function and initial state. The final
243-- state extracted is identical to the intermediate state.
247{-# INLINE mkFoldId #-}
248mkFoldId :: Monad m => (b -> a -> m b) -> m b -> Fold m a b
249mkFoldId step initial = Fold step initial return
251------------------------------------------------------------------------------
253------------------------------------------------------------------------------
255-- | Change the underlying monad of a fold
258hoist :: (forall x. m x -> n x) -> Fold m a b -> Fold n a b
259hoist f (Fold step initial extract) =
260 Fold (\x a -> f $ step x a) (f initial) (f . extract)
262-- | Adapt a pure fold to any monad
264-- > generally = hoist (return . runIdentity)
267generally :: Monad m => Fold Identity a b -> Fold m a b
268generally = hoist (return . runIdentity)
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 #-}
302transform :: Monad m => Pipe m a b -> Fold m b c -> Fold m a c
303transform (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-- | Compute an 'Int' sized polynomial rolling hash
516-- > H = salt * k ^ n + c1 * k ^ (n - 1) + c2 * k ^ (n - 2) + ... + cn * k ^ 0
518-- Where @c1@, @c2@, @cn@ are the elements in the input stream and @k@ is a
521-- This hash is often used in Rabin-Karp string search algorithm.
523-- See https://en.wikipedia.org/wiki/Rolling_hash
526{-# INLINABLE rollingHashWithSalt #-}
527rollingHashWithSalt :: (Monad m, Enum a) => Int -> Fold m a Int
528rollingHashWithSalt salt = Fold step initial extract
531 initial = return salt
532 step cksum a = return $ cksum * k + fromEnum a
535-- | A default salt used in the implementation of 'rollingHash'.
536{-# INLINE defaultSalt #-}
538#if WORD_SIZE_IN_BITS == 64
539defaultSalt = 0xdc36d1615b7400a4
541defaultSalt = 0x087fc72c
544-- | Compute an 'Int' sized polynomial rolling hash of a stream.
546-- > rollingHash = rollingHashWithSalt defaultSalt
549{-# INLINABLE rollingHash #-}
550rollingHash :: (Monad m, Enum a) => Fold m a Int
551rollingHash = rollingHashWithSalt defaultSalt
553------------------------------------------------------------------------------
554-- Monoidal left folds
555------------------------------------------------------------------------------
557-- | Fold an input stream consisting of monoidal elements using 'mappend'
560-- > S.fold FL.mconcat (S.map Sum $ S.enumerateFromTo 1 10)
563{-# INLINABLE mconcat #-}
564mconcat :: (Monad m, Monoid a) => Fold m a a
565mconcat = Fold (\x a -> return $ mappend x a) (return mempty) return
568-- > foldMap f = map f mconcat
570-- Make a fold from a pure function that folds the output of the function
571-- using 'mappend' and 'mempty'.
573-- > S.fold (FL.foldMap Sum) $ S.enumerateFromTo 1 10
576{-# INLINABLE foldMap #-}
577foldMap :: (Monad m, Monoid b) => (a -> b) -> Fold m a b
578foldMap f = lmap f mconcat
581-- > foldMapM f = mapM f mconcat
583-- Make a fold from a monadic function that folds the output of the function
584-- using 'mappend' and 'mempty'.
586-- > S.fold (FL.foldMapM (return . Sum)) $ S.enumerateFromTo 1 10
589{-# INLINABLE foldMapM #-}
590foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b
591foldMapM act = Fold step begin done
594 begin = return mempty
597 return $! mappend m m'
599------------------------------------------------------------------------------
601------------------------------------------------------------------------------
603-- | Folds the input stream to a list.
605-- /Warning!/ working on large lists accumulated as buffers in memory could be
606-- very inefficient, consider using "Streamly.Array" instead.
610-- id . (x1 :) . (x2 :) . (x3 :) . ... . (xn :) $ []
611{-# INLINABLE toList #-}
612toList :: Monad m => Fold m a [a]
613toList = Fold (\f x -> return $ f . (x :))
617------------------------------------------------------------------------------
619------------------------------------------------------------------------------
621------------------------------------------------------------------------------
623------------------------------------------------------------------------------
625-- | Like 'index', except with a more general 'Integral' argument
628{-# INLINABLE genericIndex #-}
629genericIndex :: (Integral i, Monad m) => i -> Fold m a (Maybe a)
630genericIndex i = Fold step (return $ Left' 0) done
643-- | Lookup the element at the given index.
646{-# INLINABLE index #-}
647index :: Monad m => Int -> Fold m a (Maybe a)
650-- | Extract the first element of the stream, if any.
653{-# INLINABLE head #-}
654head :: Monad m => Fold m a (Maybe a)
657-- | Returns the first element that satisfies the given predicate.
660{-# INLINABLE find #-}
661find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
662find predicate = Fold step (return Nothing') fromStrictMaybe
666 Nothing' -> if predicate a
671-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
672-- first pair where the key equals the given value @a@.
675{-# INLINABLE lookup #-}
676lookup :: (Eq a, Monad m) => a -> Fold m (a,b) (Maybe b)
677lookup a0 = Fold step (return Nothing') fromStrictMaybe
679 step x (a,b) = return $
681 Nothing' -> if a == a0
686-- | Convert strict 'Either'' to lazy 'Maybe'
687{-# INLINABLE hush #-}
688hush :: Either' a b -> Maybe b
689hush (Left' _) = Nothing
690hush (Right' b) = Just b
692-- | Returns the first index that satisfies the given predicate.
695{-# INLINABLE findIndex #-}
696findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
697findIndex predicate = Fold step (return $ Left' 0) (return . hush)
707-- | Returns the first index where a given value is found in the stream.
710{-# INLINABLE elemIndex #-}
711elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)
712elemIndex a = findIndex (a ==)
714------------------------------------------------------------------------------
716------------------------------------------------------------------------------
718-- | Return 'True' if the input stream is empty.
721{-# INLINABLE null #-}
722null :: Monad m => Fold m a Bool
723null = Fold (\_ _ -> return False) (return True) return
726-- > any p = lmap p or
728-- | Returns 'True' if any of the elements of a stream satisfies a predicate.
732any :: Monad m => (a -> Bool) -> Fold m a Bool
733any predicate = Fold (\x a -> return $ x || predicate a) (return False) return
735-- | Return 'True' if the given element is present in the stream.
738{-# INLINABLE elem #-}
739elem :: (Eq a, Monad m) => a -> Fold m a Bool
743-- > all p = lmap p and
745-- | Returns 'True' if all elements of a stream satisfy a predicate.
749all :: Monad m => (a -> Bool) -> Fold m a Bool
750all predicate = Fold (\x a -> return $ x && predicate a) (return True) return
752-- | Returns 'True' if the given element is not present in the stream.
755{-# INLINABLE notElem #-}
756notElem :: (Eq a, Monad m) => a -> Fold m a Bool
757notElem a = all (a /=)
759-- | Returns 'True' if all elements are 'True', 'False' otherwise
763and :: Monad m => Fold m Bool Bool
764and = Fold (\x a -> return $ x && a) (return True) return
766-- | Returns 'True' if any element is 'True', 'False' otherwise
770or :: Monad m => Fold m Bool Bool
771or = Fold (\x a -> return $ x || a) (return False) return
773------------------------------------------------------------------------------
775------------------------------------------------------------------------------
777-- | Distribute one copy of the stream to each fold and zip the results.
780-- |-------Fold m a b--------|
781-- ---stream m a---| |---m (b,c)
782-- |-------Fold m a c--------|
784-- >>> S.fold (FL.tee FL.sum FL.length) (S.enumerateFromTo 1.0 100.0)
789tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b,c)
790tee f1 f2 = (,) <$> f1 <*> f2
792{-# INLINE foldNil #-}
793foldNil :: Monad m => Fold m a [b]
794foldNil = Fold step begin done where
799{-# INLINE foldCons #-}
800foldCons :: Monad m => Fold m a b -> Fold m a [b] -> Fold m a [b]
801foldCons (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
806 begin = Tuple' <$> beginL <*> beginR
807 step (Tuple' xL xR) a = Tuple' <$> stepL xL a <*> stepR xR a
808 done (Tuple' xL xR) = (:) <$> (doneL xL) <*> (doneR xR)
810-- XXX use "List" instead of "[]"?, use Array for output to scale it to a large
811-- number of consumers? For polymorphic case a vector could be helpful. For
812-- Storables we can use arrays. Will need separate APIs for those.
814-- | Distribute one copy of the stream to each fold and collect the results in
819-- |-------Fold m a b--------|
820-- ---stream m a---| |---m [b]
821-- |-------Fold m a b--------|
826-- >>> S.fold (FL.distribute [FL.sum, FL.length]) (S.enumerateFromTo 1 5)
829-- This is the consumer side dual of the producer side 'sequence' operation.
832{-# INLINE distribute #-}
833distribute :: Monad m => [Fold m a b] -> Fold m a [b]
834distribute [] = foldNil
835distribute (x:xs) = foldCons x (distribute xs)
837------------------------------------------------------------------------------
839------------------------------------------------------------------------------
841-- | Partition the input over two folds using an 'Either' partitioning
846-- |-------Fold b x--------|
847-- -----stream m a --> (Either b c)----| |----(x,y)
848-- |-------Fold c y--------|
851-- Send input to either fold randomly:
853-- >>> import System.Random (randomIO)
854-- >>> randomly a = randomIO >>= \x -> return $ if x then Left a else Right a
855-- >>> S.fold (FL.partitionByM randomly FL.length FL.length) (S.enumerateFromTo 1 100)
858-- Send input to the two folds in a proportion of 2:1:
861-- import Data.IORef (newIORef, readIORef, writeIORef)
862-- proportionately m n = do
863-- ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
866-- writeIORef ref $ tail r
870-- f <- proportionately 2 1
871-- r <- S.fold (FL.partitionByM f FL.length FL.length) (S.enumerateFromTo (1 :: Int) 100)
878-- This is the consumer side dual of the producer side 'mergeBy' operation.
881{-# INLINE partitionByM #-}
882partitionByM :: Monad m
883 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
884partitionByM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
890 begin = Tuple' <$> beginL <*> beginR
891 step (Tuple' xL xR) a = do
894 Left b -> Tuple' <$> stepL xL b <*> return xR
895 Right c -> Tuple' <$> return xL <*> stepR xR c
896 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
898-- Note: we could use (a -> Bool) instead of (a -> Either b c), but the latter
899-- makes the signature clearer as to which case belongs to which fold.
900-- XXX need to check the performance in both cases.
902-- | Same as 'partitionByM' but with a pure partition function.
904-- Count even and odd numbers in a stream:
907-- >>> let f = FL.partitionBy (\\n -> if even n then Left n else Right n)
908-- (fmap (("Even " ++) . show) FL.length)
909-- (fmap (("Odd " ++) . show) FL.length)
910-- in S.fold f (S.enumerateFromTo 1 100)
911-- ("Even 50","Odd 50")
915{-# INLINE partitionBy #-}
916partitionBy :: Monad m
917 => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
918partitionBy f = partitionByM (return . f)
920-- | Compose two folds such that the combined fold accepts a stream of 'Either'
921-- and routes the 'Left' values to the first fold and 'Right' values to the
924-- > partition = partitionBy id
927{-# INLINE partition #-}
929 => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)
930partition = partitionBy id
933-- | Send one item to each fold in a round-robin fashion. This is the consumer
934-- side dual of producer side 'mergeN' operation.
936-- partitionN :: Monad m => [Fold m a b] -> Fold m a [b]
937-- partitionN fs = Fold step begin done
940-- TODO Demultiplex an input element into a number of typed variants. We want
941-- to statically restrict the target values within a set of predefined types,
942-- an enumeration of a GADT. We also want to make sure that the Map contains
943-- only those types and the full set of those types.
945-- TODO Instead of the input Map it should probably be a lookup-table using an
946-- array and not in GC memory. The same applies to the output Map as well.
947-- However, that would only be helpful if we have a very large data structure,
948-- need to measure and see how it scales.
950-- This is the consumer side dual of the producer side 'mux' operation (XXX to
953-- | Split the input stream based on a key field and fold each split using a
954-- specific fold collecting the results in a map from the keys to the results.
955-- Useful for cases like protocol handlers to handle different type of packets
956-- using different handlers.
961-- -----stream m a-----Map-----|
968{-# INLINE demuxWith #-}
969demuxWith :: (Monad m, Ord k)
970 => (a -> (k, a')) -> Map k (Fold m a' b) -> Fold m a (Map k b)
971demuxWith f kv = Fold step initial extract
976 step mp a = case f a of
977 (k, a') -> Map.alterF twiddle k mp
978 -- XXX should we raise an exception in Nothing case?
979 -- Ideally we should enforce that it is a total map over k so that look
981 -- XXX we could use a monadic update function for a single lookup and
982 -- update in the map.
984 twiddle Nothing = pure Nothing
985 twiddle (Just (Fold step' acc extract')) = do
986 !r <- acc >>= \x -> step' x a'
987 pure . Just $ Fold step' (return r) extract'
988 extract = Prelude.mapM (\(Fold _ acc e) -> acc >>= e)
990-- | Fold a stream of key value pairs using a map of specific folds for each
991-- key into a map from keys to the results of fold outputs of the corresponding
995-- > let table = Data.Map.fromList [(\"SUM", FL.sum), (\"PRODUCT", FL.product)]
996-- input = S.fromList [(\"SUM",1),(\"PRODUCT",2),(\"SUM",3),(\"PRODUCT",4)]
997-- in S.fold (FL.demux table) input
1004demux :: (Monad m, Ord k)
1005 => Map k (Fold m a b) -> Fold m (k, a) (Map k b)
1008-- | Split the input stream based on a key field and fold each split using a
1009-- specific fold without collecting the results. Useful for cases like protocol
1010-- handlers to handle different type of packets.
1014-- |-------Fold m a ()
1015-- -----stream m a-----Map-----|
1016-- |-------Fold m a ()
1024-- demuxWith_ can be slightly faster than demuxWith because we do not need to
1025-- update the Map in this case. This may be significant only if the map is
1027{-# INLINE demuxWith_ #-}
1028demuxWith_ :: (Monad m, Ord k)
1029 => (a -> (k, a')) -> Map k (Fold m a' b) -> Fold m a ()
1030demuxWith_ f kv = Fold step initial extract
1035 Prelude.mapM (\(Fold s i e) ->
1036 i >>= \r -> return (Fold s (return r) e)) kv
1038 -- XXX should we raise an exception in Nothing case?
1039 -- Ideally we should enforce that it is a total map over k so that look
1042 = case Map.lookup k mp of
1043 Nothing -> return mp
1044 Just (Fold step' acc _) -> do
1045 _ <- acc >>= \x -> step' x a'
1047 extract mp = Prelude.mapM_ (\(Fold _ acc e) -> acc >>= e) mp
1049-- | Given a stream of key value pairs and a map from keys to folds, fold the
1050-- values for each key using the corresponding folds, discarding the outputs.
1053-- > let prn = FL.drainBy print
1054-- > let table = Data.Map.fromList [(\"ONE", prn), (\"TWO", prn)]
1055-- input = S.fromList [(\"ONE",1),(\"TWO",2)]
1056-- in S.fold (FL.demux_ table) input
1062{-# INLINE demux_ #-}
1063demux_ :: (Monad m, Ord k) => Map k (Fold m a ()) -> Fold m (k, a) ()
1064demux_ = demuxWith_ id
1066-- TODO If the data is large we may need a map/hashmap in pinned memory instead
1067-- of a regular Map. That may require a serializable constraint though. We can
1068-- have another API for that.
1070-- | Split the input stream based on a key field and fold each split using the
1071-- given fold. Useful for map/reduce, bucketizing the input in different bins
1072-- or for generating histograms.
1075-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1076-- in S.fold (FL.classify FL.toList) input
1077-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1081{-# INLINE classifyWith #-}
1082classifyWith :: (Monad m, Ord k) => (a -> k) -> Fold m a b -> Fold m a (Map k b)
1083classifyWith f (Fold step initial extract) = Fold step' initial' extract'
1087 initial' = return Map.empty
1090 in case Map.lookup k kv of
1094 return $ Map.insert k r kv
1097 return $ Map.insert k r kv
1098 extract' = Prelude.mapM extract
1100-- | Given an input stream of key value pairs and a fold for values, fold all
1101-- the values belonging to each key. Useful for map/reduce, bucketizing the
1102-- input in different bins or for generating histograms.
1105-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
1106-- in S.fold (FL.classify FL.toList) input
1107-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
1114-- > classify fld = classifyWith fst (lmap snd fld)
1116{-# INLINE classify #-}
1117classify :: (Monad m, Ord k) => Fold m a b -> Fold m (k, a) (Map k b)
1118classify fld = classifyWith fst (lmap snd fld)
1120------------------------------------------------------------------------------
1122------------------------------------------------------------------------------
1124-- | Like 'unzipWith' but with a monadic splitter function.
1127{-# INLINE unzipWithM #-}
1128unzipWithM :: Monad m
1129 => (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1130unzipWithM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
1131 Fold step begin done
1135 step (Tuple' xL xR) a = do
1137 Tuple' <$> stepL xL b <*> stepR xR c
1138 begin = Tuple' <$> beginL <*> beginR
1139 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
1141-- | Split elements in the input stream into two parts using a pure splitter
1142-- function, direct each part to a different fold and zip the results.
1145{-# INLINE unzipWith #-}
1147 => (a -> (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1148unzipWith f = unzipWithM (return . f)
1150-- | Send the elements of tuples in a stream of tuples through two different
1155-- |-------Fold m a x--------|
1156-- ---------stream of (a,b)--| |----m (x,y)
1157-- |-------Fold m b y--------|
1161-- This is the consumer side dual of the producer side 'zip' operation.
1165unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a,b) (x,y)
1168------------------------------------------------------------------------------
1170------------------------------------------------------------------------------
1173-- All the stream flattening transformations can also be applied to a fold
1176-- | This can be used to apply all the stream generation operations on folds.
1177lconcatMap ::(IsStream t, Monad m) => (a -> t m b)
1180lconcatMap s f1 f2 = undefined
1183-- All the grouping transformation that we apply to a stream can also be
1184-- applied to a fold input stream.
1187-- | Group the input stream into groups of elements between @low@ and @high@.
1188-- Collection starts in chunks of @low@ and then keeps doubling until we reach
1189-- @high@. Each chunk is folded using the provided fold function.
1191-- This could be useful, for example, when we are folding a stream of unknown
1192-- size to a stream of arrays and we want to minimize the number of
1197-- XXX we should be able to implement it with parsers/terminating folds.
1199{-# INLINE lchunksInRange #-}
1200lchunksInRange :: Monad m
1201 => Int -> Int -> Fold m a b -> Fold m b c -> Fold m a c
1202lchunksInRange low high (Fold step1 initial1 extract1)
1203 (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