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-- This module is the consumer side dual of the "Streamly.Prelude" module. The
19-- "Streamly.Prelude" module contains producer or stream generation side
20-- compositions while this module contains consumer side or stream fold
21-- composition. Both the modules are organized in the same way so that you can
22-- easily find the corresponding operations.
24-- Stream consumers are essentially left folds that can be composed in many
25-- interesting ways. For example, a parsing applicative composition builds an
26-- applicative parser, a distributing applicative fold composition distributes
27-- the input to the constituent folds and then combines the outputs.
28-- Similarly, a partitioning applicative can partition the input among the
29-- constituent folds. There are many other ways to combine folds.
31-- All combinators in this module are of true streaming nature. For example,
32-- the splitting combinators accept a fold which consumes the elements in the
33-- split segments as soon as they are generated by the producer, segments are
34-- not buffered in memory, resulting in constant memory usage. The folds used
35-- in these combinators can be considered as continuations.
37-- > import qualified Streamly.Fold as FL
40-- A left fold is represented by the type 'Fold'. @Fold m a b@ folds an
41-- input stream consisting of values of type @a@ to a structure of type
42-- @b@. The fold can be run using 'foldl'' and an input stream.
44-- >>> FL.foldl' FL.sum (S.enumerateFromTo 1 100)
47-- Also see the "Streamly.Sink" module that provides specialized left folds
48-- that discard the outputs.
49-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
80 -- ** Full Folds (Monoidal)
85 -- ** Full Folds (To Containers)
86 -- | Avoid using these folds in scalable or performance critical
87 -- applications, they buffer all the input in memory.
89 , toStream -- experimental
90 , toStreamRev -- experimental
93 , toListRev -- experimental
110 -- XXX these are slower than right folds even when full input is used
117 -- | Unlike stream producer types (e.g. @SerialT m a@) which have only
118 -- output side, folds have an input side as well as an output side. In the
119 -- type @Fold m a b@, the input type is @a@ and the output type is @b@.
120 -- Transformations can be applied either on the input side or on the output
121 -- side. The 'Functor' instance of a fold maps on the output of the fold:
123 -- >>> FL.foldl' (fmap show FL.sum) (S.enumerateFromTo 1 100)
126 -- However, the input side or contravariant transformations are more
127 -- interesting for folds. The following sections describe the input
128 -- transformation operations on a fold. The names of the operations are
129 -- consistent with their covariant counterparts in "Streamly.Prelude", the
130 -- only difference is that they are prefixed with 'l' which stands for
131 -- 'left' assuming left side is the input side, notice that in @Fold m a b@
132 -- the type variable @a@ is on the left side.
160 -- ** Mapping Filters
164 -- ** Scanning Filters
169 -- | Insertion adds more elements to the stream.
209 -- | Streams can be split into segments in space or in time. We use the
210 -- term @chunk@ to refer to a spatial length of the stream (spatial window)
211 -- and the term @session@ to refer to a length in time (time window).
213 -- In imperative terms, grouped folding can be considered as a nested loop
214 -- where we loop over the stream to group elements and then loop over
215 -- individual groups to fold them to a single value that is yielded in the
237 -- Keeping the delimiters
242 -- Splitting by multiple sequences
244 -- , splitSuffixOnAny
245 -- , splitPrefixOnAny
254 -- The 'Applicative' instance of a distributing 'Fold' distributes one copy
255 -- of the stream to each fold and combines the results using a function.
259 -- |-------Fold m a b--------|
260 -- ---stream m a---| |---m (b,c,...)
261 -- |-------Fold m a c--------|
266 -- To compute the average of numbers in a stream without going throught he
269 -- >>> let avg = (/) <$> FL.sum <*> fmap fromIntegral FL.length
270 -- >>> FL.foldl' avg (S.enumerateFromTo 1.0 100.0)
273 -- The 'Semigroup' and 'Monoid' instances of a distributing fold distribute
274 -- the input to both the folds and combines the outputs using Monoid or
275 -- Semigroup instances of the output types:
277 -- >>> import Data.Monoid (Sum)
278 -- >>> FL.foldl' (FL.head <> FL.last) (fmap Sum $ S.enumerateFromTo 1.0 100.0)
279 -- Just (Sum {getSum = 101.0})
281 -- The 'Num', 'Floating', and 'Fractional' instances work in the same way.
288 -- Direct items in the input stream to different folds using a function to
289 -- select the fold. This is useful to demultiplex the input stream.
306 -- These can be expressed using lmap/lmapM and unzip
313 , duplicate -- experimental
315 -- * Windowed Classification
316 -- | Split the stream into windows or chunks in space or time. Each window
317 -- can be associated with a key, all events associated with a particular
318 -- key in the window can be folded to a single result. The stream is split
319 -- into windows of specified size, the window can be terminated early if
320 -- the closing flag is specified in the input stream.
322 -- The term "chunk" is used for a space window and the term "session" is
323 -- used for a time window.
325 -- ** Tumbling Windows
326 -- | A new window starts after the previous window is finished.
327 -- , classifyChunksOf
330 -- ** Keep Alive Windows
331 -- | The window size is extended if an event arrives within the specified
332 -- window size. This can represent sessions with idle or inactive timeout.
333 -- , classifyKeepAliveChunks
334 , classifyKeepAliveSessions
337 -- ** Sliding Windows
338 -- | A new window starts after the specified slide from the previous
339 -- window. Therefore windows can overlap.
340 , classifySlidingChunks
341 , classifySlidingSessions
343 -- ** Sliding Window Buffers
344 -- , slidingChunkBuffer
345 -- , slidingSessionBuffer
349import Control.Concurrent (threadDelay)
350import Control.Monad (void)
351import Control.Monad.IO.Class (MonadIO(..))
352import Data.Functor.Identity (Identity)
353import Data.Heap (Entry(..))
354import Data.Map.Strict (Map)
355import Data.Maybe (fromJust, isJust, isNothing)
357import Foreign.Storable (Storable(..))
359 hiding (filter, drop, dropWhile, take, takeWhile, zipWith, foldr,
360 foldl, map, mapM_, sequence, all, any, sum, product, elem,
361 notElem, maximum, minimum, head, last, tail, length, null,
362 reverse, iterate, init, and, or, lookup, foldr1, (!!),
363 scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip,
364 span, splitAt, break)
366import qualified Data.Heap as H
367import qualified Data.Map.Strict as Map
369import Streamly (MonadAsync, parallel)
370import Streamly.Fold.Types (Fold(..))
371import Streamly.Mem.Array (Array)
372-- import Streamly.Mem.Ring (Ring)
373import Streamly.Streams.Serial (SerialT)
374import Streamly.Streams.StreamK (IsStream())
375import Streamly.Time.Units
376 (AbsTime, MilliSecond64(..), addToAbsTime, diffAbsTime, toRelTime,
379import Streamly.Strict
381import qualified Streamly.Mem.Array as A
382import qualified Streamly.Prelude as S
383import qualified Streamly.Streams.StreamD as D
384import qualified Streamly.Streams.StreamK as K
385import qualified Streamly.Streams.Prelude as P
389-- We can use the left folds in this module instead of the folds in
390-- "Streamly.Prelude". For example the following two ways of folding are
391-- equivalent in functionality and performance,
393-- >>> FL.foldl' FL.sum (S.enumerateFromTo 1 100)
395-- >>> S.sum (S.enumerateFromTo 1 100)
398-- However, left folds are push type folds. That means we push the entire input
399-- to a fold before we can get the output. Therefore, the performance is
400-- equivalent only for full folds like 'sum' and 'length'. For partial folds
401-- like 'head' or 'any' the folds in "Streamly.Prelude" may be much more
402-- efficient because they are implemented as right folds that terminate as soon
403-- as we get the result. Note that when a full fold is composed with a partial
404-- fold in parallel the performance is not impacted as we anyway have to
405-- consume the whole stream due to the full fold.
407-- >>> S.head (1 `S.cons` undefined)
409-- >>> FL.foldl' FL.head (1 `S.cons` undefined)
410-- *** Exception: Prelude.undefined
412-- However, we can wrap the fold in a scan to convert it into a lazy stream of
413-- fold steps. We can then terminate the stream whenever we want. For example,
415-- >>> S.toList $ S.take 1 $ FL.scanl' FL.head (1 `S.cons` undefined)
418-- The following example extracts the input stream up to a point where the
419-- running average of elements is no more than 10:
423-- $ S.map (fromJust . fst)
424-- $ S.takeWhile (\\(_,x) -> x <= 10)
425-- $ FL.postscanl' ((,) \<$> FL.last \<*> avg) (S.enumerateFromTo 1.0 100.0)
428-- [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0,16.0,17.0,18.0,19.0]
431------------------------------------------------------------------------------
433------------------------------------------------------------------------------
435-- | Fold a stream using the supplied monadic fold.
437-- >>> FL.foldl' FL.sum (S.enumerateFromTo 1 100)
442foldl' :: Monad m => Fold m a b -> SerialT m a -> m b
443foldl' (Fold step begin done) = P.foldlMx' step begin done
445------------------------------------------------------------------------------
446-- Transformations on fold inputs
447------------------------------------------------------------------------------
449-- | @(lmap f fold)@ maps the function @f@ on the input of the fold.
451-- >>> FL.foldl' (FL.lmap (\x -> x * x) FL.sum) (S.enumerateFromTo 1 100)
455{-# INLINABLE lmap #-}
456lmap :: (a -> b) -> Fold m b r -> Fold m a r
457lmap f (Fold step begin done) = Fold step' begin done
459 step' x a = step x (f a)
461-- | @(lmapM f fold)@ maps the monadic function @f@ on the input of the fold.
464{-# INLINABLE lmapM #-}
465lmapM :: Monad m => (a -> m b) -> Fold m b r -> Fold m a r
466lmapM f (Fold step begin done) = Fold step' begin done
468 step' x a = f a >>= step x
470------------------------------------------------------------------------------
472------------------------------------------------------------------------------
474-- | @_Fold1 step@ returns a new 'Fold' using just a step function that has the
475-- same type for the accumulator and the element. The result type is the
476-- accumulator type wrapped in 'Maybe'. The initial accumulator is retrieved
477-- from the 'Foldable', the result is 'None' for empty containers.
478{-# INLINABLE _Fold1 #-}
479_Fold1 :: Monad m => (a -> a -> a) -> Fold m a (Maybe a)
480_Fold1 step = Fold step_ (return Nothing') fromStrictMaybe
482 step_ mx a = return $ Just' $
487------------------------------------------------------------------------------
489------------------------------------------------------------------------------
491------------------------------------------------------------------------------
493------------------------------------------------------------------------------
495-- | A fold that drains all its input, running the effects and discarding the
499{-# INLINABLE drain #-}
500drain :: Monad m => Fold m a ()
501drain = Fold step begin done
508-- > drainBy f = lmapM f drain
510-- Drain all input after passing it through a monadic function. This is the
511-- dual of mapM_ on stream producers.
512{-# INLINABLE drainBy #-}
513drainBy :: Monad m => (a -> m b) -> Fold m a ()
514drainBy f = Fold (const (void . f)) (return ()) return
516-- | Extract the last element of the input stream, if any.
519{-# INLINABLE last #-}
520last :: Monad m => Fold m a (Maybe a)
521last = _Fold1 (flip const)
523------------------------------------------------------------------------------
525------------------------------------------------------------------------------
527-- | Like 'length', except with a more general 'Num' return value
530{-# INLINABLE genericLength #-}
531genericLength :: (Monad m, Num b) => Fold m a b
532genericLength = Fold (\n _ -> return $ n + 1) (return 0) return
534-- | Determine the length of the input stream.
537{-# INLINABLE length #-}
538length :: Monad m => Fold m a Int
539length = genericLength
541-- | Determine the sum of all elements of a stream of numbers. Returns additive
542-- identity (@0@) when the stream is empty. Note that this is not numerically
543-- stable for floating point numbers.
547sum :: (Monad m, Num a) => Fold m a a
548sum = Fold (\x a -> return $ x + a) (return 0) return
550-- | Determine the product of all elements of a stream of numbers. Returns
551-- multiplicative identity (@1@) when the stream is empty.
554{-# INLINABLE product #-}
555product :: (Monad m, Num a) => Fold m a a
556product = Fold (\x a -> return $ x * a) (return 1) return
558------------------------------------------------------------------------------
560------------------------------------------------------------------------------
562-- | Determine the maximum element in a stream using the supplied comparison
566{-# INLINABLE maximumBy #-}
567maximumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
568maximumBy cmp = _Fold1 max'
570 max' x y = case cmp x y of
576-- maximum = 'maximumBy' compare
579-- Determine the maximum element in a stream.
582{-# INLINABLE maximum #-}
583maximum :: (Monad m, Ord a) => Fold m a (Maybe a)
586-- | Computes the minimum element with respect to the given comparison function
587{-# INLINABLE minimumBy #-}
588minimumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
589minimumBy cmp = _Fold1 min'
591 min' x y = case cmp x y of
595-- | Determine the minimum element in a stream using the supplied comparison
599{-# INLINABLE minimum #-}
600minimum :: (Monad m, Ord a) => Fold m a (Maybe a)
603------------------------------------------------------------------------------
604-- To Summary (Statistical)
605------------------------------------------------------------------------------
607-- | Compute a numerically stable arithmetic mean of all elements in the input
611{-# INLINABLE mean #-}
612mean :: (Monad m, Fractional a) => Fold m a a
613mean = Fold step (return begin) (return . done)
616 step (Tuple' x n) y = return $
618 in Tuple' (x + (y - x) / n') n'
619 done (Tuple' x _) = x
621-- | Compute a numerically stable (population) variance over all elements in
625{-# INLINABLE variance #-}
626variance :: (Monad m, Fractional a) => Fold m a a
627variance = Fold step (return begin) (return . done)
629 begin = Tuple3' 0 0 0
631 step (Tuple3' n mean_ m2) x = return $ Tuple3' n' mean' m2'
634 mean' = (n * mean_ + x) / (n + 1)
636 m2' = m2 + delta * delta * n / (n + 1)
638 done (Tuple3' n _ m2) = m2 / n
640-- | Compute a numerically stable (population) standard deviation over all
641-- elements in the input stream.
644{-# INLINABLE stdDev #-}
645stdDev :: (Monad m, Floating a) => Fold m a a
646stdDev = sqrt variance
648------------------------------------------------------------------------------
649-- Monoidal left folds
650------------------------------------------------------------------------------
652-- | Fold an input stream consisting of monoidal elements using 'mappend'
655-- > FL.foldl FL.mconcat (S.map Sum $ S.enumerateFromTo 1 10)
658{-# INLINABLE mconcat #-}
659mconcat :: (Monad m, Monoid a) => Fold m a a
660mconcat = Fold (\x a -> return $ mappend x a) (return mempty) return
663-- > foldMap f = map f mconcat
665-- Make a fold from a pure function that folds the output of the function
666-- using 'mappend' and 'mempty'.
668-- > FL.foldl (FL.foldMap Sum) $ S.enumerateFromTo 1 10
671{-# INLINABLE foldMap #-}
672foldMap :: (Monad m, Monoid b) => (a -> b) -> Fold m a b
673foldMap f = lmap f mconcat
676-- > foldMapM f = mapM f mconcat
678-- Make a fold from a monadic function that folds the output of the function
679-- using 'mappend' and 'mempty'.
681-- > FL.foldM (FL.foldMapM (return . Sum)) $ S.enumerateFromTo 1 10
684{-# INLINABLE foldMapM #-}
685foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b
686foldMapM act = Fold step begin done
689 begin = return mempty
692 return $! mappend m m'
694------------------------------------------------------------------------------
696------------------------------------------------------------------------------
698-- | Folds the input stream to a list.
700-- /Warning!/ working on large lists accumulated as buffers in memory could be
701-- very inefficient, consider using "Streamly.Array" instead.
705-- id . (x1 :) . (x2 :) . (x3 :) . ... . (xn :) $ []
706{-# INLINABLE toList #-}
707toList :: Monad m => Fold m a [a]
708toList = Fold (\f x -> return $ f . (x :))
712-- This is more efficient than 'toList'. toList is exactly the same as
713-- reversing the list after toListRev.
715-- | Buffers the input stream to a list in the reverse order of the input.
717-- /Warning!/ working on large lists accumulated as buffers in memory could be
718-- very inefficient, consider using "Streamly.Array" instead.
722-- xn : ... : x2 : x1 : []
723{-# INLINABLE toListRev #-}
724toListRev :: Monad m => Fold m a [a]
725toListRev = Fold (\xs x -> return $ x:xs) (return []) return
727-- | A fold that buffers its input to a pure stream.
729-- /Warning!/ working on large streams accumulated as buffers in memory could
730-- be very inefficient, consider using "Streamly.Array" instead.
733{-# INLINABLE toStream #-}
734toStream :: Monad m => Fold m a (SerialT Identity a)
735toStream = Fold (\f x -> return $ f . (x `K.cons`))
739-- This is more efficient than 'toStream'. toStream is exactly the same as
740-- reversing the stream after toStreamRev.
742-- | Buffers the input stream to a pure stream in the reverse order of the
745-- /Warning!/ working on large streams accumulated as buffers in memory could
746-- be very inefficient, consider using "Streamly.Array" instead.
750-- xn : ... : x2 : x1 : []
751{-# INLINABLE toStreamRev #-}
752toStreamRev :: Monad m => Fold m a (SerialT Identity a)
753toStreamRev = Fold (\xs x -> return $ x `S.cons` xs) (return S.nil) return
755------------------------------------------------------------------------------
757------------------------------------------------------------------------------
759------------------------------------------------------------------------------
761------------------------------------------------------------------------------
763-- | Like 'index', except with a more general 'Integral' argument
766{-# INLINABLE genericIndex #-}
767genericIndex :: (Integral i, Monad m) => i -> Fold m a (Maybe a)
768genericIndex i = Fold step (return $ Left' 0) done
781-- | Lookup the element at the given index.
784{-# INLINABLE index #-}
785index :: Monad m => Int -> Fold m a (Maybe a)
788-- | Extract the first element of the stream, if any.
791{-# INLINABLE head #-}
792head :: Monad m => Fold m a (Maybe a)
795-- | Returns the first element that satisfies the given predicate.
798{-# INLINABLE find #-}
799find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
800find predicate = Fold step (return Nothing') fromStrictMaybe
804 Nothing' -> if predicate a
809-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
810-- first pair where the key equals the given value @a@.
813{-# INLINABLE lookup #-}
814lookup :: (Eq a, Monad m) => a -> Fold m (a,b) (Maybe b)
815lookup a0 = Fold step (return Nothing') fromStrictMaybe
817 step x (a,b) = return $
819 Nothing' -> if a == a0
824-- | Convert strict 'Either'' to lazy 'Maybe'
825{-# INLINABLE hush #-}
826hush :: Either' a b -> Maybe b
827hush (Left' _) = Nothing
828hush (Right' b) = Just b
830-- | Returns the first index that satisfies the given predicate.
833{-# INLINABLE findIndex #-}
834findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
835findIndex predicate = Fold step (return $ Left' 0) (return . hush)
845-- | Returns the first index where a given value is found in the stream.
848{-# INLINABLE elemIndex #-}
849elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)
850elemIndex a = findIndex (a ==)
852------------------------------------------------------------------------------
854------------------------------------------------------------------------------
856-- | Return 'True' if the input stream is empty.
859{-# INLINABLE null #-}
860null :: Monad m => Fold m a Bool
861null = Fold (\_ _ -> return False) (return True) return
864-- > any p = lmap p or
866-- | Returns 'True' if any of the elements of a stream satisfies a predicate.
870any :: Monad m => (a -> Bool) -> Fold m a Bool
871any predicate = Fold (\x a -> return $ x || predicate a) (return False) return
873-- | Return 'True' if the given element is present in the stream.
876{-# INLINABLE elem #-}
877elem :: (Eq a, Monad m) => a -> Fold m a Bool
881-- > all p = lmap p and
883-- | Returns 'True' if all elements of a stream satisfy a predicate.
887all :: Monad m => (a -> Bool) -> Fold m a Bool
888all predicate = Fold (\x a -> return $ x && predicate a) (return True) return
890-- | Returns 'True' if the given element is not present in the stream.
893{-# INLINABLE notElem #-}
894notElem :: (Eq a, Monad m) => a -> Fold m a Bool
895notElem a = all (a /=)
897-- | Returns 'True' if all elements are 'True', 'False' otherwise
901and :: Monad m => Fold m Bool Bool
902and = Fold (\x a -> return $ x && a) (return True) return
904-- | Returns 'True' if any element is 'True', 'False' otherwise
908or :: Monad m => Fold m Bool Bool
909or = Fold (\x a -> return $ x || a) (return False) return
911------------------------------------------------------------------------------
912-- Scanning with a Fold
913------------------------------------------------------------------------------
915-- | Scan a stream using the given monadic fold.
919scanl' :: Monad m => Fold m a b -> SerialT m a -> SerialT m b
920scanl' (Fold step begin done) = P.scanlMx' step begin done
922-- | Postscan a stream using the given monadic fold.
925{-# INLINE postscanl' #-}
926postscanl' :: Monad m => Fold m a b -> SerialT m a -> SerialT m b
927postscanl' (Fold step begin done) = P.postscanlMx' step begin done
931------------------------------------------------------------------------------
933------------------------------------------------------------------------------
935-- | Include only those elements that pass a predicate.
937-- >>> FL.foldl (lfilter (> 5) FL.sum) [1..10]
941{-# INLINABLE lfilter #-}
942lfilter :: Monad m => (a -> Bool) -> Fold m a r -> Fold m a r
943lfilter f (Fold step begin done) = Fold step' begin done
945 step' x a = if f a then step x a else return x
947-- | Like 'lfilter' but with a monadic predicate.
950{-# INLINABLE lfilterM #-}
951lfilterM :: Monad m => (a -> m Bool) -> Fold m a r -> Fold m a r
952lfilterM f (Fold step begin done) = Fold step' begin done
956 if use then step x a else return x
958-- | Take first 'n' elements from the stream and discard the rest.
961{-# INLINABLE ltake #-}
962ltake :: Monad m => Int -> Fold m a b -> Fold m a b
963ltake n (Fold step initial done) = Fold step' initial' done'
965 initial' = fmap (Tuple' 0) initial
966 step' (Tuple' i r) a = do
970 return $ Tuple' (i + 1) res
971 else return $ Tuple' i r
972 done' (Tuple' _ r) = done r
974-- | Takes elements from the input as long as the predicate succeeds.
977{-# INLINABLE ltakeWhile #-}
978ltakeWhile :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a b
979ltakeWhile predicate (Fold step initial done) = Fold step' initial' done'
981 initial' = fmap Left' initial
982 step' (Left' r) a = do
984 then fmap Left' $ step r a
985 else return (Right' r)
987 done' (Left' r) = done r
988 done' (Right' r) = done r
990------------------------------------------------------------------------------
992------------------------------------------------------------------------------
994------------------------------------------------------------------------------
995-- Grouping without looking at elements
996------------------------------------------------------------------------------
998------------------------------------------------------------------------------
1000------------------------------------------------------------------------------
1003-- | @splitAt n f1 f2@ composes folds @f1@ and @f2@ such that first @n@
1004-- elements of its input are sent to fold @f1@ and the rest of the stream is
1005-- sent to fold @f2@.
1007-- > let splitAt_ n xs = FL.foldl' (FL.splitAt n FL.toList FL.toList) $ S.fromList xs
1009-- >>> splitAt_ 6 "Hello World!"
1010-- > ("Hello ","World!")
1012-- >>> splitAt_ (-1) [1,2,3]
1015-- >>> splitAt_ 0 [1,2,3]
1018-- >>> splitAt_ 1 [1,2,3]
1021-- >>> splitAt_ 3 [1,2,3]
1024-- >>> splitAt_ 4 [1,2,3]
1027-- This can be considered as a two-fold version of 'ltake' where we take both
1028-- the segments instead of discarding the leftover.
1031{-# INLINE splitAt #-}
1038splitAt n (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
1039 Fold step init extract
1041 init = Tuple3' <$> return n <*> initialL <*> initialR
1043 step (Tuple3' i xL xR) input =
1045 then stepL xL input >>= (\a -> return (Tuple3' (i - 1) a xR))
1046 else stepR xR input >>= (\b -> return (Tuple3' i xL b))
1048 extract (Tuple3' _ a b) = (,) <$> extractL a <*> extractR b
1050------------------------------------------------------------------------------
1052------------------------------------------------------------------------------
1054------------------------------------------------------------------------------
1055-- Generalized grouping
1056------------------------------------------------------------------------------
1058-- This combinator is the most general grouping combinator and can be used to
1059-- implement all other grouping combinators.
1061-- XXX check if this can implement the splitOn combinator i.e. we can slide in
1062-- new elements, slide out old elements and incrementally compute the hash.
1063-- Also, can we implement the windowed classification combinators using this?
1065-- In fact this is a parse. Instead of using a special return value in the fold
1066-- we are using a mapping function.
1068-- Note that 'scanl'' (usually followed by a map to extract the desired value
1069-- from the accumulator) can be used to realize many implementations e.g. a
1070-- sliding window implementation. A scan followed by a mapMaybe is also a good
1071-- pattern to express many problems where we want to emit a filtered output and
1072-- not emit an output on every input.
1074-- Passing on of the initial accumulator value to the next fold is equivalent
1075-- to returning the leftover concept.
1078-- | @groupScan splitter fold stream@ folds the input stream using @fold@.
1079-- @splitter@ is applied on the accumulator of the fold every time an item is
1080-- consumed by the fold. The fold continues until @splitter@ returns a 'Just'
1081-- value. A 'Just' result from the @splitter@ specifies a result to be emitted
1082-- in the output stream and the initial value of the accumulator for the next
1083-- group's fold. This allows us to control whether to start fresh for the next
1084-- fold or to continue from the previous fold's output.
1086{-# INLINE groupScan #-}
1088 :: (IsStream t, Monad m)
1089 => (x -> m (Maybe (b, x))) -> Fold m a x -> t m a -> t m b
1090groupScan split fold m = undefined
1093-- | Group the input stream into groups of @n@ elements each and then fold each
1094-- group using the provided fold function.
1096-- >> S.toList $ FL.chunksOf 2 FL.sum (S.enumerateFromTo 1 10)
1099-- This can be considered as an n-fold version of 'ltake' where we apply
1100-- 'ltake' repeatedly on the leftover stream until the stream exhausts.
1103{-# INLINE chunksOf #-}
1105 :: (IsStream t, Monad m)
1106 => Int -> Fold m a b -> t m a -> t m b
1107chunksOf n f m = D.fromStreamD $ D.groupsOf n f (D.toStreamD m)
1109-- | Transform a fold from a pure input to a 'Maybe' input, consuming only
1111lcatMaybes :: Monad m => Fold m a b -> Fold m (Maybe a) b
1112lcatMaybes = lfilter isJust . lmap fromJust
1114-- XXX we can implement this by repeatedly applying the 'lrunFor' fold.
1115-- XXX add this example after fixing the serial stream rate control
1116-- >>> S.toList $ S.take 5 $ sessionsOf 1 FL.sum $ constRate 2 $ S.enumerateFrom 1
1119-- | Group the input stream into windows of @n@ second each and then fold each
1120-- group using the provided fold function.
1123{-# INLINE sessionsOf #-}
1125 :: (IsStream t, MonadAsync m)
1126 => Double -> Fold m a b -> t m a -> t m b
1128 splitSuffixBy' isNothing (lcatMaybes f)
1129 (S.intersperseByTime n (return Nothing) (S.map Just xs))
1131------------------------------------------------------------------------------
1132-- Element Aware APIs
1133------------------------------------------------------------------------------
1135------------------------------------------------------------------------------
1137------------------------------------------------------------------------------
1139-- | Break the input stream into two groups, the first group takes the input as
1140-- long as the predicate applied to the first element of the stream and next
1141-- input element holds 'True', the second group takes the rest of the input.
1149_spanBy cmp (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
1150 Fold step init extract
1153 init = Tuple3' <$> initialL <*> initialR <*> return (Tuple' Nothing True)
1155 step (Tuple3' a b (Tuple' (Just frst) isFirstG)) input =
1156 if cmp frst input && isFirstG
1158 >>= (\a' -> return (Tuple3' a' b (Tuple' (Just frst) isFirstG)))
1160 >>= (\a' -> return (Tuple3' a a' (Tuple' Nothing False)))
1162 step (Tuple3' a b (Tuple' Nothing isFirstG)) input =
1165 >>= (\a' -> return (Tuple3' a' b (Tuple' (Just input) isFirstG)))
1167 >>= (\a' -> return (Tuple3' a a' (Tuple' Nothing False)))
1169 extract (Tuple3' a b _) = (,) <$> extractL a <*> extractR b
1171-- | Span as long as the predicate is 'True'. @span p f1 f2@ composes folds
1172-- @f1@ and @f2@ such that the composed fold continues sending the input to
1173-- @f1@ as long as the predicate @p@ is 'True'. The rest of the input is sent
1176-- > let span_ p xs = FL.foldl' (FL.span p FL.toList FL.toList) $ S.fromList xs
1178-- >>> span_ (< 1) [1,2,3]
1181-- >>> span_ (< 2) [1,2,3]
1184-- >>> span_ (< 4) [1,2,3]
1187-- This can be considered as a two-fold version of 'ltakeWhile' where we take
1188-- both the segments instead of discarding the leftover.
1198span p (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
1199 Fold step init extract
1202 init = Tuple3' <$> initialL <*> initialR <*> return True
1204 step (Tuple3' a b isFirstG) input =
1205 if isFirstG && p input
1206 then stepL a input >>= (\a' -> return (Tuple3' a' b True))
1207 else stepR b input >>= (\a' -> return (Tuple3' a a' False))
1209 extract (Tuple3' a b _) = (,) <$> extractL a <*> extractR b
1212-- > break p = span (not . p)
1214-- Break as soon as the predicate becomes 'True'. @break p f1 f2@ composes
1215-- folds @f1@ and @f2@ such that @f1@ stops receiving input as soon as the
1216-- predicate @p@ becomes 'True'. The rest of the input is sent to @f2@.
1218-- This is the binary version of 'splitBy'.
1220-- > let break_ p xs = FL.foldl' (FL.break p FL.toList FL.toList) $ S.fromList xs
1222-- >>> break_ (< 1) [3,2,1]
1225-- >>> break_ (< 2) [3,2,1]
1228-- >>> break_ (< 4) [3,2,1]
1239break p = span (not . p)
1241-- | Like 'spanBy' but applies the predicate in a rolling fashion i.e.
1242-- predicate is applied to the previous and the next input elements.
1243{-# INLINE _spanRollingBy #-}
1250_spanRollingBy cmp (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
1251 Fold step init extract
1254 init = Tuple3' <$> initialL <*> initialR <*> return Nothing
1256 step (Tuple3' a b (Just frst)) input =
1258 then stepL a input >>= (\a' -> return (Tuple3' a' b (Just input)))
1259 else stepR b input >>= (\b' -> return (Tuple3' a b' (Just input)))
1261 step (Tuple3' a b Nothing) input =
1262 stepL a input >>= (\a' -> return (Tuple3' a' b (Just input)))
1264 extract (Tuple3' a b _) = (,) <$> extractL a <*> extractR b
1266------------------------------------------------------------------------------
1268------------------------------------------------------------------------------
1270-- | @groupsBy cmp f $ S.fromList [a,b,c,...]@ assigns the element @a@ to the
1271-- first group, if @a \`cmp` b@ is 'True' then @b@ is also assigned to the same
1272-- group. If @a \`cmp` c@ is 'True' then @c@ is also assigned to the same
1273-- group and so on. When the comparison fails a new group is started. Each
1274-- group is folded using the fold @f@.
1276-- >>> S.toList $ FL.groupsBy (>) FL.toList $ S.fromList [1,3,7,0,2,5]
1277-- > [[1,3,7],[0,2,5]]
1281 :: (IsStream t, Monad m)
1286groupsBy cmp f m = D.fromStreamD $ D.groupsBy cmp f (D.toStreamD m)
1288-- | Unlike @groupsBy@ this function performs a rolling comparison of two
1289-- successive elements in the input stream. @groupsRollingBy cmp f $ S.fromList
1290-- [a,b,c,...]@ assigns the element @a@ to the first group, if @a \`cmp` b@ is
1291-- 'True' then @b@ is also assigned to the same group. If @b \`cmp` c@ is
1292-- 'True' then @c@ is also assigned to the same group and so on. When the
1293-- comparison fails a new group is started. Each group is folded using the fold
1296-- >>> S.toList $ FL.groupsRollingBy (\a b -> a + 1 == b) FL.toList $ S.fromList [1,2,3,7,8,9]
1297-- > [[1,2,3],[7,8,9]]
1301 :: (IsStream t, Monad m)
1306groupsRollingBy cmp f m = D.fromStreamD $ D.groupsRollingBy cmp f (D.toStreamD m)
1309-- > groups = groupsBy (==)
1310-- > groups = groupsRollingBy (==)
1312-- Groups a contiguous span of equal elements together in one group.
1314-- >>> S.toList $ FL.groups FL.toList $ S.fromList [1,1,2,2]
1318groups :: (IsStream t, Monad m, Eq a) => Fold m a b -> t m a -> t m b
1319groups = groupsBy (==)
1321------------------------------------------------------------------------------
1322-- Binary splitting on a separator
1323------------------------------------------------------------------------------
1326-- | Find the first occurrence of the specified sequence in the input stream
1327-- and break the input stream into two parts, the first part consisting of the
1328-- stream before the sequence and the second part consisting of the sequence
1329-- and the rest of the stream.
1331-- > let breakOn_ pat xs = FL.foldl' (FL.breakOn pat FL.toList FL.toList) $ S.fromList xs
1333-- >>> breakOn_ "dear" "Hello dear world!"
1334-- > ("Hello ","dear world!")
1336{-# INLINE breakOn #-}
1337breakOn :: Monad m => Array a -> Fold m a b -> Fold m a c -> Fold m a (b,c)
1338breakOn pat f m = undefined
1341------------------------------------------------------------------------------
1342-- N-ary split on a predicate
1343------------------------------------------------------------------------------
1345-- TODO: Use a Splitter configuration similar to the "split" package to make it
1346-- possible to express all splitting combinations. In general, we can have
1347-- infix/suffix/prefix/condensing of separators, dropping both leading/trailing
1348-- separators. We can have a single split operation taking the splitter config
1351-- | Split a stream on separator elements determined by a predicate, dropping
1352-- the separator. Separators are not considered part of stream segments on
1353-- either side of it instead they are treated as infixed between two stream
1354-- segments. For example, with @.@ as separator, @"a.b.c"@ would be parsed as
1355-- @["a","b","c"]@. When @.@ is in leading or trailing position it is still
1356-- considered as infixed, treating the first or the last segment as empty. For
1357-- example, @".a."@ would be parsed as @["","a",""]@. This operation is
1358-- opposite of 'intercalate'.
1360-- Let's use the following definition for illustration:
1362-- > splitBy_ p xs = S.toList $ FL.splitBy p (FL.toList) (S.fromList xs)
1364-- >>> splitBy_ (== '.') ""
1367-- >>> splitBy_ (== '.') "."
1370-- >>> splitBy_ (== '.') ".a"
1373-- >>> splitBy_ (== '.') "a."
1376-- >>> splitBy_ (== '.') "a.b"
1379-- >>> splitBy_ (== '.') "a..b"
1382-- This can be considered as an n-fold version of 'break' where we apply
1383-- 'break' successively on the input stream, dropping the first element
1384-- of the second segment after each break.
1387{-# INLINE splitBy #-}
1389 :: (IsStream t, Monad m)
1390 => (a -> Bool) -> Fold m a b -> t m a -> t m b
1391splitBy predicate f m =
1392 D.fromStreamD $ D.splitBy predicate f (D.toStreamD m)
1394-- | Like 'splitBy' but the separator is treated as part of the previous
1395-- stream segment (suffix). Therefore, when the separator is in trailing
1396-- position, no empty segment is considered to follow it. For example, @"a.b."@
1397-- would be parsed as @["a","b"]@ instead of @["a","b",""]@ as in the case of
1400-- > splitSuffixBy_ p xs = S.toList $ FL.splitSuffixBy p (FL.toList) (S.fromList xs)
1402-- >>> splitSuffixBy_ (== '.') ""
1405-- >>> splitSuffixBy_ (== '.') "."
1408-- >>> splitSuffixBy_ (== '.') "a"
1411-- >>> splitSuffixBy_ (== '.') ".a"
1414-- >>> splitSuffixBy_ (== '.') "a."
1417-- >>> splitSuffixBy_ (== '.') "a.b"
1420-- >>> splitSuffixBy_ (== '.') "a.b."
1423-- >>> splitSuffixBy_ (== '.') "a..b.."
1426-- > lines = splitSuffixBy (== '\n')
1428-- This can be considered as an n-fold version of 'breakPost' where we apply
1429-- 'breakPost' successively on the input stream, dropping the first element
1430-- of the second segment after each break.
1433{-# INLINE splitSuffixBy #-}
1435 :: (IsStream t, Monad m)
1436 => (a -> Bool) -> Fold m a b -> t m a -> t m b
1437splitSuffixBy predicate f m =
1438 D.fromStreamD $ D.splitSuffixBy predicate f (D.toStreamD m)
1440-- | Like 'splitBy' but ignores repeated separators or separators in leading
1441-- or trailing position. Therefore, @"..a..b.."@ would be parsed as
1442-- @["a","b"]@. In other words, it treats the input like words separated by
1443-- whitespace elements determined by the predicate.
1445-- > wordsBy' p xs = S.toList $ FL.wordsBy p (FL.toList) (S.fromList xs)
1447-- >>> wordsBy' (== ',') ""
1450-- >>> wordsBy' (== ',') ","
1453-- >>> wordsBy' (== ',') ",a,,b,"
1456-- > words = wordsBy isSpace
1459{-# INLINE wordsBy #-}
1461 :: (IsStream t, Monad m)
1462 => (a -> Bool) -> Fold m a b -> t m a -> t m b
1463wordsBy predicate f m =
1464 D.fromStreamD $ D.wordsBy predicate f (D.toStreamD m)
1466-- XXX we should express this using the Splitter config.
1468-- We can get splitSuffixBy' by appending the suffix to the output segments
1469-- produced by splitSuffixBy. However, it may add an additional suffix if the last
1470-- fragment did not have a suffix in the first place.
1472-- | Like 'splitSuffixBy' but keeps the suffix in the splits.
1474-- > splitSuffixBy'_ p xs = S.toList $ FL.splitSuffixBy' p (FL.toList) (S.fromList xs)
1476-- >>> splitSuffixBy'_ (== '.') ""
1479-- >>> splitSuffixBy'_ (== '.') "."
1482-- >>> splitSuffixBy'_ (== '.') "a"
1485-- >>> splitSuffixBy'_ (== '.') ".a"
1488-- >>> splitSuffixBy'_ (== '.') "a."
1491-- >>> splitSuffixBy'_ (== '.') "a.b"
1494-- >>> splitSuffixBy'_ (== '.') "a.b."
1497-- >>> splitSuffixBy'_ (== '.') "a..b.."
1498-- > ["a.",".","b.","."]
1500-- This can be considered as an n-fold version of 'breakPost' where we apply
1501-- 'breakPost' successively on the input stream.
1504{-# INLINE splitSuffixBy' #-}
1506 :: (IsStream t, Monad m)
1507 => (a -> Bool) -> Fold m a b -> t m a -> t m b
1508splitSuffixBy' predicate f m =
1509 D.fromStreamD $ D.splitSuffixBy' predicate f (D.toStreamD m)
1511------------------------------------------------------------------------------
1512-- Split on a delimiter sequence
1513------------------------------------------------------------------------------
1515-- Int list examples for splitOn:
1517-- >>> splitList [] [1,2,3,3,4]
1518-- > [[1],[2],[3],[3],[4]]
1520-- >>> splitList [5] [1,2,3,3,4]
1523-- >>> splitList [1] [1,2,3,3,4]
1526-- >>> splitList [4] [1,2,3,3,4]
1529-- >>> splitList [2] [1,2,3,3,4]
1532-- >>> splitList [3] [1,2,3,3,4]
1535-- >>> splitList [3,3] [1,2,3,3,4]
1538-- >>> splitList [1,2,3,3,4] [1,2,3,3,4]
1541-- | Split the stream on both sides of a separator sequence, dropping the
1544-- For illustration, let's define a function that operates on pure lists:
1547-- splitOn_ pat xs = S.toList $ FL.splitOn (A.fromList pat) (FL.toList) (S.fromList xs)
1550-- >>> splitOn_ "" "hello"
1551-- > ["h","e","l","l","o"]
1553-- >>> splitOn_ "hello" ""
1556-- >>> splitOn_ "hello" "hello"
1559-- >>> splitOn_ "x" "hello"
1562-- >>> splitOn_ "h" "hello"
1565-- >>> splitOn_ "o" "hello"
1568-- >>> splitOn_ "e" "hello"
1571-- >>> splitOn_ "l" "hello"
1574-- >>> splitOn_ "ll" "hello"
1577-- 'splitOn' is an inverse of 'intercalate'. The following law always holds:
1579-- > intercalate . splitOn == id
1581-- The following law holds when the separator is non-empty and contains none of
1582-- the elements present in the input lists:
1584-- > splitOn . intercalate == id
1586-- The following law always holds:
1588-- > concat . splitOn . intercalate == concat
1591{-# INLINE splitOn #-}
1593 :: (IsStream t, MonadIO m, Storable a, Enum a, Eq a)
1594 => Array a -> Fold m a b -> t m a -> t m b
1595splitOn patt f m = D.fromStreamD $ D.splitOn patt f (D.toStreamD m)
1598-- This can be implemented easily using Rabin Karp
1599-- | Split on any one of the given patterns.
1600{-# INLINE splitOnAny #-}
1602 :: (IsStream t, Monad m, Storable a, Integral a)
1603 => [Array a] -> Fold m a b -> t m a -> t m b
1604splitOnAny subseq f m = undefined -- D.fromStreamD $ D.splitOnAny f subseq (D.toStreamD m)
1607-- | Like 'splitSuffixBy' but the separator is a sequence of elements, instead
1608-- of a predicate for a single element.
1610-- > splitSuffixOn_ pat xs = S.toList $ FL.splitSuffixOn (A.fromList pat) (FL.toList) (S.fromList xs)
1612-- >>> splitSuffixOn_ "." ""
1615-- >>> splitSuffixOn_ "." "."
1618-- >>> splitSuffixOn_ "." "a"
1621-- >>> splitSuffixOn_ "." ".a"
1624-- >>> splitSuffixOn_ "." "a."
1627-- >>> splitSuffixOn_ "." "a.b"
1630-- >>> splitSuffixOn_ "." "a.b."
1633-- >>> splitSuffixOn_ "." "a..b.."
1636-- > lines = splitSuffixOn "\n"
1639{-# INLINE splitSuffixOn #-}
1641 :: (IsStream t, MonadIO m, Storable a, Enum a, Eq a)
1642 => Array a -> Fold m a b -> t m a -> t m b
1643splitSuffixOn patt f m =
1644 D.fromStreamD $ D.splitSuffixOn False patt f (D.toStreamD m)
1647-- | Like 'splitOn' but drops any empty splits.
1649{-# INLINE wordsOn #-}
1651 :: (IsStream t, Monad m, Storable a, Eq a)
1652 => Array a -> Fold m a b -> t m a -> t m b
1653wordsOn subseq f m = undefined -- D.fromStreamD $ D.wordsOn f subseq (D.toStreamD m)
1656-- XXX use a non-monadic intersperse to remove the MonadAsync constraint.
1658-- | Like 'splitOn' but splits the separator as well, as an infix token.
1660-- > splitOn'_ pat xs = S.toList $ FL.splitOn' (A.fromList pat) (FL.toList) (S.fromList xs)
1662-- >>> splitOn'_ "" "hello"
1663-- > ["h","","e","","l","","l","","o"]
1665-- >>> splitOn'_ "hello" ""
1668-- >>> splitOn'_ "hello" "hello"
1671-- >>> splitOn'_ "x" "hello"
1674-- >>> splitOn'_ "h" "hello"
1677-- >>> splitOn'_ "o" "hello"
1680-- >>> splitOn'_ "e" "hello"
1683-- >>> splitOn'_ "l" "hello"
1684-- > ["he","l","","l","o"]
1686-- >>> splitOn'_ "ll" "hello"
1690{-# INLINE splitOn' #-}
1692 :: (IsStream t, MonadAsync m, Storable a, Enum a, Eq a)
1693 => Array a -> Fold m a b -> t m a -> t m b
1694splitOn' patt f m = S.intersperseM (foldl' f (A.read patt)) $ splitOn patt f m
1696-- | Like 'splitSuffixOn' but keeps the suffix intact in the splits.
1698-- > splitSuffixOn'_ pat xs = S.toList $ FL.splitSuffixOn' (A.fromList pat) (FL.toList) (S.fromList xs)
1700-- >>> splitSuffixOn'_ "." ""
1703-- >>> splitSuffixOn'_ "." "."
1706-- >>> splitSuffixOn'_ "." "a"
1709-- >>> splitSuffixOn'_ "." ".a"
1712-- >>> splitSuffixOn'_ "." "a."
1715-- >>> splitSuffixOn'_ "." "a.b"
1718-- >>> splitSuffixOn'_ "." "a.b."
1721-- >>> splitSuffixOn'_ "." "a..b.."
1722-- > ["a.",".","b.","."]
1725{-# INLINE splitSuffixOn' #-}
1727 :: (IsStream t, MonadIO m, Storable a, Enum a, Eq a)
1728 => Array a -> Fold m a b -> t m a -> t m b
1729splitSuffixOn' patt f m =
1730 D.fromStreamD $ D.splitSuffixOn True patt f (D.toStreamD m)
1733-- This can be implemented easily using Rabin Karp
1734-- | Split post any one of the given patterns.
1735{-# INLINE splitSuffixOnAny #-}
1737 :: (IsStream t, Monad m, Storable a, Integral a)
1738 => [Array a] -> Fold m a b -> t m a -> t m b
1739splitSuffixOnAny subseq f m = undefined
1740 -- D.fromStreamD $ D.splitPostAny f subseq (D.toStreamD m)
1743------------------------------------------------------------------------------
1744-- Reorder in sequence
1745------------------------------------------------------------------------------
1748-- Buffer until the next element in sequence arrives. The function argument
1749-- determines the difference in sequence numbers. This could be useful in
1750-- implementing sequenced streams, for example, TCP reassembly.
1751{-# INLINE reassembleBy #-}
1753 :: (IsStream t, Monad m)
1758reassembleBy = undefined
1761------------------------------------------------------------------------------
1763------------------------------------------------------------------------------
1765-- | Distribute one copy of the stream to each fold and zip the results.
1768-- |-------Fold m a b--------|
1769-- ---stream m a---| |---m (b,c)
1770-- |-------Fold m a c--------|
1772-- >>> FL.foldl' (FL.tee FL.sum FL.length) (S.enumerateFromTo 1.0 100.0)
1777tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b,c)
1778tee f1 f2 = (,) <$> f1 <*> f2
1780{-# INLINE foldNil #-}
1781foldNil :: Monad m => Fold m a [b]
1782foldNil = Fold step begin done where
1784 step _ _ = return []
1787{-# INLINE foldCons #-}
1788foldCons :: Monad m => Fold m a b -> Fold m a [b] -> Fold m a [b]
1789foldCons (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
1790 Fold step begin done
1794 begin = Tuple' <$> beginL <*> beginR
1795 step (Tuple' xL xR) a = Tuple' <$> stepL xL a <*> stepR xR a
1796 done (Tuple' xL xR) = (:) <$> (doneL xL) <*> (doneR xR)
1798-- XXX use "List" instead of "[]"?, use Array for output to scale it to a large
1799-- number of consumers?
1801-- | Distribute one copy of the stream to each fold and collect the results in
1806-- |-------Fold m a b--------|
1807-- ---stream m a---| |---m [b]
1808-- |-------Fold m a b--------|
1813-- >>> FL.foldl' (FL.distribute [FL.sum, FL.length]) (S.enumerateFromTo 1 5)
1816-- This is the consumer side dual of the producer side 'sequence' operation.
1819{-# INLINE distribute #-}
1820distribute :: Monad m => [Fold m a b] -> Fold m a [b]
1821distribute [] = foldNil
1822distribute (x:xs) = foldCons x (distribute xs)
1824------------------------------------------------------------------------------
1826------------------------------------------------------------------------------
1828-- | Partition the input over two folds using an 'Either' partitioning
1833-- |-------Fold b x--------|
1834-- -----stream m a --> (Either b c)----| |----(x,y)
1835-- |-------Fold c y--------|
1838-- Send input to either fold randomly:
1840-- >>> import System.Random (randomIO)
1841-- >>> randomly a = randomIO >>= \x -> return $ if x then Left a else Right a
1842-- >>> FL.foldl' (FL.partitionByM randomly FL.length FL.length) (S.enumerateFromTo 1 100)
1845-- Send input to the two folds in a proportion of 2:1:
1848-- import Data.IORef (newIORef, readIORef, writeIORef)
1849-- proportionately m n = do
1850-- ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
1851-- return $ \\a -> do
1852-- r <- readIORef ref
1853-- writeIORef ref $ tail r
1857-- f <- proportionately 2 1
1858-- r <- FL.foldl' (FL.partitionByM f FL.length FL.length) (S.enumerateFromTo (1 :: Int) 100)
1865-- This is the consumer side dual of the producer side 'mergeBy' operation.
1868{-# INLINE partitionByM #-}
1869partitionByM :: Monad m
1870 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1871partitionByM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
1873 Fold step begin done
1877 begin = Tuple' <$> beginL <*> beginR
1878 step (Tuple' xL xR) a = do
1881 Left b -> Tuple' <$> stepL xL b <*> return xR
1882 Right c -> Tuple' <$> return xL <*> stepR xR c
1883 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
1885-- Note: we could use (a -> Bool) instead of (a -> Either b c), but the latter
1886-- makes the signature clearer as to which case belongs to which fold.
1887-- XXX need to check the performance in both cases.
1889-- | Same as 'partitionByM' but with a pure partition function.
1891-- Count even and odd numbers in a stream:
1894-- >>> let f = FL.partitionBy (\\n -> if even n then Left n else Right n)
1895-- (fmap (("Even " ++) . show) FL.length)
1896-- (fmap (("Odd " ++) . show) FL.length)
1897-- in FL.foldl' f (S.enumerateFromTo 1 100)
1898-- ("Even 50","Odd 50")
1902{-# INLINE partitionBy #-}
1903partitionBy :: Monad m
1904 => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1905partitionBy f = partitionByM (return . f)
1907-- | Compose two folds such that the combined fold accepts a stream of 'Either'
1908-- and routes the 'Left' values to the first fold and 'Right' values to the
1911-- > partition = partitionBy id
1914{-# INLINE partition #-}
1916 => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)
1917partition = partitionBy id
1920-- | Send one item to each fold in a round-robin fashion. This is the consumer
1921-- side dual of producer side 'mergeN' operation.
1923-- partitionN :: Monad m => [Fold m a b] -> Fold m a [b]
1924-- partitionN fs = Fold step begin done
1927-- Demultiplex an input element into a number of typed variants. We want to
1928-- statically restrict the target values within a set of predefined types, an
1929-- enumeration of a GADT. We also want to make sure that the Map contains only
1930-- those types and the full set of those types. Instead of Map it should
1931-- probably be a lookup-table using an array and not in GC memory.
1933-- This is the consumer side dual of the producer side 'mux' operation (XXX to
1936-- | Split the input stream based on a key field and fold each split using a
1937-- specific fold collecting the results in a map from the keys to the results.
1938-- Useful for cases like protocol handlers to handle different type of packets
1939-- using different handlers.
1943-- |-------Fold m a b
1944-- -----stream m a-----Map-----|
1945-- |-------Fold m a b
1951demuxWith :: (Monad m, Ord k)
1952 => (a -> k) -> Map k (Fold m a b) -> Fold m a (Map k b)
1953demuxWith f kv = Fold step initial extract
1959 -- XXX should we raise an exception in Nothing case?
1960 -- Ideally we should enforce that it is a total map over k so that look
1962 -- XXX we could use a monadic update function for a single lookup and
1963 -- update in the map.
1965 in case Map.lookup k mp of
1966 Nothing -> return mp
1967 Just (Fold step' acc extract') -> do
1968 !r <- acc >>= \x -> step' x a
1969 return $ Map.insert k (Fold step' (return r) extract') mp
1970 extract = mapM (\(Fold _ acc e) -> acc >>= e)
1972-- | Fold a stream of key value pairs using a map of specific folds for each
1973-- key into a map from keys to the results of fold outputs of the corresponding
1977-- > let table = Data.Map.fromList [(\"SUM", FL.sum), (\"PRODUCT", FL.product)]
1978-- input = S.fromList [(\"SUM",1),(\"PRODUCT",2),(\"SUM",3),(\"PRODUCT",4)]
1979-- in FL.foldl' (FL.demux table) input
1985demux :: (Monad m, Ord k)
1986 => Map k (Fold m a b) -> Fold m (k, a) (Map k b)
1987demux fs = demuxWith fst (Map.map (lmap snd) fs)
1989-- | Split the input stream based on a key field and fold each split using a
1990-- specific fold without collecting the results. Useful for cases like protocol
1991-- handlers to handle different type of packets.
1995-- |-------Fold m a ()
1996-- -----stream m a-----Map-----|
1997-- |-------Fold m a ()
2005-- demuxWith_ can be slightly faster than demuxWith because we do not need to
2006-- update the Map in this case. This may be significant only if the map is
2008demuxWith_ :: (Monad m, Ord k)
2009 => (a -> k) -> Map k (Fold m a b) -> Fold m a ()
2010demuxWith_ f kv = Fold step initial extract
2014 initial = mapM (\(Fold s i e) -> i >>= \r -> return (Fold s (return r) e)) kv
2016 -- XXX should we raise an exception in Nothing case?
2017 -- Ideally we should enforce that it is a total map over k so that look
2019 case Map.lookup (f a) mp of
2020 Nothing -> return mp
2021 Just (Fold step' acc _) -> do
2022 _ <- acc >>= \x -> step' x a
2024 extract mp = mapM (\(Fold _ acc e) -> acc >>= e) mp >> return ()
2026-- | Given a stream of key value pairs and a map from keys to folds, fold the
2027-- values for each key using the corresponding folds, discarding the outputs.
2030-- > let prn = FL.drainBy print
2031-- > let table = Data.Map.fromList [(\"ONE", prn), (\"TWO", prn)]
2032-- input = S.fromList [(\"ONE",1),(\"TWO",2)]
2033-- in FL.foldl' (FL.demux_ table) input
2039demux_ :: (Monad m, Ord k) => Map k (Fold m a ()) -> Fold m (k, a) ()
2040demux_ fs = demuxWith_ fst (Map.map (lmap snd) fs)
2042-- XXX instead of a Map we could yield the results as a pure stream as they
2043-- complete. We could then concatMap the fold results to implement the
2044-- windowing combinators.
2046-- | Split the input stream based on a key field and fold each split using the
2047-- given fold. Useful for map/reduce, bucketizing the input in different bins
2048-- or for generating histograms.
2051-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
2052-- in FL.foldl' (FL.classify FL.toListRev) input
2053-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
2057classifyWith :: (Monad m, Ord k) => (a -> k) -> Fold m a b -> Fold m a (Map k b)
2058classifyWith f (Fold step initial extract) = Fold step' initial' extract'
2062 initial' = return Map.empty
2065 in case Map.lookup k kv of
2069 return $ Map.insert k r kv
2072 return $ Map.insert k r kv
2073 extract' = mapM extract
2075-- | Given an input stream of key value pairs and a fold for values, fold all
2076-- the values belonging to each key. Useful for map/reduce, bucketizing the
2077-- input in different bins or for generating histograms.
2080-- > let input = S.fromList [(\"ONE",1),(\"ONE",1.1),(\"TWO",2), (\"TWO",2.2)]
2081-- in FL.foldl' (FL.classify FL.toListRev) input
2082-- fromList [(\"ONE",[1.1,1.0]),(\"TWO",[2.2,2.0])]
2087-- > classify fld = classifyWith fst (lmap snd fld)
2090classify :: (Monad m, Ord k) => Fold m a b -> Fold m (k, a) (Map k b)
2091classify fld = classifyWith fst (lmap snd fld)
2093------------------------------------------------------------------------------
2095------------------------------------------------------------------------------
2097-- | Like 'unzipWith' but with a monadic splitter function.
2100{-# INLINE unzipWithM #-}
2101unzipWithM :: Monad m
2102 => (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
2103unzipWithM f (Fold stepL beginL doneL) (Fold stepR beginR doneR) =
2104 Fold step begin done
2108 step (Tuple' xL xR) a = do
2110 Tuple' <$> stepL xL b <*> stepR xR c
2111 begin = Tuple' <$> beginL <*> beginR
2112 done (Tuple' xL xR) = (,) <$> doneL xL <*> doneR xR
2114-- | Split elements in the input stream into two parts using a pure splitter
2115-- function, direct each part to a different fold and zip the results.
2118{-# INLINE unzipWith #-}
2120 => (a -> (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
2121unzipWith f = unzipWithM (return . f)
2123-- | Send the elements of tuples in a stream of tuples through two different
2128-- |-------Fold a x--------|
2129-- -----Stream m x----(a,b)--| |----m (x,y)
2130-- |-------Fold b y--------|
2134-- This is the consumer side dual of the producer side 'zip' operation.
2137unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a,b) (x,y)
2140------------------------------------------------------------------------------
2142------------------------------------------------------------------------------
2144-- | Modify the fold such that when the fold is done, instead of returning the
2145-- accumulator, it returns a fold. The returned fold starts from where we left
2146-- i.e. it uses the last accumulator value as the initial value of the
2147-- accumulator. Thus we can resume the fold later and feed it more input.
2150-- > more <- FL.foldl (FL.duplicate FL.sum) (S.enumerateFromTo 1 10)
2151-- > evenMore <- FL.foldl (FL.duplicate more) (S.enumerateFromTo 11 20)
2152-- > FL.foldl evenMore (S.enumerateFromTo 21 30)
2156{-# INLINABLE duplicate #-}
2157duplicate :: Applicative m => Fold m a b -> Fold m a (Fold m a b)
2158duplicate (Fold step begin done) =
2159 Fold step begin (\x -> pure (Fold step (pure x) done))
2162-- All the stream flattening transformations can also be applied to a fold
2165-- | This can be used to apply all the stream generation operations on folds.
2166lconcatMap ::(IsStream t, Monad m) => (a -> t m b)
2169lconcatMap s f1 f2 = undefined
2171-- All the grouping transformation that we apply to a stream can also be
2172-- applied to a fold input stream.
2174-- | Group the input elements of a fold input stream by some criterion and fold
2175-- each group using a given fold before its fed to the fold.
2177-- For example, we can copy and distribute a stream to multiple folds and then
2178-- in each fold we can group the input differently e.g. by one second, one
2179-- minute and one hour windows respectively and fold each resulting stream of
2184-- -----Fold m a b----|-Fold n a c-|-Fold n a c-|-...-|----Fold m a c
2187lchunksOf :: Int -> Fold m a b -> Fold m b c -> Fold m a c
2188lchunksOf n f1 f2 = undefined
2191------------------------------------------------------------------------------
2192-- Windowed classification
2193------------------------------------------------------------------------------
2195-- We divide the stream into windows or chunks in space or time and each window
2196-- can be associated with a key, all events associated with a particular key in
2197-- the window can be folded to a single result. The stream can be split into
2198-- windows by size or by using a split predicate on the elements in the stream.
2199-- For example, when we receive a closing flag, we can close the window.
2201-- A "chunk" is a space window and a "session" is a time window. Are there any
2202-- other better short words to describe them. An alternative is to use
2203-- "swindow" and "twindow". Another word for "session" could be "spell".
2205-- TODO: To mark the position in space or time we can have Indexed or
2206-- TimeStamped types. That can make it easy to deal with the position indices
2209------------------------------------------------------------------------------
2210-- Keyed Sliding Windows
2211------------------------------------------------------------------------------
2214{-# INLINABLE classifySlidingChunks #-}
2215classifySlidingChunks
2216 :: (IsStream t, MonadAsync m, Ord k)
2217 => Int -- ^ window size
2218 -> Int -- ^ window slide
2219 -> Fold m a b -- ^ Fold to be applied to window events
2220 -> t m (k, a, Bool) -- ^ window key, data, close event
2222classifySlidingChunks wsize wslide (Fold step initial extract) str
2225-- XXX Another variant could be to slide the window on an event, e.g. in TCP we
2226-- slide the send window when an ack is received and we slide the receive
2227-- window when a sequence is complete. Sliding is stateful in case of TCP,
2228-- sliding releases the send buffer or makes data available to the user from
2229-- the receive buffer.
2230{-# INLINABLE classifySlidingSessions #-}
2231classifySlidingSessions
2232 :: (IsStream t, MonadAsync m, Ord k)
2233 => Double -- ^ timer tick in seconds
2234 -> Double -- ^ time window size
2235 -> Double -- ^ window slide
2236 -> Fold m a b -- ^ Fold to be applied to window events
2237 -> t m (k, a, Bool, AbsTime) -- ^ window key, data, close flag, timestamp
2239classifySlidingSessions tick interval slide (Fold step initial extract) str
2243------------------------------------------------------------------------------
2244-- Sliding Window Buffers
2245------------------------------------------------------------------------------
2247-- These buffered versions could be faster than concurrent incremental folds of
2248-- all overlapping windows as in many cases we may not need all the values to
2249-- compute the fold, we can just compute the result using the old value and new
2250-- value. However, we may need the buffer once in a while, for example for
2251-- string search we usually compute the hash incrementally but when the hash
2252-- matches the hash of the pattern we need to compare the whole string.
2254-- XXX we should be able to implement sequence based splitting combinators
2255-- using this combinator.
2258-- | Buffer n elements of the input in a ring buffer. When t new elements are
2259-- collected, slide the window to remove the same number of oldest elements,
2260-- insert the new elements, and apply an incremental fold on the sliding
2261-- window, supplying the outgoing elements, the new ring buffer as arguments.
2263 :: (IsStream t, Monad m, Ord a, Storable a)
2264 => Int -- window size
2265 -> Int -- window slide
2266 -> Fold m (Ring a, Array a) b
2269slidingChunkBuffer = undefined
2271-- Buffer n seconds worth of stream elements of the input in a radix tree.
2272-- Every t seconds, remove the items that are older than n seconds, and apply
2273-- an incremental fold on the sliding window, supplying the outgoing elements,
2274-- and the new radix tree buffer as arguments.
2276 :: (IsStream t, Monad m, Ord a, Storable a)
2277 => Int -- window size
2279 -> Fold m (RTree a, Array a) b
2282slidingSessionBuffer = undefined
2285------------------------------------------------------------------------------
2286-- Keyed Session Windows
2287------------------------------------------------------------------------------
2290-- | Keyed variable size space windows. Close the window if we do not receive a
2291-- window event in the next "spaceout" elements.
2292{-# INLINABLE classifyChunksBy #-}
2294 :: (IsStream t, MonadAsync m, Ord k)
2295 => Int -- ^ window spaceout (spread)
2296 -> Bool -- ^ reset the spaceout when a chunk window element is received
2297 -> Fold m a b -- ^ Fold to be applied to chunk window elements
2298 -> t m (k, a, Bool) -- ^ chunk key, data, last element
2300classifyChunksBy spanout reset (Fold step initial extract) str = undefined
2302-- | Like 'classifyChunksOf' but the chunk size is reset if an element is
2303-- received within the chunk size window. The chunk gets closed only if no
2304-- element is received within the chunk window.
2306{-# INLINABLE classifyKeepAliveChunks #-}
2307classifyKeepAliveChunks
2308 :: (IsStream t, MonadAsync m, Ord k)
2309 => Int -- ^ window spaceout (spread)
2310 -> Fold m a b -- ^ Fold to be applied to chunk window elements
2311 -> t m (k, a, Bool) -- ^ chunk key, data, last element
2313classifyKeepAliveChunks spanout = classifyChunksBy spanout True
2316-- | @classifySessionsBy tick timeout reset f stream@ groups together all input
2317-- stream elements that belong to the same session. @timeout@ is the maximum
2318-- lifetime of a session in seconds. All elements belonging to a session are
2319-- purged after this duration. If "reset" is 'Ture' then the timeout is reset
2320-- after every event received in the session. Session duration is measured
2321-- using the timestamp of the first element seen for that session. To detect
2322-- session timeouts, a monotonic event time clock is maintained using the
2323-- timestamps seen in the inputs and a timer with a tick duration specified by
2326-- @session key@ is a key that uniquely identifies the session for the given
2327-- element, @timestamp@ characterizes the time when the input element was
2328-- generated, this is an absolute time measured from some @Epoch@. @session
2329-- close@ is a boolean indicating whether this element marks the closing of the
2330-- session. When an input element with @session close@ set to @True@ is seen
2331-- the session is purged immediately.
2333-- All the input elements belonging to a session are collected using the fold
2334-- @f@. The session key and the fold result are emitted in the output stream
2335-- when the session is purged either via the session close event or via the
2336-- session liftime timeout.
2339{-# INLINABLE classifySessionsBy #-}
2341 :: (IsStream t, MonadAsync m, Ord k)
2342 => Double -- ^ timer tick in seconds
2343 -> Double -- ^ session timeout
2344 -> Bool -- ^ reset the timeout when an event is received
2345 -> Fold m a b -- ^ Fold to be applied to session events
2346 -> t m (k, a, Bool, AbsTime) -- ^ session key, timestamp, close event, data
2348classifySessionsBy tick timeout reset (Fold step initial extract) str =
2349 S.concatMap (\(Tuple4' _ _ _ s) -> s) $ S.scanlM' sstep szero stream
2353 timeoutMs = toRelTime (round (timeout * 1000) :: MilliSecond64)
2354 tickMs = toRelTime (round (tick * 1000) :: MilliSecond64)
2355 szero = Tuple4' (toAbsTime (0 :: MilliSecond64)) H.empty Map.empty S.nil
2357 -- Got a new stream input element
2358 sstep (Tuple4' evTime hp mp _) (Just (key, a, closing, ts)) =
2359 -- XXX we should use a heap in pinned memory to scale it to a large
2362 -- deleting a key from the heap is expensive, so we never delete a
2363 -- key, we just purge it from the Map and it gets purged from the
2364 -- heap on timeout. We just need an extra lookup in the Map when
2365 -- the key is purged from the heap, that should not be expensive.
2367 -- To detect session inactivity we keep a timestamp of the latest event
2368 -- in the Map along with the fold result. When we purge the session
2369 -- from the heap we match the timestamp in the heap with the timestamp
2370 -- in the Map, if the latest timestamp is newer and has not expired we
2371 -- reinsert the key in the heap.
2373 -- XXX if the key is an Int, we can also use an IntMap for slightly
2374 -- better performance.
2376 let accumulate v = do
2377 Tuple' _ old <- maybe (initial >>= return . Tuple' ts) return v
2379 return $ Tuple' ts new
2382 let (r, mp') = Map.updateLookupWithKey (\_ _ -> Nothing) key mp
2383 Tuple' _ acc <- accumulate r
2385 return $ Tuple4' evTime hp mp' (S.yield (key, res))
2387 let r = Map.lookup key mp
2389 let mp' = Map.insert key acc mp
2393 let expiry = addToAbsTime ts timeoutMs
2394 in H.insert (Entry expiry key) hp
2396 -- Event time is maintained as monotonically increasing
2397 -- time. If we have lagged behind any of the timestamps
2398 -- seen then we increase it to match the latest time seen
2399 -- in the timestamps. We also increase it on timer ticks.
2400 return $ Tuple4' (max evTime ts) hp' mp' S.nil
2402 -- Got a timer tick event
2403 -- XXX can we yield the entries without accumulating them?
2404 sstep (Tuple4' evTime heap sessions _) Nothing = do
2405 (hp', mp', out) <- go heap sessions S.nil
2406 return $ Tuple4' curTime hp' mp' out
2410 curTime = addToAbsTime evTime tickMs
2412 let hres = H.uncons hp
2414 Just (Entry ts key, hp') -> do
2415 let duration = diffAbsTime curTime ts
2416 if duration >= timeoutMs
2418 let (r, mp') = Map.updateLookupWithKey
2419 (\_ _ -> Nothing) key mp
2421 Nothing -> go hp' mp' out
2422 Just (Tuple' latestTS acc) -> do
2423 let dur = diffAbsTime curTime latestTS
2424 if dur >= timeoutMs || not reset
2427 go hp' mp' ((key, sess) `S.cons` out)
2429 -- reset the session timeout
2430 let expiry = addToAbsTime latestTS timeoutMs
2431 hp'' = H.insert (Entry expiry key) hp'
2432 mp'' = Map.insert key (Tuple' latestTS acc) mp'
2434 else return (hp, mp, out)
2435 Nothing -> return (hp, mp, out)
2437 -- merge timer events in the stream
2438 stream = S.map Just str `parallel` S.repeatM timer
2440 liftIO $ threadDelay (round $ tick * 1000000)
2443-- | Like 'classifySessionsOf' but the session is kept alive if an event is
2444-- received within the session window. The session times out and gets closed
2445-- only if no event is received within the specified session window size.
2448{-# INLINABLE classifyKeepAliveSessions #-}
2449classifyKeepAliveSessions
2450 :: (IsStream t, MonadAsync m, Ord k)
2451 => Double -- ^ session inactive timeout
2452 -> Fold m a b -- ^ Fold to be applied to session payload data
2453 -> t m (k, a, Bool, AbsTime) -- ^ session key, data, close flag, timestamp
2455classifyKeepAliveSessions timeout = classifySessionsBy 1 timeout True
2457------------------------------------------------------------------------------
2458-- Keyed tumbling windows
2459------------------------------------------------------------------------------
2461-- Tumbling windows is a special case of sliding windows where the window slide
2462-- is the same as the window size. Or it can be a special case of session
2463-- windows where the reset flag is set to False.
2465-- XXX instead of using the early termination flag in the stream, we can use an
2466-- early terminating fold instead.
2469-- | Split the stream into fixed size chunks of specified size. Within each
2470-- such chunk fold the elements in buckets identified by the keys. A particular
2471-- bucket fold can be terminated early if a closing flag is encountered in an
2472-- element for that key.
2475{-# INLINABLE classifyChunksOf #-}
2477 :: (IsStream t, MonadAsync m, Ord k)
2478 => Int -- ^ window size
2479 -> Fold m a b -- ^ Fold to be applied to window events
2480 -> t m (k, a, Bool) -- ^ window key, data, close event
2482classifyChunksOf wsize = classifyChunksBy wsize False
2485-- | Split the stream into fixed size time windows of specified interval in
2486-- seconds. Within each such window, fold the elements in buckets identified by
2487-- the keys. A particular bucket fold can be terminated early if a closing flag
2488-- is encountered in an element for that key. Once a fold is terminated the key
2489-- and value for that bucket are emitted in the output stream.
2491-- Session @timestamp@ in the input stream is an absolute time from some epoch,
2492-- characterizing the time when the input element was generated. To detect
2493-- session window end, a monotonic event time clock is maintained synced with
2494-- the timestamps with a clock resolution of 1 second.
2497{-# INLINABLE classifySessionsOf #-}
2499 :: (IsStream t, MonadAsync m, Ord k)
2500 => Double -- ^ time window size
2501 -> Fold m a b -- ^ Fold to be applied to window events
2502 -> t m (k, a, Bool, AbsTime) -- ^ window key, data, close flag, timestamp
2504classifySessionsOf interval = classifySessionsBy 1 interval False
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