Streamly.Internal.Data.Fold

See Streamly.Data.Fold for an overview and Streamly.Internal.Data.Fold.Type for design notes.

Imports

>>> :m
>>> :set -XFlexibleContexts
>>> import Control.Monad (void)
>>> import qualified Data.Foldable as Foldable
>>> import Data.Function ((&))
>>> import Data.Functor.Identity (Identity, runIdentity)
>>> import Data.IORef (newIORef, readIORef, writeIORef)
>>> import Data.Maybe (fromJust, isJust)
>>> import Data.Monoid (Endo(..), Last(..), Sum(..))

>>> import Streamly.Data.Array (Array)
>>> import Streamly.Data.Fold (Fold, Tee(..))
>>> import Streamly.Data.Stream (Stream)

>>> import qualified Streamly.Data.Array as Array
>>> import qualified Streamly.Data.Fold as Fold
>>> import qualified Streamly.Data.MutArray as MutArray
>>> import qualified Streamly.Data.Parser as Parser
>>> import qualified Streamly.Data.Stream as Stream
>>> import qualified Streamly.Data.StreamK as StreamK
>>> import qualified Streamly.Data.Unfold as Unfold

For APIs that have not been released yet.

>>> import qualified Streamly.Internal.Data.Fold as Fold
>>> import qualified Streamly.Internal.Data.Fold.Window as FoldW

Fold Type

data Step s b

Represents the result of the step of a Fold. Partial returns an intermediate state of the fold, the fold step can be called again with the state or the driver can use extract on the state to get the result out. Done returns the final result and the fold cannot be driven further.

Pre-release

Constructors

Partial !s

Done !b

Instances

Bifunctor Step

first maps over Partial and second maps over Done.

Defined in Streamly.Internal.Data.Fold.Step

Methods

bimap :: (a -> b) -> (c -> d) -> Step a c -> Step b d

first :: (a -> b) -> Step a c -> Step b c

second :: (b -> c) -> Step a b -> Step a c

Functor (Step s)

fmap maps over Done.

fmap = second

Defined in Streamly.Internal.Data.Fold.Step

Methods

fmap :: (a -> b) -> Step s a -> Step s b

(<$) :: a -> Step s b -> Step s a

data Fold m a b

The type Fold m a b having constructor Fold step initial extract represents a fold over an input stream of values of type a to a final value of type b in Monad m.

The fold uses an intermediate state s as accumulator, the type s is internal to the specific fold definition. The initial value of the fold state s is returned by initial. The step function consumes an input and either returns the final result b if the fold is done or the next intermediate state (see Step). At any point the fold driver can extract the result from the intermediate state using the extract function.

NOTE: The constructor is not yet released, smart constructors are provided to create folds.

Constructors

forall s. Fold (s -> a -> m (Step s b)) (m (Step s b)) (s -> m b)

Fold step initial extract

Instances

Monad m => Applicative (Fold m a)

Applicative form of splitWith. Split the input serially over two folds. Note that this fuses but performance degrades quadratically with respect to the number of compositions. It should be good to use for less than 8 compositions.

Defined in Streamly.Internal.Data.Fold.Type

Methods

pure :: a0 -> Fold m a a0

(<*>) :: Fold m a (a0 -> b) -> Fold m a a0 -> Fold m a b

liftA2 :: (a0 -> b -> c) -> Fold m a a0 -> Fold m a b -> Fold m a c

(*>) :: Fold m a a0 -> Fold m a b -> Fold m a b

(<*) :: Fold m a a0 -> Fold m a b -> Fold m a a0

Functor m => Functor (Fold m a)

Maps a function on the output of the fold (the type b).

Defined in Streamly.Internal.Data.Fold.Type

Methods

fmap :: (a0 -> b) -> Fold m a a0 -> Fold m a b

(<$) :: a0 -> Fold m a b -> Fold m a a0

newtype Tee m a b

Tee is a newtype wrapper over the Fold type providing distributing Applicative, Semigroup, Monoid, Num, Floating and Fractional instances.

The input received by the composed Tee is replicated and distributed to the constituent folds of the Tee.

For example, to compute the average of numbers in a stream without going through the stream twice:

>>> avg = (/) <$> (Tee Fold.sum) <*> (Tee $ fmap fromIntegral Fold.length)
>>> Stream.fold (unTee avg) $ Stream.fromList [1.0..100.0]
50.5

Similarly, the Semigroup and Monoid instances of Tee distribute the input to both the folds and combine the outputs using Monoid or Semigroup instances of the output types:

>>> import Data.Monoid (Sum(..))
>>> t = Tee Fold.one <> Tee Fold.latest
>>> Stream.fold (unTee t) (fmap Sum $ Stream.enumerateFromTo 1.0 100.0)
Just (Sum {getSum = 101.0})

The Num, Floating, and Fractional instances work in the same way.

Constructors

Tee

Fields

• unTee :: Fold m a b

Instances

Monad m => Applicative (Tee m a)

<*> distributes the input to both the argument Tees and combines their outputs using function application.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

pure :: a0 -> Tee m a a0

(<*>) :: Tee m a (a0 -> b) -> Tee m a a0 -> Tee m a b

liftA2 :: (a0 -> b -> c) -> Tee m a a0 -> Tee m a b -> Tee m a c

(*>) :: Tee m a a0 -> Tee m a b -> Tee m a b

(<*) :: Tee m a a0 -> Tee m a b -> Tee m a a0

Functor m => Functor (Tee m a)

Defined in Streamly.Internal.Data.Fold.Tee

Methods

fmap :: (a0 -> b) -> Tee m a a0 -> Tee m a b

(<$) :: a0 -> Tee m a b -> Tee m a a0

(Semigroup b, Monoid b, Monad m) => Monoid (Tee m a b)

<> distributes the input to both the argument Tees and combines their outputs using the Monoid instance of the output type.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

mempty :: Tee m a b

mappend :: Tee m a b -> Tee m a b -> Tee m a b

mconcat :: [Tee m a b] -> Tee m a b

(Semigroup b, Monad m) => Semigroup (Tee m a b)

<> distributes the input to both the argument Tees and combines their outputs using the Semigroup instance of the output type.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

(<>) :: Tee m a b -> Tee m a b -> Tee m a b

sconcat :: NonEmpty (Tee m a b) -> Tee m a b

stimes :: Integral b0 => b0 -> Tee m a b -> Tee m a b

(Monad m, Floating b) => Floating (Tee m a b)

Binary Floating operations distribute the input to both the argument Tees and combine their outputs using the Floating instance of the output type.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

pi :: Tee m a b

exp :: Tee m a b -> Tee m a b

log :: Tee m a b -> Tee m a b

sqrt :: Tee m a b -> Tee m a b

(**) :: Tee m a b -> Tee m a b -> Tee m a b

logBase :: Tee m a b -> Tee m a b -> Tee m a b

sin :: Tee m a b -> Tee m a b

cos :: Tee m a b -> Tee m a b

