2-- Module : Streamly.Internal.Data.Fold
3-- Copyright : (c) 2019 Composewell Technologies
4-- (c) 2013 Gabriel Gonzalez
6-- Maintainer : streamly@composewell.com
7-- Stability : experimental
10-- See "Streamly.Data.Fold" for an overview and
11-- "Streamly.Internal.Data.Fold.Types" for design notes.
13-- IMPORTANT: keep the signatures consistent with the folds in Streamly.Prelude
15module Streamly.Internal.Data.Fold
22 -- | Which constructor to use?
24 -- * @foldl*@: If the fold never terminates i.e. does not use the 'Done'
25 -- constructor otherwise use the @mkFold@ variants.
26 -- * @*M@: Use the @M@ suffix variants if any of the step, initial, or
27 -- extract function is monadic, otherwise use the pure variants.
28 -- * @*_@: Use the @_@ suffix variants if the extract function is 'id' or
47 -- *** Semigroups and Monoids
69 -- *** Saturating Reducers
70 -- | 'product' terminates if it becomes 0. Other folds can theoretically
71 -- saturate on bounded types, and therefore terminate, however, they will
72 -- run forever on unbounded types like Integer/Double.
81 -- | Avoid using these folds in scalable or performance critical
82 -- applications, they buffer all the input in GC memory which can be
83 -- detrimental to performance if the input is large.
91 -- ** Terminating Folds
116 -- ** Transforming the Monad
120 -- ** Mapping on output
123 -- ** Mapping on Input
141 -- ** Mapping Filters
146 -- ** Scanning Filters
152 -- | Insertion adds more elements to the stream.
180 -- , splitIn -- sessionN
182 -- ** Parallel Distribution
191 -- ** Parallel Alternative
203 -- | Direct values in the input stream to different folds using an n-ary
205 , demux -- XXX rename this to demux_
207 , demuxDefault -- XXX rename this to demux
213 -- | In an input stream of key value pairs fold values for different keys
214 -- in individual output buckets using the given fold.
223 -- These two can be expressed using lmap/lmapM and unzip
243 -- | Normally you would run a fold to completion by supplying it a stream,
244 -- e.g. using 'Stream.fold'. However, you could also run a fold partially
245 -- by using 'duplicate' on it and then running it with a stream.
246 -- Alternatively, 'initialize', 'snoc' and 'finish' can be used to run a
247 -- fold incrementally, however, that may not be the most efficient way to
260import Data.Bifunctor (first)
261import Data.Either (isLeft, isRight)
262import Data.Functor.Identity (Identity(..))
263import Data.Int (Int64)
264import Data.Map.Strict (Map)
265import Data.Maybe (isJust, fromJust)
266#if __GLASGOW_HASKELL__ < 804
267import Data.Semigroup (Semigroup((<>)))
269import Streamly.Internal.BaseCompat (fromLeft, fromRight)
270import Streamly.Internal.Data.Either.Strict
271 (Either'(..), fromLeft', fromRight', isLeft', isRight')
272import Streamly.Internal.Data.Pipe.Type (Pipe (..), PipeState(..))
273import Streamly.Internal.Data.Tuple.Strict (Tuple'(..), Tuple3'(..))
274import Streamly.Internal.Data.Stream.Serial (SerialT(..))
276import qualified Data.IntSet as IntSet
277import qualified Data.Map.Strict as Map
278import qualified Data.Set as Set
279import qualified Streamly.Internal.Data.Pipe.Type as Pipe
280-- import qualified Streamly.Internal.Data.Stream.IsStream.Enumeration as Stream
281import qualified Prelude
284 ( filter, foldl1, drop, dropWhile, take, takeWhile, zipWith
285 , foldl, foldr, map, mapM_, sequence, all, any, sum, product, elem
286 , notElem, maximum, minimum, head, last, tail, length, null
287 , reverse, iterate, init, and, or, lookup, (!!)
288 , scanl, scanl1, replicate, concatMap, mconcat, foldMap, unzip
289 , span, splitAt, break, mapM, zip)
290import Streamly.Internal.Data.Fold.Type
294-- >>> :set -package streamly
295-- >>> import Prelude hiding (break, map, span, splitAt)
296-- >>> import qualified Streamly.Prelude as Stream
297-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, foldMany)
298-- >>> import qualified Streamly.Data.Fold as Fold
299-- >>> import qualified Streamly.Internal.Data.Fold as Fold
300-- >>> import qualified Streamly.Internal.Data.Fold.Type as Fold
301-- >>> import qualified Streamly.Internal.Data.Parser as Parser
302-- >>> import Streamly.Internal.Data.Stream.Serial (SerialT(..))
303-- >>> import Data.IORef (newIORef, readIORef, writeIORef)
305------------------------------------------------------------------------------
307------------------------------------------------------------------------------
309-- | Change the underlying monad of a fold
312hoist :: (forall x. m x -> n x) -> Fold m a b -> Fold n a b
313hoist f (Fold step initial extract) =
314 Fold (\x a -> f $ step x a) (f initial) (f . extract)
316-- | Adapt a pure fold to any monad
318-- > generally = Fold.hoist (return . runIdentity)
321generally :: Monad m => Fold Identity a b -> Fold m a b
322generally = hoist (return . runIdentity)
324------------------------------------------------------------------------------
325-- Transformations on fold inputs
326------------------------------------------------------------------------------
328-- | Flatten the monadic output of a fold to pure output.
331{-# DEPRECATED sequence "Use \"rmapM id\" instead" #-}
332{-# INLINE sequence #-}
333sequence :: Monad m => Fold m a (m b) -> Fold m a b
336-- | Map a monadic function on the output of a fold.
339{-# DEPRECATED mapM "Use rmapM instead" #-}
341mapM :: Monad m => (b -> m c) -> Fold m a b -> Fold m a c
344-- | @mapMaybe f fold@ maps a 'Maybe' returning function @f@ on the input of
345-- the fold, filters out 'Nothing' elements, and return the values extracted
348-- >>> f x = if even x then Just x else Nothing
349-- >>> fld = Fold.mapMaybe f Fold.toList
350-- >>> Stream.fold fld (Stream.enumerateFromTo 1 10)
354{-# INLINE mapMaybe #-}
355mapMaybe :: (Monad m) => (a -> Maybe b) -> Fold m b r -> Fold m a r
356mapMaybe f = lmap f . filter isJust . lmap fromJust
358------------------------------------------------------------------------------
359-- Transformations on fold inputs
360------------------------------------------------------------------------------
364-- | Apply a transformation on a 'Fold' using a 'Pipe'.
367{-# INLINE transform #-}
368transform :: Monad m => Pipe m a b -> Fold m b c -> Fold m a c
369transform (Pipe pstep1 pstep2 pinitial) (Fold fstep finitial fextract) =
370 Fold step initial extract
374 initial = first (Tuple' pinitial) <$> finitial
376 step (Tuple' ps fs) x = do
383 go acc (Pipe.Yield b (Consume ps')) = do
387 Partial s -> Partial $ Tuple' ps' s
389 go acc (Pipe.Yield b (Produce ps')) = do
394 Done b2 -> return $ Done b2
395 go acc (Pipe.Continue (Consume ps')) =
396 return $ Partial $ Tuple' ps' acc
397 go acc (Pipe.Continue (Produce ps')) = do
401 extract (Tuple' _ fs) = fextract fs
403-- | Scan the input of a 'Fold' to change it in a stateful manner using another
407scan :: Monad m => Fold m a b -> Fold m b c -> Fold m a c
408scan (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
409 Fold step initial extract
413 -- XXX It can be moved out and used for both scan and postscan
414 {-# INLINE runStep #-}
415 runStep actionL sR = do
421 Partial sR1 -> Done <$> extractR sR1
422 Done bR -> return $ Done bR
428 Partial sR1 -> Partial (sL, sR1)
434 Partial sR -> runStep initialL sR
435 Done b -> return $ Done b
437 step (sL, sR) x = runStep (stepL sL x) sR
439 extract = extractR . snd
441-- | Postscan the input of a 'Fold' to change it in a stateful manner using
444{-# INLINE postscan #-}
445postscan :: Monad m => Fold m a b -> Fold m b c -> Fold m a c
446postscan (Fold stepL initialL extractL) (Fold stepR initialR extractR) =
447 Fold step initial extract
451 {-# INLINE runStep #-}
452 runStep actionL sR = do
458 Partial sR1 -> Done <$> extractR sR1
459 Done bR -> return $ Done bR
465 Partial sR1 -> Partial (sL, sR1)
474 Done _ -> Done <$> extractR sR
475 Partial sL -> return $ Partial (sL, sR)
476 Done b -> return $ Done b
478 step (sL, sR) x = runStep (stepL sL x) sR
480 extract = extractR . snd
482------------------------------------------------------------------------------
484------------------------------------------------------------------------------
486-- | Convert a predicate into a filtering fold.
488-- >>> f = Fold.foldFilter (Fold.satisfy (> 5)) Fold.sum
489-- >>> Stream.fold f $ Stream.fromList [1..10]
493{-# INLINE satisfy #-}
494satisfy :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
495satisfy f = Fold step (return $ Partial ()) (const (return Nothing))
499 step () a = return $ Done $ if f a then Just a else Nothing
501-- | Use a 'Maybe' returning fold as a filtering scan.
503-- >>> f = Fold.foldFilter (Fold.satisfy (> 5)) Fold.sum
504-- >>> Stream.fold f $ Stream.fromList [1..10]
507-- The above snippet is equivalent to:
509-- >>> f = Fold.filter (> 5) Fold.sum
510-- >>> Stream.fold f $ Stream.fromList [1..10]
514{-# INLINE foldFilter #-}
515foldFilter :: Monad m => Fold m a (Maybe b) -> Fold m b c -> Fold m a c
516foldFilter f1 f2 = many f1 (catMaybes f2)
518------------------------------------------------------------------------------
520------------------------------------------------------------------------------
522------------------------------------------------------------------------------
524------------------------------------------------------------------------------
527-- > drainBy f = lmapM f drain
528-- > drainBy = Fold.foldMapM (void . f)
530-- Drain all input after passing it through a monadic function. This is the
531-- dual of mapM_ on stream producers.
533-- See also: 'Streamly.Prelude.mapM_'
536{-# INLINE drainBy #-}
537drainBy :: Monad m => (a -> m b) -> Fold m a ()
538drainBy f = lmapM f drain
540-- | Extract the last element of the input stream, if any.
542-- > last = fmap getLast $ Fold.foldMap (Last . Just)
546last :: Monad m => Fold m a (Maybe a)
547last = foldl1' (\_ x -> x)
549------------------------------------------------------------------------------
551------------------------------------------------------------------------------
553-- | Like 'length', except with a more general 'Num' return value
555-- > genericLength = fmap getSum $ foldMap (Sum . const 1)
558{-# INLINE genericLength #-}
559genericLength :: (Monad m, Num b) => Fold m a b
560genericLength = foldl' (\n _ -> n + 1) 0
562-- | Determine the length of the input stream.
564-- > length = fmap getSum $ Fold.foldMap (Sum . const 1)
568length :: Monad m => Fold m a Int
569length = genericLength
572-- XXX Add a countDistinct window fold
573-- XXX Add a bloom filter fold
575-- | Count non-duplicate elements in the stream.
577-- The memory used is proportional to the number of distinct elements in the
578-- stream, to guard against using too much memory use it as a scan and
579-- terminate if the count reaches more than a threshold.
581-- /Space/: \(\mathcal{O}(n)\)
585{-# INLINE countDistinct #-}
586countDistinct :: (Monad m, Ord a) => Fold m a Int
587countDistinct = fmap (\(Tuple' _ n) -> n) $ foldl' step initial
591 initial = Tuple' Set.empty 0
593 step (Tuple' set n) x = do
599 in Tuple' (Set.insert x set) cnt
601-- | Like 'countDistinct' but specialized to a stream of 'Int', for better
605{-# INLINE countDistinctInt #-}
606countDistinctInt :: Monad m => Fold m Int Int
607countDistinctInt = fmap (\(Tuple' _ n) -> n) $ foldl' step initial
611 initial = Tuple' IntSet.empty 0
613 step (Tuple' set n) x = do
614 if IntSet.member x set
619 in Tuple' (IntSet.insert x set) cnt
621-- | Determine the sum of all elements of a stream of numbers. Returns additive
622-- identity (@0@) when the stream is empty. Note that this is not numerically
623-- stable for floating point numbers.
625-- > sum = fmap getSum $ Fold.foldMap Sum
629sum :: (Monad m, Num a) => Fold m a a
632-- | Determine the product of all elements of a stream of numbers. Returns
633-- multiplicative identity (@1@) when the stream is empty. The fold terminates
634-- when it encounters (@0@) in its input.
636-- Compare with @Fold.foldMap Product@.
639-- /Since 0.8.0 (Added 'Eq' constraint)/
640{-# INLINE product #-}
641product :: (Monad m, Num a, Eq a) => Fold m a a
642product = mkFold_ step (Partial 1)
651------------------------------------------------------------------------------
653------------------------------------------------------------------------------
655-- | Determine the maximum element in a stream using the supplied comparison
659{-# INLINE maximumBy #-}
660maximumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
661maximumBy cmp = foldl1' max'
672-- maximum = Fold.maximumBy compare
675-- Determine the maximum element in a stream.
677-- Compare with @Fold.foldMap Max@.
680{-# INLINE maximum #-}
681maximum :: (Monad m, Ord a) => Fold m a (Maybe a)
684-- | Computes the minimum element with respect to the given comparison function
687{-# INLINE minimumBy #-}
688minimumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)
689minimumBy cmp = foldl1' min'
698-- | Determine the minimum element in a stream using the supplied comparison
702-- minimum = 'minimumBy' compare
705-- Compare with @Fold.foldMap Min@.
708{-# INLINE minimum #-}
709minimum :: (Monad m, Ord a) => Fold m a (Maybe a)
712------------------------------------------------------------------------------
713-- To Summary (Statistical)
714------------------------------------------------------------------------------
716-- | Compute a numerically stable arithmetic mean of all elements in the input
721mean :: (Monad m, Fractional a) => Fold m a a
722mean = fmap done $ foldl' step begin
728 step (Tuple' x n) y =
730 in Tuple' (x + (y - x) / n1) n1
732 done (Tuple' x _) = x
734-- | Compute a numerically stable (population) variance over all elements in
738{-# INLINE variance #-}
739variance :: (Monad m, Fractional a) => Fold m a a
740variance = fmap done $ foldl' step begin
744 begin = Tuple3' 0 0 0
746 step (Tuple3' n mean_ m2) x = Tuple3' n' mean' m2'
751 mean' = (n * mean_ + x) / (n + 1)
753 m2' = m2 + delta * delta * n / (n + 1)
755 done (Tuple3' n _ m2) = m2 / n
757-- | Compute a numerically stable (population) standard deviation over all
758-- elements in the input stream.
762stdDev :: (Monad m, Floating a) => Fold m a a
763stdDev = sqrt <$> variance
765-- | Compute an 'Int' sized polynomial rolling hash
767-- > H = salt * k ^ n + c1 * k ^ (n - 1) + c2 * k ^ (n - 2) + ... + cn * k ^ 0
769-- Where @c1@, @c2@, @cn@ are the elements in the input stream and @k@ is a
772-- This hash is often used in Rabin-Karp string search algorithm.
774-- See https://en.wikipedia.org/wiki/Rolling_hash
777{-# INLINE rollingHashWithSalt #-}
778rollingHashWithSalt :: (Monad m, Enum a) => Int64 -> Fold m a Int64
779rollingHashWithSalt = foldl' step
783 k = 2891336453 :: Int64
785 step cksum a = cksum * k + fromIntegral (fromEnum a)
787-- | A default salt used in the implementation of 'rollingHash'.
788{-# INLINE defaultSalt #-}
790defaultSalt = -2578643520546668380
792-- | Compute an 'Int' sized polynomial rolling hash of a stream.
794-- > rollingHash = Fold.rollingHashWithSalt defaultSalt
797{-# INLINE rollingHash #-}
798rollingHash :: (Monad m, Enum a) => Fold m a Int64
799rollingHash = rollingHashWithSalt defaultSalt
801-- | Compute an 'Int' sized polynomial rolling hash of the first n elements of
804-- > rollingHashFirstN = Fold.take n Fold.rollingHash
807{-# INLINE rollingHashFirstN #-}
808rollingHashFirstN :: (Monad m, Enum a) => Int -> Fold m a Int64
809rollingHashFirstN n = take n rollingHash
811------------------------------------------------------------------------------
812-- Monoidal left folds
813------------------------------------------------------------------------------
815-- | Append the elements of an input stream to a provided starting value.
817-- >>> Stream.fold (Fold.sconcat 10) (Stream.map Data.Monoid.Sum $ Stream.enumerateFromTo 1 10)
821-- sconcat = Fold.foldl' (<>)
825{-# INLINE sconcat #-}
826sconcat :: (Monad m, Semigroup a) => a -> Fold m a a
829-- | Fold an input stream consisting of monoidal elements using 'mappend'
832-- >>> Stream.fold Fold.mconcat (Stream.map Data.Monoid.Sum $ Stream.enumerateFromTo 1 10)
835-- > mconcat = Fold.sconcat mempty
838{-# INLINE mconcat #-}
841#if !MIN_VERSION_base(4,11,0)
844 , Monoid a) => Fold m a a
845mconcat = sconcat mempty
848-- > foldMap f = Fold.lmap f Fold.mconcat
850-- Make a fold from a pure function that folds the output of the function
851-- using 'mappend' and 'mempty'.
853-- >>> Stream.fold (Fold.foldMap Data.Monoid.Sum) $ Stream.enumerateFromTo 1 10
857{-# INLINE foldMap #-}
858foldMap :: (Monad m, Monoid b
859#if !MIN_VERSION_base(4,11,0)
862 ) => (a -> b) -> Fold m a b
863foldMap f = lmap f mconcat
866-- > foldMapM f = Fold.lmapM f Fold.mconcat
868-- Make a fold from a monadic function that folds the output of the function
869-- using 'mappend' and 'mempty'.
871-- >>> Stream.fold (Fold.foldMapM (return . Data.Monoid.Sum)) $ Stream.enumerateFromTo 1 10
875{-# INLINE foldMapM #-}
876foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b
877foldMapM act = foldlM' step (pure mempty)
883 return $! mappend m m'
885------------------------------------------------------------------------------
887------------------------------------------------------------------------------
890-- This is more efficient than 'Streamly.Internal.Data.Fold.toList'. toList is
891-- exactly the same as reversing the list after 'toListRev'.
893-- | Buffers the input stream to a list in the reverse order of the input.
895-- > toListRev = Fold.foldl' (flip (:)) []
897-- /Warning!/ working on large lists accumulated as buffers in memory could be
898-- very inefficient, consider using "Streamly.Array" instead.
902-- xn : ... : x2 : x1 : []
903{-# INLINE toListRev #-}
904toListRev :: Monad m => Fold m a [a]
905toListRev = foldl' (flip (:)) []
907------------------------------------------------------------------------------
909------------------------------------------------------------------------------
911-- | A fold that drains the first n elements of its input, running the effects
912-- and discarding the results.
914-- > drainN n = Fold.take n Fold.drain
918drainN :: Monad m => Int -> Fold m a ()
919drainN n = take n drain
921------------------------------------------------------------------------------
923------------------------------------------------------------------------------
925-- | Like 'index', except with a more general 'Integral' argument
928{-# INLINE genericIndex #-}
929genericIndex :: (Integral i, Monad m) => i -> Fold m a (Maybe a)
930genericIndex i = mkFold step (Partial 0) (const Nothing)
939-- | Lookup the element at the given index.
941-- See also: 'Streamly.Prelude.!!'
945index :: Monad m => Int -> Fold m a (Maybe a)
948-- | Extract the first element of the stream, if any.
952head :: Monad m => Fold m a (Maybe a)
953head = mkFold_ (const (Done . Just)) (Partial Nothing)
955-- | Returns the first element that satisfies the given predicate.
959find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)
960find predicate = mkFold step (Partial ()) (const Nothing)
969-- | In a stream of (key-value) pairs @(a, b)@, return the value @b@ of the
970-- first pair where the key equals the given value @a@.
972-- > lookup = snd <$> Fold.find ((==) . fst)
976lookup :: (Eq a, Monad m) => a -> Fold m (a,b) (Maybe b)
977lookup a0 = mkFold step (Partial ()) (const Nothing)
986-- | Returns the first index that satisfies the given predicate.
989{-# INLINE findIndex #-}
990findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
991findIndex predicate = mkFold step (Partial 0) (const Nothing)
1000-- XXX If we have a Continue contructor we won't need a Maybe type for the
1001-- scan. The fold will have the ability to skip producing output.
1003-- | Returns all indices that satisfy the given predicate.
1005{-# INLINE findIndices #-}
1006findIndices :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)
1007findIndices predicate =
1008 fmap (either (const Nothing) Just) $ foldl' step (Left (-1))
1014 then Right (either id id i + 1)
1015 else Left (either id id i + 1)
1017-- | Returns the first index where a given value is found in the stream.
1019-- > elemIndex a = Fold.findIndex (== a)
1022{-# INLINE elemIndex #-}
1023elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)
1024elemIndex a = findIndex (a ==)
1026------------------------------------------------------------------------------
1028------------------------------------------------------------------------------
1030-- | Return 'True' if the input stream is empty.
1032-- > null = fmap isJust Fold.head
1036null :: Monad m => Fold m a Bool
1037null = mkFold (\() _ -> Done False) (Partial ()) (const True)
1039-- | Returns 'True' if any of the elements of a stream satisfies a predicate.
1041-- >>> Stream.fold (Fold.any (== 0)) $ Stream.fromList [1,0,1]
1044-- > any p = Fold.lmap p Fold.or
1048any :: Monad m => (a -> Bool) -> Fold m a Bool
1049any predicate = mkFold_ step initial
1053 initial = Partial False
1060-- | Return 'True' if the given element is present in the stream.
1062-- > elem a = Fold.any (== a)
1066elem :: (Eq a, Monad m) => a -> Fold m a Bool
1069-- | Returns 'True' if all elements of a stream satisfy a predicate.
1071-- >>> Stream.fold (Fold.all (== 0)) $ Stream.fromList [1,0,1]
1074-- > all p = Fold.lmap p Fold.and
1078all :: Monad m => (a -> Bool) -> Fold m a Bool
1079all predicate = mkFold_ step initial
1083 initial = Partial True
1090-- | Returns 'True' if the given element is not present in the stream.
1092-- > notElem a = Fold.all (/= a)
1095{-# INLINE notElem #-}
1096notElem :: (Eq a, Monad m) => a -> Fold m a Bool
1097notElem a = all (a /=)
1099-- | Returns 'True' if all elements are 'True', 'False' otherwise
1101-- > and = Fold.all (== True)
1105and :: Monad m => Fold m Bool Bool
1108-- | Returns 'True' if any element is 'True', 'False' otherwise
1110-- > or = Fold.any (== True)
1114or :: Monad m => Fold m Bool Bool
1117------------------------------------------------------------------------------
1118-- Grouping/Splitting
1119------------------------------------------------------------------------------
1121------------------------------------------------------------------------------
1122-- Grouping without looking at elements
1123------------------------------------------------------------------------------
1125------------------------------------------------------------------------------
1127------------------------------------------------------------------------------
1129-- | @splitAt n f1 f2@ composes folds @f1@ and @f2@ such that first @n@
1130-- elements of its input are consumed by fold @f1@ and the rest of the stream
1131-- is consumed by fold @f2@.
1133-- >>> let splitAt_ n xs = Stream.fold (Fold.splitAt n Fold.toList Fold.toList) $ Stream.fromList xs
1135-- >>> splitAt_ 6 "Hello World!"
1136-- ("Hello ","World!")
1138-- >>> splitAt_ (-1) [1,2,3]
1141-- >>> splitAt_ 0 [1,2,3]
1144-- >>> splitAt_ 1 [1,2,3]
1147-- >>> splitAt_ 3 [1,2,3]
1150-- >>> splitAt_ 4 [1,2,3]
1153-- > splitAt n f1 f2 = Fold.serialWith (,) (Fold.take n f1) f2
1157{-# INLINE splitAt #-}
1164splitAt n fld = serialWith (,) (take n fld)
1166------------------------------------------------------------------------------
1167-- Element Aware APIs
1168------------------------------------------------------------------------------
1170------------------------------------------------------------------------------
1172------------------------------------------------------------------------------
1174-- Note: Keep this consistent with S.splitOn. In fact we should eliminate
1175-- S.splitOn in favor of the fold.
1177-- XXX Use Fold.many instead once it is fixed.
1179-- | Like 'takeEndBy' but drops the element on which the predicate succeeds.
1181-- >>> Stream.fold (Fold.takeEndBy_ (== '\n') Fold.toList) $ Stream.fromList "hello\nthere\n"
1184-- >>> Stream.toList $ Stream.foldMany (Fold.takeEndBy_ (== '\n') Fold.toList) $ Stream.fromList "hello\nthere\n"
1187-- > Stream.splitOnSuffix p f = Stream.foldMany (Fold.takeEndBy_ p f)
1189-- See 'Streamly.Prelude.splitOnSuffix' for more details on splitting a
1190-- stream using 'takeEndBy_'.
1193{-# INLINE takeEndBy_ #-}
1194takeEndBy_ :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a b
1195takeEndBy_ predicate (Fold fstep finitial fextract) =
1196 Fold step finitial fextract
1201 if not (predicate a)
1203 else Done <$> fextract s
1205-- | Take the input, stop when the predicate succeeds taking the succeeding
1208-- >>> Stream.fold (Fold.takeEndBy (== '\n') Fold.toList) $ Stream.fromList "hello\nthere\n"
1211-- >>> Stream.toList $ Stream.foldMany (Fold.takeEndBy (== '\n') Fold.toList) $ Stream.fromList "hello\nthere\n"
1212-- ["hello\n","there\n"]
1214-- > Stream.splitWithSuffix p f = Stream.foldMany (Fold.takeEndBy p f)
1216-- See 'Streamly.Prelude.splitWithSuffix' for more details on splitting a
1217-- stream using 'takeEndBy'.
1220{-# INLINE takeEndBy #-}
1221takeEndBy :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a b
1222takeEndBy predicate (Fold fstep finitial fextract) =
1223 Fold step finitial fextract
1229 if not (predicate a)
1233 Partial s1 -> Done <$> fextract s1
1234 Done b -> return $ Done b
1236------------------------------------------------------------------------------
1237-- Binary splitting on a separator
1238------------------------------------------------------------------------------
1241-- | Find the first occurrence of the specified sequence in the input stream
1242-- and break the input stream into two parts, the first part consisting of the
1243-- stream before the sequence and the second part consisting of the sequence
1244-- and the rest of the stream.
1246-- > let breakOn_ pat xs = S.fold (S.breakOn pat FL.toList FL.toList) $ S.fromList xs
1248-- >>> breakOn_ "dear" "Hello dear world!"
1249-- > ("Hello ","dear world!")
1251{-# INLINE breakOn #-}
1252breakOn :: Monad m => Array a -> Fold m a b -> Fold m a c -> Fold m a (b,c)
1253breakOn pat f m = undefined
1256------------------------------------------------------------------------------
1258------------------------------------------------------------------------------
1260-- | Distribute one copy of the stream to each fold and zip the results.
1263-- |-------Fold m a b--------|
1264-- ---stream m a---| |---m (b,c)
1265-- |-------Fold m a c--------|
1267-- >>> Stream.fold (Fold.tee Fold.sum Fold.length) (Stream.enumerateFromTo 1.0 100.0)
1270-- > tee = teeWith (,)
1274tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b,c)
1277-- XXX use "List" instead of "[]"?, use Array for output to scale it to a large
1278-- number of consumers? For polymorphic case a vector could be helpful. For
1279-- Storables we can use arrays. Will need separate APIs for those.
1281-- | Distribute one copy of the stream to each fold and collect the results in
1286-- |-------Fold m a b--------|
1287-- ---stream m a---| |---m [b]
1288-- |-------Fold m a b--------|
1293-- >>> Stream.fold (Fold.distribute [Fold.sum, Fold.length]) (Stream.enumerateFromTo 1 5)
1296-- > distribute = Prelude.foldr (Fold.teeWith (:)) (Fold.fromPure [])
1298-- This is the consumer side dual of the producer side 'sequence' operation.
1300-- Stops when all the folds stop.
1303{-# INLINE distribute #-}
1304distribute :: Monad m => [Fold m a b] -> Fold m a [b]
1305distribute = Prelude.foldr (teeWith (:)) (fromPure [])
1307------------------------------------------------------------------------------
1309------------------------------------------------------------------------------
1311{-# INLINE partitionByMUsing #-}
1312partitionByMUsing :: Monad m =>
1313 ( (x -> y -> (x, y))
1314 -> Fold m (Either b c) x
1315 -> Fold m (Either b c) y
1316 -> Fold m (Either b c) (x, y)
1318 -> (a -> m (Either b c))
1322partitionByMUsing t f fld1 fld2 =
1323 let l = lmap (fromLeft undefined) fld1 -- :: Fold m (Either b c) x
1324 r = lmap (fromRight undefined) fld2 -- :: Fold m (Either b c) y
1325 in lmapM f (t (,) (filter isLeft l) (filter isRight r))
1327-- | Partition the input over two folds using an 'Either' partitioning
1332-- |-------Fold b x--------|
1333-- -----stream m a --> (Either b c)----| |----(x,y)
1334-- |-------Fold c y--------|
1337-- Send input to either fold randomly:
1340-- > import System.Random (randomIO)
1341-- > randomly a = randomIO >>= \\x -> return $ if x then Left a else Right a
1342-- > Stream.fold (Fold.partitionByM randomly Fold.length Fold.length) (Stream.enumerateFromTo 1 100)
1346-- Send input to the two folds in a proportion of 2:1:
1349-- proportionately m n = do
1350-- ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
1352-- r <- readIORef ref
1353-- writeIORef ref $ tail r
1354-- return $ Prelude.head r a
1359-- f <- proportionately 2 1
1360-- r <- Stream.fold (Fold.partitionByM f Fold.length Fold.length) (Stream.enumerateFromTo (1 :: Int) 100)
1368-- This is the consumer side dual of the producer side 'mergeBy' operation.
1370-- When one fold is done, any input meant for it is ignored until the other
1371-- fold is also done.
1373-- Stops when both the folds stop.
1375-- /See also: 'partitionByFstM' and 'partitionByMinM'./
1378{-# INLINE partitionByM #-}
1379partitionByM :: Monad m
1380 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1381partitionByM = partitionByMUsing teeWith
1383-- | Similar to 'partitionByM' but terminates when the first fold terminates.
1386{-# INLINE partitionByFstM #-}
1387partitionByFstM :: Monad m
1388 => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1389partitionByFstM = partitionByMUsing teeWithFst
1391-- | Similar to 'partitionByM' but terminates when any fold terminates.
1394{-# INLINE partitionByMinM #-}
1395partitionByMinM :: Monad m =>
1396 (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1397partitionByMinM = partitionByMUsing teeWithMin
1399-- Note: we could use (a -> Bool) instead of (a -> Either b c), but the latter
1400-- makes the signature clearer as to which case belongs to which fold.
1401-- XXX need to check the performance in both cases.
1402-- | Same as 'partitionByM' but with a pure partition function.
1404-- Count even and odd numbers in a stream:
1407-- let f = Fold.partitionBy (\n -> if even n then Left n else Right n)
1408-- (fmap (("Even " ++) . show) Fold.length)
1409-- (fmap (("Odd " ++) . show) Fold.length)
1410-- in Stream.fold f (Stream.enumerateFromTo 1 100)
1412-- ("Even 50","Odd 50")
1415{-# INLINE partitionBy #-}
1416partitionBy :: Monad m
1417 => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1418partitionBy f = partitionByM (return . f)
1420-- | Compose two folds such that the combined fold accepts a stream of 'Either'
1421-- and routes the 'Left' values to the first fold and 'Right' values to the
1424-- > partition = partitionBy id
1427{-# INLINE partition #-}
1429 => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)
1430partition = partitionBy id
1433-- | Send one item to each fold in a round-robin fashion. This is the consumer
1434-- side dual of producer side 'mergeN' operation.
1436-- partitionN :: Monad m => [Fold m a b] -> Fold m a [b]
1437-- partitionN fs = Fold step begin done
1440-- TODO Demultiplex an input element into a number of typed variants. We want
1441-- to statically restrict the target values within a set of predefined types,
1442-- an enumeration of a GADT. We also want to make sure that the Map contains
1443-- only those types and the full set of those types.
1445-- TODO Instead of the input Map it should probably be a lookup-table using an
1446-- array and not in GC memory. The same applies to the output Map as well.
1447-- However, that would only be helpful if we have a very large data structure,
1448-- need to measure and see how it scales.
1450-- This is the consumer side dual of the producer side 'mux' operation (XXX to
1453-- | Split the input stream based on a key field and fold each split using a
1454-- specific fold collecting the results in a map from the keys to the results.
1455-- Useful for cases like protocol handlers to handle different type of packets
1456-- using different handlers.
1460-- |-------Fold m a b
1461-- -----stream m a-----Map-----|
1462-- |-------Fold m a b
1467-- Any input that does not map to a fold in the input Map is silently ignored.
1469-- > demuxWith f kv = fmap fst $ demuxDefaultWith f kv drain
1473{-# INLINE demuxWith #-}
1474demuxWith :: (Monad m, Ord k)
1475 => (a -> (k, a')) -> Map k (Fold m a' b) -> Fold m a (Map k b)
1476demuxWith f kv = fmap fst $ demuxDefaultWith f kv drain
1478-- | Fold a stream of key value pairs using a map of specific folds for each
1479-- key into a map from keys to the results of fold outputs of the corresponding
1482-- >>> import qualified Data.Map
1484-- let table = Data.Map.fromList [("SUM", Fold.sum), ("PRODUCT", Fold.product)]
1485-- input = Stream.fromList [("SUM",1),("PRODUCT",2),("SUM",3),("PRODUCT",4)]
1486-- in Stream.fold (Fold.demux table) input
1488-- fromList [("PRODUCT",8),("SUM",4)]
1490-- > demux = demuxWith id
1494demux :: (Monad m, Ord k)
1495 => Map k (Fold m a b) -> Fold m (k, a) (Map k b)
1498data DemuxState s b doneMap runMap =
1499 DemuxMapAndDefault !s !doneMap !runMap
1500 | DemuxOnlyMap b !doneMap !runMap
1501 | DemuxOnlyDefault s !doneMap
1503-- | Like 'demuxWith' but uses a default catchall fold to handle inputs which
1504-- do not have a specific fold in the map to handle them.
1506-- If any fold in the map stops, inputs meant for that fold are sent to the
1507-- catchall fold. If the catchall fold stops then inputs that do not match any
1510-- Stops when all the folds, including the catchall fold, stop.
1514{-# INLINE demuxDefaultWith #-}
1515demuxDefaultWith :: (Monad m, Ord k)
1517 -> Map k (Fold m a' b)
1519 -> Fold m a (Map k b, c)
1520demuxDefaultWith f kv (Fold dstep dinitial dextract) =
1521 Fold step initial extract
1526 let runInit (Fold step1 initial1 done1) = do
1530 Partial _ -> Right' (Fold step1 (return r) done1)
1533 -- initialize folds in the kv map and separate the ones that are done
1534 -- from running ones
1535 kv1 <- Prelude.mapM runInit kv
1536 let runMap = Map.map fromRight' $ Map.filter isRight' kv1
1537 doneMap = Map.map fromLeft' $ Map.filter isLeft' kv1
1539 -- Run the default fold, and decide the next state based on its result
1545 $ if Map.size runMap > 0
1546 then DemuxMapAndDefault s doneMap runMap
1547 else DemuxOnlyDefault s doneMap
1549 if Map.size runMap > 0
1550 then Partial $ DemuxOnlyMap b doneMap runMap
1551 else Done (doneMap, b)
1553 {-# INLINE runFold #-}
1554 runFold fPartial fDone doneMap runMap (Fold step1 initial1 done1) k a1 = do
1559 return $ case res of
1561 let fld = Fold step1 (return $ Partial s) done1
1562 runMap1 = Map.insert k fld runMap
1563 in Partial $ fPartial doneMap runMap1
1565 let runMap1 = Map.delete k runMap
1566 doneMap1 = Map.insert k b doneMap
1567 if Map.size runMap1 == 0
1569 else Partial $ fPartial doneMap1 runMap1
1570 Done _ -> error "Bug: demuxDefaultWith: Done fold"
1572 step (DemuxMapAndDefault dacc doneMap runMap) a = do
1574 case Map.lookup k runMap of
1576 res <- dstep dacc (k, a1)
1580 Partial s -> DemuxMapAndDefault s doneMap runMap
1581 Done b -> DemuxOnlyMap b doneMap runMap
1584 (DemuxMapAndDefault dacc)
1585 (Partial . DemuxOnlyDefault dacc)
1586 doneMap runMap fld k a1
1588 step (DemuxOnlyMap dval doneMap runMap) a = do
1590 case Map.lookup k runMap of
1591 Nothing -> return $ Partial $ DemuxOnlyMap dval doneMap runMap
1596 doneMap runMap fld k a1
1597 step (DemuxOnlyDefault dacc doneMap) a = do
1599 res <- dstep dacc (k, a1)
1602 Partial s -> Partial $ DemuxOnlyDefault s doneMap
1603 Done b -> Done (doneMap, b)
1605 runExtract (Fold _ initial1 done1) = do
1608 Partial s -> done1 s
1611 extract (DemuxMapAndDefault dacc doneMap runMap) = do
1613 runMap1 <- Prelude.mapM runExtract runMap
1614 return (doneMap `Map.union` runMap1, b)
1615 extract (DemuxOnlyMap dval doneMap runMap) = do
1616 runMap1 <- Prelude.mapM runExtract runMap
1617 return (doneMap `Map.union` runMap1, dval)
1618 extract (DemuxOnlyDefault dacc doneMap) = do
1623-- > demuxDefault = demuxDefaultWith id
1626{-# INLINE demuxDefault #-}
1627demuxDefault :: (Monad m, Ord k)
1628 => Map k (Fold m a b) -> Fold m (k, a) b -> Fold m (k, a) (Map k b, b)
1629demuxDefault = demuxDefaultWith id
1631{-# INLINE classifyScanWith #-}
1632classifyScanWith :: (Monad m, Ord k) =>
1633 -- Note: we need to return the Map itself to display the in-progress values
1634 -- e.g. to implement top. We could possibly create a separate abstraction
1635 -- for that use case. We return an action because we want it to be lazy so
1636 -- that the downstream consumers can choose to process or discard it.
1637 (a -> k) -> Fold m a b -> Fold m a (m (Map k b), Maybe (k, b))
1638classifyScanWith f (Fold step1 initial1 extract1) =
1639 fmap extract $ foldlM' step initial
1643 initial = return $ Tuple3' Map.empty Set.empty Nothing
1645 {-# INLINE initFold #-}
1646 initFold kv set k a = do
1654 Tuple3' (Map.insert k s1 kv) set Nothing
1656 Tuple3' kv set (Just (k, b))
1657 Done b -> return (Tuple3' kv (Set.insert k set) (Just (k, b)))
1659 step (Tuple3' kv set _) a = do
1661 case Map.lookup k kv of
1664 then return (Tuple3' kv set Nothing)
1665 else initFold kv set k a
1671 Tuple3' (Map.insert k s1 kv) set Nothing
1673 let kv1 = Map.delete k kv
1674 in Tuple3' kv1 (Set.insert k set) (Just (k, b))
1676 extract (Tuple3' kv _ x) = (Prelude.mapM extract1 kv, x)
1679toMap :: (Monad m, Ord k) => Fold m (k, a) (Map k a)
1680toMap = foldl' (\kv (k, v) -> Map.insert k v kv) Map.empty
1682-- | Split the input stream based on a key field and fold each split using the
1683-- given fold. Useful for map/reduce, bucketizing the input in different bins
1684-- or for generating histograms.
1687-- let input = Stream.fromList [("ONE",1),("ONE",1.1),("TWO",2), ("TWO",2.2)]
1688-- in Stream.fold (Fold.classifyWith fst (Fold.lmap snd Fold.toList)) input
1690-- fromList [("ONE",[1.0,1.1]),("TWO",[2.0,2.2])]
1692-- Once the classifier fold terminates for a particular key any further inputs
1693-- in that bucket are ignored.
1695-- Space used is proportional to the number of keys seen till now and
1696-- monotonically increases because it stores whether a key has been seen or
1703{-# INLINE classifyWith #-}
1704classifyWith :: (Monad m, Ord k) =>
1705 (a -> k) -> Fold m a b -> Fold m a (Map k b)
1708 classifier = classifyScanWith f fld
1709 getMap Nothing = pure Map.empty
1710 getMap (Just action) = action
1713 (rmapM getMap $ lmap fst last)
1714 (lmap snd $ catMaybes toMap)
1715 in postscan classifier aggregator
1717-- | Given an input stream of key value pairs and a fold for values, fold all
1718-- the values belonging to each key. Useful for map/reduce, bucketizing the
1719-- input in different bins or for generating histograms.
1722-- let input = Stream.fromList [("ONE",1),("ONE",1.1),("TWO",2), ("TWO",2.2)]
1723-- in Stream.fold (Fold.classify Fold.toList) input
1725-- fromList [("ONE",[1.0,1.1]),("TWO",[2.0,2.2])]
1729-- > classify fld = Fold.classifyWith fst (lmap snd fld)
1732{-# INLINE classify #-}
1733classify :: (Monad m, Ord k) => Fold m a b -> Fold m (k, a) (Map k b)
1734classify fld = classifyWith fst (lmap snd fld)
1736------------------------------------------------------------------------------
1738------------------------------------------------------------------------------
1740{-# INLINE unzipWithMUsing #-}
1741unzipWithMUsing :: Monad m =>
1742 ( (x -> y -> (x, y))
1745 -> Fold m (b, c) (x, y)
1751unzipWithMUsing t f fld1 fld2 =
1752 let f1 = lmap fst fld1 -- :: Fold m (b, c) b
1753 f2 = lmap snd fld2 -- :: Fold m (b, c) c
1754 in lmapM f (t (,) f1 f2)
1756-- | Like 'unzipWith' but with a monadic splitter function.
1758-- @unzipWithM k f1 f2 = lmapM k (unzip f1 f2)@
1761{-# INLINE unzipWithM #-}
1762unzipWithM :: Monad m
1763 => (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1764unzipWithM = unzipWithMUsing teeWith
1766-- | Similar to 'unzipWithM' but terminates when the first fold terminates.
1769{-# INLINE unzipWithFstM #-}
1770unzipWithFstM :: Monad m =>
1771 (a -> m (b, c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)
1772unzipWithFstM = unzipWithMUsing teeWithFst
1774-- | Similar to 'unzipWithM' but terminates when any fold terminates.
1777{-# INLINE unzipWithMinM #-}
1778unzipWithMinM :: Monad m =>
1779 (a -> m (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1780unzipWithMinM = unzipWithMUsing teeWithMin
1782-- | Split elements in the input stream into two parts using a pure splitter
1783-- function, direct each part to a different fold and zip the results.
1785-- @unzipWith f fld1 fld2 = Fold.lmap f (Fold.unzip fld1 fld2)@
1787-- This fold terminates when both the input folds terminate.
1790{-# INLINE unzipWith #-}
1792 => (a -> (b,c)) -> Fold m b x -> Fold m c y -> Fold m a (x,y)
1793unzipWith f = unzipWithM (return . f)
1795-- | Send the elements of tuples in a stream of tuples through two different
1800-- |-------Fold m a x--------|
1801-- ---------stream of (a,b)--| |----m (x,y)
1802-- |-------Fold m b y--------|
1806-- > unzip = Fold.unzipWith id
1808-- This is the consumer side dual of the producer side 'zip' operation.
1812unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a,b) (x,y)
1815------------------------------------------------------------------------------
1816-- Combining streams and folds - Zipping
1817------------------------------------------------------------------------------
1819-- | Zip a stream with the input of a fold using the supplied function.
1823{-# INLINE zipWithM #-}
1824zipWithM :: -- Monad m =>
1825 (a -> b -> m c) -> t m a -> Fold m c x -> Fold m b x
1828-- | Zip a stream with the input of a fold.
1833zip :: Monad m => t m a -> Fold m (a, b) x -> Fold m b x
1834zip = zipWithM (curry return)
1836-- | Pair each element of a fold input with its index, starting from index 0.
1839{-# INLINE indexed #-}
1840indexed :: -- forall m a b. Monad m =>
1841 Fold m (Int, a) b -> Fold m a b
1842indexed = undefined -- zip (Stream.enumerateFrom 0 :: SerialT m Int)
1844-- | Change the predicate function of a Fold from @a -> b@ to accept an
1845-- additional state input @(s, a) -> b@. Convenient to filter with an
1846-- addiitonal index or time input.
1849-- filterWithIndex = with indexed filter
1850-- filterWithAbsTime = with timestamped filter
1851-- filterWithRelTime = with timeIndexed filter
1857 (Fold m (s, a) b -> Fold m a b)
1858 -> (((s, a) -> c) -> Fold m (s, a) b -> Fold m (s, a) b)
1859 -> (((s, a) -> c) -> Fold m a b -> Fold m a b)
1860with f comb g = f . comb g . lmap snd
1862-- | @sampleFromthen offset stride@ samples the element at @offset@ index and
1863-- then every element at strides of @stride@.
1866{-# INLINE sampleFromthen #-}
1867sampleFromthen :: Monad m => Int -> Int -> Fold m a b -> Fold m a b
1868sampleFromthen offset size =
1869 with indexed filter (\(i, _) -> (i + offset) `mod` size == 0)
1871------------------------------------------------------------------------------
1873------------------------------------------------------------------------------
1875-- | @concatSequence f t@ applies folds from stream @t@ sequentially and
1876-- collects the results using the fold @f@.
1880{-# INLINE concatSequence #-}
1883 Fold m b c -> t (Fold m a b) -> Fold m a c
1884concatSequence _f _p = undefined
1886-- | Group the input stream into groups of elements between @low@ and @high@.
1887-- Collection starts in chunks of @low@ and then keeps doubling until we reach
1888-- @high@. Each chunk is folded using the provided fold function.
1890-- This could be useful, for example, when we are folding a stream of unknown
1891-- size to a stream of arrays and we want to minimize the number of
1894-- NOTE: this would be an application of "many" using a terminating fold.
1898{-# INLINE chunksBetween #-}
1899chunksBetween :: -- Monad m =>
1900 Int -> Int -> Fold m a b -> Fold m b c -> Fold m a c
1901chunksBetween _low _high _f1 _f2 = undefined
1903-- | A fold that buffers its input to a pure stream.
1905-- /Warning!/ working on large streams accumulated as buffers in memory could
1906-- be very inefficient, consider using "Streamly.Data.Array" instead.
1908-- >>> toStream = fmap SerialT Fold.toStreamK
1911{-# INLINE toStream #-}
1912toStream :: Monad m => Fold m a (SerialT n a)
1913toStream = fmap SerialT toStreamK
1915-- This is more efficient than 'toStream'. toStream is exactly the same as
1916-- reversing the stream after toStreamRev.
1918-- | Buffers the input stream to a pure stream in the reverse order of the
1921-- >>> toStreamRev = fmap SerialT Fold.toStreamKRev
1923-- /Warning!/ working on large streams accumulated as buffers in memory could
1924-- be very inefficient, consider using "Streamly.Data.Array" instead.
1928-- xn : ... : x2 : x1 : []
1929{-# INLINE toStreamRev #-}
1930toStreamRev :: Monad m => Fold m a (SerialT n a)
1931toStreamRev = fmap SerialT toStreamKRev
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