tan :: Tee m a b -> Tee m a b

asin :: Tee m a b -> Tee m a b

acos :: Tee m a b -> Tee m a b

atan :: Tee m a b -> Tee m a b

sinh :: Tee m a b -> Tee m a b

cosh :: Tee m a b -> Tee m a b

tanh :: Tee m a b -> Tee m a b

asinh :: Tee m a b -> Tee m a b

acosh :: Tee m a b -> Tee m a b

atanh :: Tee m a b -> Tee m a b

log1p :: Tee m a b -> Tee m a b

expm1 :: Tee m a b -> Tee m a b

log1pexp :: Tee m a b -> Tee m a b

log1mexp :: Tee m a b -> Tee m a b

(Monad m, Num b) => Num (Tee m a b)

Binary Num operations distribute the input to both the argument Tees and combine their outputs using the Num instance of the output type.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

(+) :: Tee m a b -> Tee m a b -> Tee m a b

(-) :: Tee m a b -> Tee m a b -> Tee m a b

(*) :: Tee m a b -> Tee m a b -> Tee m a b

negate :: Tee m a b -> Tee m a b

abs :: Tee m a b -> Tee m a b

signum :: Tee m a b -> Tee m a b

fromInteger :: Integer -> Tee m a b

(Monad m, Fractional b) => Fractional (Tee m a b)

Binary Fractional operations distribute the input to both the argument Tees and combine their outputs using the Fractional instance of the output type.

Defined in Streamly.Internal.Data.Fold.Tee

Methods

(/) :: Tee m a b -> Tee m a b -> Tee m a b

recip :: Tee m a b -> Tee m a b

fromRational :: Rational -> Tee m a b

Constructors

Which constructor to use?

• foldl*: If the fold never terminates i.e. does not use the Done constructor otherwise use the foldt* variants.
• *M: Use the M suffix variants if any of the step, initial, or extract function is monadic, otherwise use the pure variants.

foldl' :: Monad m => (b -> a -> b) -> b -> Fold m a b

Make a fold from a left fold style pure step function and initial value of the accumulator.

If your Fold returns only Partial (i.e. never returns a Done) then you can use foldl'* constructors.

A fold with an extract function can be expressed using fmap:

mkfoldlx :: Monad m => (s -> a -> s) -> s -> (s -> b) -> Fold m a b
mkfoldlx step initial extract = fmap extract (foldl' step initial)

foldlM' :: Monad m => (b -> a -> m b) -> m b -> Fold m a b

Make a fold from a left fold style monadic step function and initial value of the accumulator.

A fold with an extract function can be expressed using rmapM:

mkFoldlxM :: Functor m => (s -> a -> m s) -> m s -> (s -> m b) -> Fold m a b
mkFoldlxM step initial extract = rmapM extract (foldlM' step initial)

foldl1' :: Monad m => (a -> a -> a) -> Fold m a (Maybe a)

Make a strict left fold, for non-empty streams, using first element as the starting value. Returns Nothing if the stream is empty.

Pre-release

foldlM1' :: Monad m => (a -> a -> m a) -> Fold m a (Maybe a)

Like 'foldl1'' but with a monadic step function.

Pre-release

foldt' :: Monad m => (s -> a -> Step s b) -> Step s b -> (s -> b) -> Fold m a b

Make a terminating fold using a pure step function, a pure initial state and a pure state extraction function.

Pre-release

foldtM' :: (s -> a -> m (Step s b)) -> m (Step s b) -> (s -> m b) -> Fold m a b

Make a terminating fold with an effectful step function and initial state, and a state extraction function.

>>> foldtM' = Fold.Fold

We can just use Fold but it is provided for completeness.

Pre-release

foldr' :: Monad m => (a -> b -> b) -> b -> Fold m a b

Make a fold using a right fold style step function and a terminal value. It performs a strict right fold via a left fold using function composition. Note that a strict right fold can only be useful for constructing strict structures in memory. For reductions this will be very inefficient.

Definitions:

>>> foldr' f z = fmap (flip appEndo z) $ Fold.foldMap (Endo . f)
>>> foldr' f z = fmap ($ z) $ Fold.foldl' (\g x -> g . f x) id

Example:

>>> Stream.fold (Fold.foldr' (:) []) $ Stream.enumerateFromTo 1 5
[1,2,3,4,5]

foldrM' :: Monad m => (a -> b -> m b) -> m b -> Fold m a b

Like foldr' but with a monadic step function.

Example:

>>> toList = Fold.foldrM' (\a xs -> return $ a : xs) (return [])

See also: foldrM

Pre-release

Mappers

Monadic functions useful with mapM/lmapM on folds or streams.

tracing :: Monad m => (a -> m b) -> a -> m a

Apply a monadic function on the input and return the input.

>>> Stream.fold (Fold.lmapM (Fold.tracing print) Fold.drain) $ (Stream.enumerateFromTo (1 :: Int) 2)
1
2

Pre-release

trace :: Monad m => (a -> m b) -> Fold m a r -> Fold m a r

Apply a monadic function to each element flowing through and discard the results.

>>> Stream.fold (Fold.trace print Fold.drain) $ (Stream.enumerateFromTo (1 :: Int) 2)
1
2

>>> trace f = Fold.lmapM (Fold.tracing f)

Pre-release

Folds

Accumulators

Semigroups and Monoids

sconcat :: (Monad m, Semigroup a) => a -> Fold m a a

Semigroup concat. Append the elements of an input stream to a provided starting value.

Definition:

>>> sconcat = Fold.foldl' (<>)

>>> semigroups = fmap Data.Monoid.Sum $ Stream.enumerateFromTo 1 10
>>> Stream.fold (Fold.sconcat 10) semigroups
Sum {getSum = 65}

mconcat :: (Monad m, Monoid a) => Fold m a a

Monoid concat. Fold an input stream consisting of monoidal elements using mappend and mempty.

Definition:

>>> mconcat = Fold.sconcat mempty

>>> monoids = fmap Data.Monoid.Sum $ Stream.enumerateFromTo 1 10
>>> Stream.fold Fold.mconcat monoids
Sum {getSum = 55}

foldMap :: (Monad m, Monoid b) => (a -> b) -> Fold m a b

Definition:

>>> foldMap f = Fold.lmap f Fold.mconcat

Make a fold from a pure function that folds the output of the function using mappend and mempty.

>>> sum = Fold.foldMap Data.Monoid.Sum
>>> Stream.fold sum $ Stream.enumerateFromTo 1 10
Sum {getSum = 55}

foldMapM :: (Monad m, Monoid b) => (a -> m b) -> Fold m a b

Definition:

>>> foldMapM f = Fold.lmapM f Fold.mconcat

Make a fold from a monadic function that folds the output of the function using mappend and mempty.

>>> sum = Fold.foldMapM (return . Data.Monoid.Sum)
>>> Stream.fold sum $ Stream.enumerateFromTo 1 10
Sum {getSum = 55}

Reducers

drain :: Monad m => Fold m a ()

A fold that drains all its input, running the effects and discarding the results.

>>> drain = Fold.drainMapM (const (return ()))
>>> drain = Fold.foldl' (\_ _ -> ()) ()

drainMapM :: Monad m => (a -> m b) -> Fold m a ()

Definitions:

>>> drainMapM f = Fold.lmapM f Fold.drain
>>> drainMapM f = Fold.foldMapM (void . f)

Drain all input after passing it through a monadic function. This is the dual of mapM_ on stream producers.

the :: (Monad m, Eq a) => Fold m a (Maybe a)

Terminates with Nothing as soon as it finds an element different than the previous one, returns the element if the entire input consists of the same element.

length :: Monad m => Fold m a Int

Determine the length of the input stream.

Definition:

>>> length = Fold.lengthGeneric
>>> length = fmap getSum $ Fold.foldMap (Sum . const  1)

lengthGeneric :: (Monad m, Num b) => Fold m a b

Like length, except with a more general Num return value

Definition:

>>> lengthGeneric = fmap getSum $ Fold.foldMap (Sum . const  1)
>>> lengthGeneric = Fold.foldl' (\n _ -> n + 1) 0

Pre-release

mean :: (Monad m, Fractional a) => Fold m a a

Compute a numerically stable arithmetic mean of all elements in the input stream.

rollingHash :: (Monad m, Enum a) => Fold m a Int64

Compute an Int sized polynomial rolling hash of a stream.

>>> rollingHash = Fold.rollingHashWithSalt Fold.defaultSalt

defaultSalt :: Int64

A default salt used in the implementation of rollingHash.

rollingHashWithSalt :: (Monad m, Enum a) => Int64 -> Fold m a Int64

Compute an Int sized polynomial rolling hash

H = salt * k ^ n + c1 * k ^ (n - 1) + c2 * k ^ (n - 2) + ... + cn * k ^ 0

Where c1, c2, cn are the elements in the input stream and k is a constant.

This hash is often used in Rabin-Karp string search algorithm.

See https://en.wikipedia.org/wiki/Rolling_hash

rollingHashFirstN :: (Monad m, Enum a) => Int -> Fold m a Int64

Compute an Int sized polynomial rolling hash of the first n elements of a stream.

>>> rollingHashFirstN n = Fold.take n Fold.rollingHash

Pre-release

Saturating Reducers

product terminates if it becomes 0. Other folds can theoretically saturate on bounded types, and therefore terminate, however, they will run forever on unbounded types like Integer/Double.

sum :: (Monad m, Num a) => Fold m a a

Determine the sum of all elements of a stream of numbers. Returns additive identity (0) when the stream is empty. Note that this is not numerically stable for floating point numbers.

>>> sum = FoldW.cumulative FoldW.sum

Same as following but numerically stable:

>>> sum = Fold.foldl' (+) 0
>>> sum = fmap Data.Monoid.getSum $ Fold.foldMap Data.Monoid.Sum

product :: (Monad m, Num a, Eq a) => Fold m a a

Determine the product of all elements of a stream of numbers. Returns multiplicative identity (1) when the stream is empty. The fold terminates when it encounters (0) in its input.

Same as the following but terminates on multiplication by 0:

>>> product = fmap Data.Monoid.getProduct $ Fold.foldMap Data.Monoid.Product

maximumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)

Determine the maximum element in a stream using the supplied comparison function.

maximum :: (Monad m, Ord a) => Fold m a (Maybe a)

Determine the maximum element in a stream.

Definitions:

>>> maximum = Fold.maximumBy compare
>>> maximum = Fold.foldl1' max

Same as the following but without a default maximum. The Max Monoid uses the minBound as the default maximum:

>>> maximum = fmap Data.Semigroup.getMax $ Fold.foldMap Data.Semigroup.Max

minimumBy :: Monad m => (a -> a -> Ordering) -> Fold m a (Maybe a)

Computes the minimum element with respect to the given comparison function

minimum :: (Monad m, Ord a) => Fold m a (Maybe a)

Determine the minimum element in a stream using the supplied comparison function.

Definitions:

>>> minimum = Fold.minimumBy compare
>>> minimum = Fold.foldl1' min

Same as the following but without a default minimum. The Min Monoid uses the maxBound as the default maximum:

>>> maximum = fmap Data.Semigroup.getMin $ Fold.foldMap Data.Semigroup.Min

Collectors

Avoid using these folds in scalable or performance critical applications, they buffer all the input in GC memory which can be detrimental to performance if the input is large.

toList :: Monad m => Fold m a [a]

Folds the input stream to a list.

Warning! working on large lists accumulated as buffers in memory could be very inefficient, consider using Streamly.Data.Array instead.

>>> toList = Fold.foldr' (:) []

toListRev :: Monad m => Fold m a [a]

Buffers the input stream to a list in the reverse order of the input.

Definition:

>>> toListRev = Fold.foldl' (flip (:)) []

Warning! working on large lists accumulated as buffers in memory could be very inefficient, consider using Streamly.Array instead.

This is more efficient than toList. toList is exactly the same as reversing the list after toListRev.

toStream :: (Monad m, Monad n) => Fold m a (Stream n a)

A fold that buffers its input to a pure stream.

Warning! working on large streams accumulated as buffers in memory could be very inefficient, consider using Streamly.Data.Array instead.

>>> toStream = fmap Stream.fromList Fold.toList

Pre-release

toStreamRev :: (Monad m, Monad n) => Fold m a (Stream n a)

Buffers the input stream to a pure stream in the reverse order of the input.

>>> toStreamRev = fmap Stream.fromList Fold.toListRev

Warning! working on large streams accumulated as buffers in memory could be very inefficient, consider using Streamly.Data.Array instead.

Pre-release

toStreamK :: Monad m => Fold m a (StreamK n a)

A fold that buffers its input to a pure stream.

>>> toStreamK = foldr StreamK.cons StreamK.nil
>>> toStreamK = fmap StreamK.reverse Fold.toStreamKRev

Internal

toStreamKRev :: Monad m => Fold m a (StreamK n a)

Buffers the input stream to a pure stream in the reverse order of the input.

>>> toStreamKRev = Foldable.foldl' (flip StreamK.cons) StreamK.nil

This is more efficient than toStreamK. toStreamK has exactly the same performance as reversing the stream after toStreamKRev.

Pre-release

topBy :: (MonadIO m, Unbox a) => (a -> a -> Ordering) -> Int -> Fold m a (MutArray a)

Get the top n elements using the supplied comparison function.

To get bottom n elements instead:

>>> bottomBy cmp = Fold.topBy (flip cmp)

Example:

>>> stream = Stream.fromList [2::Int,7,9,3,1,5,6,11,17]
>>> Stream.fold (Fold.topBy compare 3) stream >>= MutArray.toList
[17,11,9]

Pre-release

top :: (MonadIO m, Unbox a, Ord a) => Int -> Fold m a (MutArray a)

Fold the input stream to top n elements.

Definition:

>>> top = Fold.topBy compare

>>> stream = Stream.fromList [2::Int,7,9,3,1,5,6,11,17]
>>> Stream.fold (Fold.top 3) stream >>= MutArray.toList
[17,11,9]

Pre-release

bottomBy :: (MonadIO m, Unbox a) => (a -> a -> Ordering) -> Int -> Fold m a (MutArray a)

Get the bottom most n elements using the supplied comparison function.

bottom :: (MonadIO m, Unbox a, Ord a) => Int -> Fold m a (MutArray a)

Fold the input stream to bottom n elements.

Definition:

>>> bottom = Fold.bottomBy compare

>>> stream = Stream.fromList [2::Int,7,9,3,1,5,6,11,17]
>>> Stream.fold (Fold.bottom 3) stream >>= MutArray.toList
[1,2,3]

Pre-release

Scanners

Stateful transformation of the elements. Useful in combination with the scanMaybe combinator. For scanners the result of the fold is usually a transformation of the current element rather than an aggregation of all elements till now.

latest :: Monad m => Fold m a (Maybe a)

Returns the latest element of the input stream, if any.

>>> latest = Fold.foldl1' (\_ x -> x)
>>> latest = fmap getLast $ Fold.foldMap (Last . Just)

indexingWith :: Monad m => Int -> (Int -> Int) -> Fold m a (Maybe (Int, a))

Pair each element of a fold input with its index, starting from index 0.

indexing :: Monad m => Fold m a (Maybe (Int, a))

>>> indexing = Fold.indexingWith 0 (+ 1)

indexingRev :: Monad m => Int -> Fold m a (Maybe (Int, a))

>>> indexingRev n = Fold.indexingWith n (subtract 1)

rollingMapM :: Monad m => (Maybe a -> a -> m b) -> Fold m a b

Apply a function on every two successive elements of a stream. The first argument of the map function is the previous element and the second argument is the current element. When processing the very first element in the stream, the previous element is Nothing.

Pre-release

Filters

Useful in combination with the scanMaybe combinator.

filtering :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

A scanning fold for filtering elements based on a predicate.

deleteBy :: Monad m => (a -> a -> Bool) -> a -> Fold m a (Maybe a)

Returns the latest element omitting the first occurrence that satisfies the given equality predicate.

Example:

>>> input = Stream.fromList [1,3,3,5]
>>> Stream.fold Fold.toList $ Stream.scanMaybe (Fold.deleteBy (==) 3) input
[1,3,5]

uniqBy :: Monad m => (a -> a -> Bool) -> Fold m a (Maybe a)

Return the latest unique element using the supplied comparison function. Returns Nothing if the current element is same as the last element otherwise returns Just.

Example, strip duplicate path separators:

>>> input = Stream.fromList "//a//b"
>>> f x y = x == '/' && y == '/'
>>> Stream.fold Fold.toList $ Stream.scanMaybe (Fold.uniqBy f) input
"/a/b"

Space: O(1)

Pre-release

uniq :: (Monad m, Eq a) => Fold m a (Maybe a)

See uniqBy.

Definition:

>>> uniq = Fold.uniqBy (==)

repeated :: Fold m a (Maybe a)

Emit only repeated elements, once.

Unimplemented

findIndices :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)

Returns the index of the latest element if the element satisfies the given predicate.

elemIndices :: (Monad m, Eq a) => a -> Fold m a (Maybe Int)

Returns the index of the latest element if the element matches the given value.

Definition:

>>> elemIndices a = Fold.findIndices (== a)

Terminating Folds

Empty folds

Folds that return a result without consuming any input.

fromPure :: Applicative m => b -> Fold m a b

Make a fold that yields the supplied value without consuming any further input.

Pre-release

fromEffect :: Applicative m => m b -> Fold m a b

Make a fold that yields the result of the supplied effectful action without consuming any further input.

Pre-release

fromRefold :: Refold m c a b -> c -> Fold m a b

Make a fold from a consumer.

Internal

Singleton folds

Folds that terminate after consuming exactly one input element. All these can be implemented in terms of the maybe fold.

one :: Monad m => Fold m a (Maybe a)

Take one element from the stream and stop.

Definition:

>>> one = Fold.maybe Just

This is similar to the stream uncons operation.

null :: Monad m => Fold m a Bool

Consume one element, return True if successful else return False. In other words, test if the input is empty or not.

WARNING! It consumes one element if the stream is not empty. If that is not what you want please use the eof parser instead.

Definition:

>>> null = fmap isJust Fold.one

satisfy :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

Consume a single element and return it if it passes the predicate else return Nothing.

Definition:

>>> satisfy f = Fold.maybe (\a -> if f a then Just a else Nothing)

Pre-release

maybe :: Monad m => (a -> Maybe b) -> Fold m a (Maybe b)

Consume a single input and transform it using the supplied Maybe returning function.

Pre-release

Multi folds

Terminate after consuming one or more elements.

drainN :: Monad m => Int -> Fold m a ()

A fold that drains the first n elements of its input, running the effects and discarding the results.

Definition:

>>> drainN n = Fold.take n Fold.drain

Pre-release

indexGeneric :: (Integral i, Monad m) => i -> Fold m a (Maybe a)

Like index, except with a more general Integral argument

Pre-release

index :: Monad m => Int -> Fold m a (Maybe a)

Return the element at the given index.

Definition:

>>> index = Fold.indexGeneric

findM :: Monad m => (a -> m Bool) -> Fold m a (Maybe a)

Returns the first element that satisfies the given predicate.

Pre-release

find :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

Returns the first element that satisfies the given predicate.

lookup :: (Eq a, Monad m) => a -> Fold m (a, b) (Maybe b)

In a stream of (key-value) pairs (a, b), return the value b of the first pair where the key equals the given value a.

Definition:

>>> lookup x = fmap snd <$> Fold.find ((== x) . fst)

findIndex :: Monad m => (a -> Bool) -> Fold m a (Maybe Int)

Returns the first index that satisfies the given predicate.

elemIndex :: (Eq a, Monad m) => a -> Fold m a (Maybe Int)

Returns the first index where a given value is found in the stream.

Definition:

>>> elemIndex a = Fold.findIndex (== a)

elem :: (Eq a, Monad m) => a -> Fold m a Bool

Return True if the given element is present in the stream.

Definition:

>>> elem a = Fold.any (== a)

notElem :: (Eq a, Monad m) => a -> Fold m a Bool

Returns True if the given element is not present in the stream.

Definition:

>>> notElem a = Fold.all (/= a)

all :: Monad m => (a -> Bool) -> Fold m a Bool

Returns True if all elements of the input satisfy the predicate.

Definition:

>>> all p = Fold.lmap p Fold.and

Example:

>>> Stream.fold (Fold.all (== 0)) $ Stream.fromList [1,0,1]
False

any :: Monad m => (a -> Bool) -> Fold m a Bool

Returns True if any element of the input satisfies the predicate.

Definition:

>>> any p = Fold.lmap p Fold.or

Example:

>>> Stream.fold (Fold.any (== 0)) $ Stream.fromList [1,0,1]
True

and :: Monad m => Fold m Bool Bool

Returns True if all elements are True, False otherwise

Definition:

>>> and = Fold.all (== True)

or :: Monad m => Fold m Bool Bool

Returns True if any element is True, False otherwise

Definition:

>>> or = Fold.any (== True)

Trimmers

Useful in combination with the scanMaybe combinator.

taking :: Monad m => Int -> Fold m a (Maybe a)

dropping :: Monad m => Int -> Fold m a (Maybe a)

takingEndByM :: Monad m => (a -> m Bool) -> Fold m a (Maybe a)

takingEndBy :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

>>> takingEndBy p = Fold.takingEndByM (return . p)

takingEndByM_ :: Monad m => (a -> m Bool) -> Fold m a (Maybe a)

takingEndBy_ :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

>>> takingEndBy_ p = Fold.takingEndByM_ (return . p)

droppingWhileM :: Monad m => (a -> m Bool) -> Fold m a (Maybe a)

droppingWhile :: Monad m => (a -> Bool) -> Fold m a (Maybe a)

>>> droppingWhile p = Fold.droppingWhileM (return . p)

prune :: (a -> Bool) -> Fold m a (Maybe a)

Strip all leading and trailing occurrences of an element passing a predicate and make all other consecutive occurrences uniq.

> prune p = Stream.dropWhileAround p $ Stream.uniqBy (x y -> p x && p y)

> Stream.prune isSpace (Stream.fromList "  hello      world!   ")
"hello world!"

Space: O(1)

Unimplemented

Running A Fold

drive :: Monad m => Stream m a -> Fold m a b -> m b

Drive a fold using the supplied Stream, reducing the resulting expression strictly at each step.

Definition:

>>> drive = flip Stream.fold

Example:

>>> Fold.drive (Stream.enumerateFromTo 1 100) Fold.sum
5050

Building Incrementally

extractM :: Monad m => Fold m a b -> m b

Extract the accumulated result of the fold.

Definition:

>>> extractM = Fold.drive Stream.nil

Example:

>>> Fold.extractM Fold.toList
[]

Pre-release

reduce :: Monad m => Fold m a b -> m (Fold m a b)

Evaluate the initialization effect of a fold. If we are building the fold by chaining lazy actions in fold init this would reduce the actions to a strict accumulator value.

Pre-release

close :: Monad m => Fold m a b -> Fold m a b

Close a fold so that it does not accept any more input.

isClosed :: Monad m => Fold m a b -> m Bool

Check if the fold has terminated and can take no more input.

Pre-release

snoc :: Monad m => Fold m a b -> a -> m (Fold m a b)

Append a singleton value to the fold, in other words run a single step of the fold.

Example:

>>> import qualified Data.Foldable as Foldable
>>> Foldable.foldlM Fold.snoc Fold.toList [1..3] >>= Fold.drive Stream.nil
[1,2,3]

Pre-release

snocl :: Monad m => Fold m a b -> a -> Fold m a b

Append a singleton value to the fold lazily, in other words run a single step of the fold.

Definition:

>>> snocl f = Fold.snoclM f . return

Example:

>>> import qualified Data.Foldable as Foldable
>>> Fold.extractM $ Foldable.foldl Fold.snocl Fold.toList [1..3]
[1,2,3]

Pre-release

snocM :: Monad m => Fold m a b -> m a -> m (Fold m a b)

Append a singleton value to the fold in other words run a single step of the fold.

Definition:

>>> snocM f = Fold.reduce . Fold.snoclM f

Pre-release

snoclM :: Monad m => Fold m a b -> m a -> Fold m a b

Append an effect to the fold lazily, in other words run a single step of the fold.

Pre-release

addOne :: Monad m => a -> Fold m a b -> m (Fold m a b)

Append a singleton value to the fold.

See examples under addStream.

Pre-release

addStream :: Monad m => Stream m a -> Fold m a b -> m (Fold m a b)

Append a stream to a fold to build the fold accumulator incrementally. We can repeatedly call addStream on the same fold to continue building the fold and finally use drive to finish the fold and extract the result. Also see the addOne operation which is a singleton version of addStream.

Definitions:

>>> addStream stream = Fold.drive stream . Fold.duplicate

Example, build a list incrementally:

>>> :{
pure (Fold.toList :: Fold IO Int [Int])
    >>= Fold.addOne 1
    >>= Fold.addStream (Stream.enumerateFromTo 2 4)
    >>= Fold.drive Stream.nil
    >>= print
:}
[1,2,3,4]

This can be used as an O(n) list append compared to the O(n^2) ++ when used for incrementally building a list.

Example, build a stream incrementally:

>>> :{
pure (Fold.toStream :: Fold IO Int (Stream Identity Int))
    >>= Fold.addOne 1
    >>= Fold.addStream (Stream.enumerateFromTo 2 4)
    >>= Fold.drive Stream.nil
    >>= print
:}
fromList [1,2,3,4]

This can be used as an O(n) stream append compared to the O(n^2) <> when used for incrementally building a stream.

Example, build an array incrementally:

>>> :{
pure (Array.write :: Fold IO Int (Array Int))
    >>= Fold.addOne 1
    >>= Fold.addStream (Stream.enumerateFromTo 2 4)
    >>= Fold.drive Stream.nil
    >>= print
:}
fromList [1,2,3,4]

Example, build an array stream incrementally:

>>> :{
let f :: Fold IO Int (Stream Identity (Array Int))
    f = Fold.groupsOf 2 (Array.writeN 3) Fold.toStream
in pure f
    >>= Fold.addOne 1
    >>= Fold.addStream (Stream.enumerateFromTo 2 4)
    >>= Fold.drive Stream.nil
    >>= print
:}
fromList [fromList [1,2],fromList [3,4]]

Combinators

Utilities

with :: (Fold m (s, a) b -> Fold m a b) -> (((s, a) -> c) -> Fold m (s, a) b -> Fold m (s, a) b) -> ((s, a) -> c) -> Fold m a b -> Fold m a b

Change the predicate function of a Fold from a -> b to accept an additional state input (s, a) -> b. Convenient to filter with an addiitonal index or time input.

>>> filterWithIndex = Fold.with Fold.indexed Fold.filter

filterWithAbsTime = with timestamped filter
filterWithRelTime = with timeIndexed filter

Pre-release

Transforming the Monad

morphInner :: (forall x. m x -> n x) -> Fold m a b -> Fold n a b

Change the underlying monad of a fold. Also known as hoist.

Pre-release

generalizeInner :: Monad m => Fold Identity a b -> Fold m a b

Adapt a pure fold to any monad.

>>> generalizeInner = Fold.morphInner (return . runIdentity)

Pre-release

Mapping on output

rmapM :: Monad m => (b -> m c) -> Fold m a b -> Fold m a c

Map a monadic function on the output of a fold.

Mapping on Input

transform :: Monad m => Pipe m a b -> Fold m b c -> Fold m a c

Apply a transformation on a Fold using a Pipe.

Pre-release

lmap :: (a -> b) -> Fold m b r -> Fold m a r

lmap f fold maps the function f on the input of the fold.

Definition:

>>> lmap = Fold.lmapM return

Example:

>>> sumSquared = Fold.lmap (\x -> x * x) Fold.sum
>>> Stream.fold sumSquared (Stream.enumerateFromTo 1 100)
338350

lmapM :: Monad m => (a -> m b) -> Fold m b r -> Fold m a r

lmapM f fold maps the monadic function f on the input of the fold.

Sliding Window

slide2 :: Monad m => Fold m (a, Maybe a) b -> Fold m a b

Provide a sliding window of length 2 elements.

See Streamly.Internal.Data.Fold.Window.

Scanning Input

scan :: Monad m => Fold m a b -> Fold m b c -> Fold m a c

Scan the input of a Fold to change it in a stateful manner using another Fold. The scan stops as soon as the fold terminates.

Pre-release

scanMany :: Monad m => Fold m a b -> Fold m b c -> Fold m a c

Scan the input of a Fold to change it in a stateful manner using another Fold. The scan restarts with a fresh state if the fold terminates.

Pre-release

postscan :: Monad m => Fold m a b -> Fold m b c -> Fold m a c

Postscan the input of a Fold to change it in a stateful manner using another Fold.

postscan scanner collector

Pre-release

indexed :: Monad m => Fold m (Int, a) b -> Fold m a b

Pair each element of a fold input with its index, starting from index 0.

>>> indexed = Fold.scanMaybe Fold.indexing

Zipping Input

zipStreamWithM :: (a -> b -> m c) -> Stream m a -> Fold m c x -> Fold m b x

Zip a stream with the input of a fold using the supplied function.

Unimplemented

zipStream :: Monad m => Stream m a -> Fold m (a, b) x -> Fold m b x

Zip a stream with the input of a fold.

>>> zip = Fold.zipStreamWithM (curry return)

Unimplemented

Filtering Input

catMaybes :: Monad m => Fold m a b -> Fold m (Maybe a) b

Modify a fold to receive a Maybe input, the Just values are unwrapped and sent to the original fold, Nothing values are discarded.

>>> catMaybes = Fold.mapMaybe id
>>> catMaybes = Fold.filter isJust . Fold.lmap fromJust

mapMaybeM :: Monad m => (a -> m (Maybe b)) -> Fold m b r -> Fold m a r

>>> mapMaybeM f = Fold.lmapM f . Fold.catMaybes

mapMaybe :: Monad m => (a -> Maybe b) -> Fold m b r -> Fold m a r

mapMaybe f fold maps a Maybe returning function f on the input of the fold, filters out Nothing elements, and return the values extracted from Just.

>>> mapMaybe f = Fold.lmap f . Fold.catMaybes
>>> mapMaybe f = Fold.mapMaybeM (return . f)

>>> f x = if even x then Just x else Nothing
>>> fld = Fold.mapMaybe f Fold.toList
>>> Stream.fold fld (Stream.enumerateFromTo 1 10)
[2,4,6,8,10]

scanMaybe :: Monad m => Fold m a (Maybe b) -> Fold m b c -> Fold m a c

Use a Maybe returning fold as a filtering scan.

>>> scanMaybe p f = Fold.postscan p (Fold.catMaybes f)

Pre-release

filter :: Monad m => (a -> Bool) -> Fold m a r -> Fold m a r

Include only those elements that pass a predicate.

>>> Stream.fold (Fold.filter (> 5) Fold.sum) $ Stream.fromList [1..10]
40

>>> filter p = Fold.scanMaybe (Fold.filtering p)
>>> filter p = Fold.filterM (return . p)
>>> filter p = Fold.mapMaybe (\x -> if p x then Just x else Nothing)

filterM :: Monad m => (a -> m Bool) -> Fold m a r -> Fold m a r

Like filter but with a monadic predicate.

>>> f p x = p x >>= \r -> return $ if r then Just x else Nothing
>>> filterM p = Fold.mapMaybeM (f p)

sampleFromthen :: Monad m => Int -> Int -> Fold m a b -> Fold m a b

sampleFromthen offset stride samples the element at offset index and then every element at strides of stride.

catLefts :: Monad m => Fold m a c -> Fold m (Either a b) c

Discard Rights and unwrap Lefts in an Either stream.

Pre-release

catRights :: Monad m => Fold m b c -> Fold m (Either a b) c

Discard Lefts and unwrap Rights in an Either stream.

Pre-release

catEithers :: Fold m a b -> Fold m (Either a a) b

Remove the either wrapper and flatten both lefts and as well as rights in the output stream.

Definition:

>>> catEithers = Fold.lmap (either id id)

Pre-release

Trimming

take :: Monad m => Int -> Fold m a b -> Fold m a b

Take at most n input elements and fold them using the supplied fold. A negative count is treated as 0.

>>> Stream.fold (Fold.take 2 Fold.toList) $ Stream.fromList [1..10]
[1,2]

takeEndBy :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a b

Take the input, stop when the predicate succeeds taking the succeeding element as well.

Example:

>>> input = Stream.fromList "hello\nthere\n"
>>> line = Fold.takeEndBy (== '\n') Fold.toList
>>> Stream.fold line input
"hello\n"

>>> Stream.fold Fold.toList $ Stream.foldMany line input
["hello\n","there\n"]

takeEndBy_ :: Monad m => (a -> Bool) -> Fold m a b -> Fold m a b

Like takeEndBy but drops the element on which the predicate succeeds.

Example:

>>> input = Stream.fromList "hello\nthere\n"
>>> line = Fold.takeEndBy_ (== '\n') Fold.toList
>>> Stream.fold line input
"hello"

>>> Stream.fold Fold.toList $ Stream.foldMany line input
["hello","there"]

takeEndBySeq :: forall m a b. (MonadIO m, Storable a, Unbox a, Enum a, Eq a) => Array a -> Fold m a b -> Fold m a b

Continue taking the input until the input sequence matches the supplied sequence, taking the supplied sequence as well. If the pattern is empty this acts as an identity fold.

>>> s = Stream.fromList "hello there. How are you?"
>>> f = Fold.takeEndBySeq (Array.fromList "re") Fold.toList
>>> Stream.fold f s
"hello there"

>>> Stream.fold Fold.toList $ Stream.foldMany f s
["hello there",". How are"," you?"]

Pre-release

takeEndBySeq_ :: forall m a b. (MonadIO m, Storable a, Unbox a, Enum a, Eq a) => Array a -> Fold m a b -> Fold m a b

Like takeEndBySeq but discards the matched sequence.

Pre-release

Serial Append

splitWith :: Monad m => (a -> b -> c) -> Fold m x a -> Fold m x b -> Fold m x c

Sequential fold application. Apply two folds sequentially to an input stream. The input is provided to the first fold, when it is done - the remaining input is provided to the second fold. When the second fold is done or if the input stream is over, the outputs of the two folds are combined using the supplied function.

Example:

>>> header = Fold.take 8 Fold.toList
>>> line = Fold.takeEndBy (== '\n') Fold.toList
>>> f = Fold.splitWith (,) header line
>>> Stream.fold f $ Stream.fromList "header: hello\n"
("header: ","hello\n")

Note: This is dual to appending streams using append.

Note: this implementation allows for stream fusion but has quadratic time complexity, because each composition adds a new branch that each subsequent fold's input element has to traverse, therefore, it cannot scale to a large number of compositions. After around 100 compositions the performance starts dipping rapidly compared to a CPS style implementation. When you need scaling use parser monad instead.

Time: O(n^2) where n is the number of compositions.

split_ :: Monad m => Fold m x a -> Fold m x b -> Fold m x b

Same as applicative *>. Run two folds serially one after the other discarding the result of the first.

This was written in the hope that it might be faster than implementing it using splitWith, but the current benchmarks show that it has the same performance. So do not expose it unless some benchmark shows benefit.

splitAt :: Monad m => Int -> Fold m a b -> Fold m a c -> Fold m a (b, c)

splitAt n f1 f2 composes folds f1 and f2 such that first n elements of its input are consumed by fold f1 and the rest of the stream is consumed by fold f2.

>>> let splitAt_ n xs = Stream.fold (Fold.splitAt n Fold.toList Fold.toList) $ Stream.fromList xs

>>> splitAt_ 6 "Hello World!"
("Hello ","World!")

>>> splitAt_ (-1) [1,2,3]
([],[1,2,3])

>>> splitAt_ 0 [1,2,3]
([],[1,2,3])

>>> splitAt_ 1 [1,2,3]
([1],[2,3])

>>> splitAt_ 3 [1,2,3]
([1,2,3],[])

>>> splitAt_ 4 [1,2,3]
([1,2,3],[])

splitAt n f1 f2 = Fold.splitWith (,) (Fold.take n f1) f2

Internal

Parallel Distribution

teeWith :: Monad m => (a -> b -> c) -> Fold m x a -> Fold m x b -> Fold m x c

teeWith k f1 f2 distributes its input to both f1 and f2 until both of them terminate and combines their output using k.

Definition:

>>> teeWith k f1 f2 = fmap (uncurry k) (Fold.tee f1 f2)

Example:

>>> avg = Fold.teeWith (/) Fold.sum (fmap fromIntegral Fold.length)
>>> Stream.fold avg $ Stream.fromList [1.0..100.0]
50.5

For applicative composition using this combinator see Streamly.Data.Fold.Tee.

See also: Streamly.Data.Fold.Tee

Note that nested applications of teeWith do not fuse.

tee :: Monad m => Fold m a b -> Fold m a c -> Fold m a (b, c)

Distribute one copy of the stream to each fold and zip the results.

                |-------Fold m a b--------|
---stream m a---|                         |---m (b,c)
                |-------Fold m a c--------|

Definition:

>>> tee = Fold.teeWith (,)

Example:

>>> t = Fold.tee Fold.sum Fold.length
>>> Stream.fold t (Stream.enumerateFromTo 1.0 100.0)
(5050.0,100)

teeWithFst :: Monad m => (b -> c -> d) -> Fold m a b -> Fold m a c -> Fold m a d

Like teeWith but terminates as soon as the first fold terminates.

Pre-release

teeWithMin :: Monad m => (b -> c -> d) -> Fold m a b -> Fold m a c -> Fold m a d

Like teeWith but terminates as soon as any one of the two folds terminates.

Pre-release

distribute :: Monad m => [Fold m a b] -> Fold m a [b]

Distribute one copy of the stream to each fold and collect the results in a container.

                |-------Fold m a b--------|
---stream m a---|                         |---m [b]
                |-------Fold m a b--------|
                |                         |
                           ...

>>> Stream.fold (Fold.distribute [Fold.sum, Fold.length]) (Stream.enumerateFromTo 1 5)
[15,5]

>>> distribute = Prelude.foldr (Fold.teeWith (:)) (Fold.fromPure [])

This is the consumer side dual of the producer side sequence operation.

Stops when all the folds stop.

Unzipping

unzip :: Monad m => Fold m a x -> Fold m b y -> Fold m (a, b) (x, y)

Send the elements of tuples in a stream of tuples through two different folds.

                          |-------Fold m a x--------|
---------stream of (a,b)--|                         |----m (x,y)
                          |-------Fold m b y--------|

Definition:

>>> unzip = Fold.unzipWith id

This is the consumer side dual of the producer side zip operation.

unzipWith :: Monad m => (a -> (b, c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Split elements in the input stream into two parts using a pure splitter function, direct each part to a different fold and zip the results.

Definitions:

>>> unzipWith f = Fold.unzipWithM (return . f)
>>> unzipWith f fld1 fld2 = Fold.lmap f (Fold.unzip fld1 fld2)

This fold terminates when both the input folds terminate.

Pre-release

unzipWithM :: Monad m => (a -> m (b, c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Like unzipWith but with a monadic splitter function.

Definition:

>>> unzipWithM k f1 f2 = Fold.lmapM k (Fold.unzip f1 f2)

Pre-release

unzipWithFstM :: Monad m => (a -> m (b, c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Similar to unzipWithM but terminates when the first fold terminates.

unzipWithMinM :: Monad m => (a -> m (b, c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Similar to unzipWithM but terminates when any fold terminates.

Parallel Alternative

shortest :: Monad m => Fold m x a -> Fold m x b -> Fold m x (Either a b)

Shortest alternative. Apply both folds in parallel but choose the result from the one which consumed least input i.e. take the shortest succeeding fold.

If both the folds finish at the same time or if the result is extracted before any of the folds could finish then the left one is taken.

Pre-release

longest :: Monad m => Fold m x a -> Fold m x b -> Fold m x (Either a b)

Longest alternative. Apply both folds in parallel but choose the result from the one which consumed more input i.e. take the longest succeeding fold.

If both the folds finish at the same time or if the result is extracted before any of the folds could finish then the left one is taken.

Pre-release

Partitioning

partitionByM :: Monad m => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Partition the input over two folds using an Either partitioning predicate.

                                    |-------Fold b x--------|
-----stream m a --> (Either b c)----|                       |----(x,y)
                                    |-------Fold c y--------|

Example, send input to either fold randomly:

>>> :set -package random
>>> import System.Random (randomIO)
>>> randomly a = randomIO >>= \x -> return $ if x then Left a else Right a
>>> f = Fold.partitionByM randomly Fold.length Fold.length
>>> Stream.fold f (Stream.enumerateFromTo 1 100)
...

Example, send input to the two folds in a proportion of 2:1:

>>> :{
proportionately m n = do
 ref <- newIORef $ cycle $ concat [replicate m Left, replicate n Right]
 return $ \a -> do
     r <- readIORef ref
     writeIORef ref $ tail r
     return $ Prelude.head r a
:}

>>> :{
main = do
 g <- proportionately 2 1
 let f = Fold.partitionByM g Fold.length Fold.length
 r <- Stream.fold f (Stream.enumerateFromTo (1 :: Int) 100)
 print r
:}

>>> main
(67,33)

This is the consumer side dual of the producer side mergeBy operation.

When one fold is done, any input meant for it is ignored until the other fold is also done.

Stops when both the folds stop.

See also: partitionByFstM and partitionByMinM.

Pre-release

partitionByFstM :: Monad m => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Similar to partitionByM but terminates when the first fold terminates.

partitionByMinM :: Monad m => (a -> m (Either b c)) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Similar to partitionByM but terminates when any fold terminates.

partitionBy :: Monad m => (a -> Either b c) -> Fold m b x -> Fold m c y -> Fold m a (x, y)

Same as partitionByM but with a pure partition function.

Example, count even and odd numbers in a stream:

>>> :{
 let f = Fold.partitionBy (\n -> if even n then Left n else Right n)
                     (fmap (("Even " ++) . show) Fold.length)
                     (fmap (("Odd "  ++) . show) Fold.length)
  in Stream.fold f (Stream.enumerateFromTo 1 100)
:}
("Even 50","Odd 50")

Pre-release

partition :: Monad m => Fold m b x -> Fold m c y -> Fold m (Either b c) (x, y)

Compose two folds such that the combined fold accepts a stream of Either and routes the Left values to the first fold and Right values to the second fold.

Definition:

>>> partition = Fold.partitionBy id

Splitting

many :: Monad m => Fold m a b -> Fold m b c -> Fold m a c

Collect zero or more applications of a fold. many first second applies the first fold repeatedly on the input stream and accumulates it's results using the second fold.

>>> two = Fold.take 2 Fold.toList
>>> twos = Fold.many two Fold.toList
>>> Stream.fold twos $ Stream.fromList [1..10]
[[1,2],[3,4],[5,6],[7,8],[9,10]]

Stops when second fold stops.

See also: concatMap, foldMany

manyPost :: Monad m => Fold m a b -> Fold m b c -> Fold m a c

Like many, but the "first" fold emits an output at the end even if no input is received.

Internal

See also: concatMap, foldMany

groupsOf :: Monad m => Int -> Fold m a b -> Fold m b c -> Fold m a c

groupsOf n split collect repeatedly applies the split fold to chunks of n items in the input stream and supplies the result to the collect fold.

Definition:

>>> groupsOf n split = Fold.many (Fold.take n split)

Example:

>>> twos = Fold.groupsOf 2 Fold.toList Fold.toList
>>> Stream.fold twos $ Stream.fromList [1..10]
[[1,2],[3,4],[5,6],[7,8],[9,10]]

Stops when collect stops.

chunksBetween :: Int -> Int -> Fold m a b -> Fold m b c -> Fold m a c

Group the input stream into groups of elements between low and high. Collection starts in chunks of low and then keeps doubling until we reach high. Each chunk is folded using the provided fold function.

This could be useful, for example, when we are folding a stream of unknown size to a stream of arrays and we want to minimize the number of allocations.

NOTE: this would be an application of "many" using a terminating fold.

Unimplemented

refoldMany :: Monad m => Fold m a b -> Refold m x b c -> Refold m x a c

Like many but uses a Refold for collecting.

refoldMany1 :: Monad m => Refold m x a b -> Fold m b c -> Refold m x a c

Like many but uses a Refold for splitting.

Internal

intersperseWithQuotes :: (Monad m, Eq a) => a -> a -> a -> Fold m a b -> Fold m b c -> Fold m a c

Nesting

unfoldMany :: Monad m => Unfold m a b -> Fold m b c -> Fold m a c

Unfold and flatten the input stream of a fold.

Stream.fold (unfoldMany u f) = Stream.fold f . Stream.unfoldMany u

Pre-release

concatSequence :: Fold m b c -> t (Fold m a b) -> Fold m a c

concatSequence f t applies folds from stream t sequentially and collects the results using the fold f.

Unimplemented

concatMap :: Monad m => (b -> Fold m a c) -> Fold m a b -> Fold m a c

Map a Fold returning function on the result of a Fold and run the returned fold. This operation can be used to express data dependencies between fold operations.

Let's say the first element in the stream is a count of the following elements that we have to add, then:

>>> import Data.Maybe (fromJust)
>>> count = fmap fromJust Fold.one
>>> total n = Fold.take n Fold.sum
>>> Stream.fold (Fold.concatMap total count) $ Stream.fromList [10,9..1]
45

This does not fuse completely, see refold for a fusible alternative.

Time: O(n^2) where n is the number of compositions.

See also: foldIterateM, refold

duplicate :: Monad m => Fold m a b -> Fold m a (Fold m a b)

duplicate provides the ability to run a fold in parts. The duplicated fold consumes the input and returns the same fold as output instead of returning the final result, the returned fold can be run later to consume more input.

duplicate essentially appends a stream to the fold without finishing the fold. Compare with snoc which appends a singleton value to the fold.

Pre-release

refold :: Monad m => Refold m b a c -> Fold m a b -> Fold m a c

Extract the output of a fold and refold it using a Refold.

A fusible alternative to concatMap.

Internal

Deprecated

foldr :: Monad m => (a -> b -> b) -> b -> Fold m a b

Deprecated: Please use foldr' instead.

drainBy :: Monad m => (a -> m b) -> Fold m a ()

Deprecated: Please use drainMapM instead.

last :: Monad m => Fold m a (Maybe a)

Deprecated: Please use latest instead.

head :: Monad m => Fold m a (Maybe a)

Deprecated: Please use "one" instead

Extract the first element of the stream, if any.

>>> head = Fold.one

sequence :: Monad m => Fold m a (m b) -> Fold m a b

Deprecated: Use "rmapM id" instead

Flatten the monadic output of a fold to pure output.

mapM :: Monad m => (b -> m c) -> Fold m a b -> Fold m a c

Deprecated: Use rmapM instead

Map a monadic function on the output of a fold.

variance :: (Monad m, Fractional a) => Fold m a a

Deprecated: Use the streamly-statistics package instead

Compute a numerically stable (population) variance over all elements in the input stream.

stdDev :: (Monad m, Floating a) => Fold m a a

Deprecated: Use the streamly-statistics package instead

Compute a numerically stable (population) standard deviation over all elements in the input stream.

serialWith :: Monad m => (a -> b -> c) -> Fold m x a -> Fold m x b -> Fold m x c

Deprecated: Please use "splitWith" instead