Control.Foldl.Transduce

This module builds on module Control.Foldl, adding stateful transducers and grouping operations.

Transducer types

type Transduction a b = forall x. Fold b x -> Fold a x

A (possibly stateful) transformation on the inputs of a Fold.

Functions constructed with combinators like premap or handles from Control.Foldl also typecheck as a Transduction.

type Transduction' a b r = forall x. Fold b x -> Fold a (r, x)

A more general from of Transduction that adds new information to the return value of the Fold.

data Transducer i o r

A stateful process that transforms a stream of inputs into a stream of outputs, and may optionally demarcate groups in the stream of outputs.

Composed of a step function, an initial state, and a extraction function.

The step function returns a triplet of:

• The new internal state.
• List of outputs belonging to the last segment detected in the previous step.

• A list of lists of outputs belonging to segments detected in the current step. If the list is empty, that means no splitting has taken place in the current step. Transducers that do not perform grouping never return anything other than [] here. In effect, they treat the whole stream as a single group.

  The extraction function returns the Transducers own result value, as well as any pending output.

Constructors

forall x . Transducer (x -> i -> (x, [o], [[o]])) x (x -> (r, [o], [[o]]))

Instances

ToTransducer Transducer

Monad m => ToTransducerM m Transducer

Bifunctor (Transducer i)

Functor (Transducer i o)

Comonad (Transducer i o)

Extend (Transducer i o)

class ToTransducer t where

Helps converting monadic transducers (over Identity) into pure ones.

Methods

toTransducer :: t i o r -> Transducer i o r

Instances

ToTransducer Transducer

ToTransducer (TransducerM Identity)

Monadic transducer types

type TransductionM m a b = forall x. Monad m => FoldM m b x -> FoldM m a x

Like Transduction, but works on monadic Folds.

type TransductionM' m a b r = forall x. FoldM m b x -> FoldM m a (r, x)

Like Transduction', but works on monadic Folds.

data TransducerM m i o r

Like Transducer, but monadic.

Constructors

forall x . TransducerM (x -> i -> m (x, [o], [[o]])) (m x) (x -> m (r, [o], [[o]]))

Instances

(~) (* -> *) m m' => ToTransducerM m (TransducerM m')

ToTransducer (TransducerM Identity)

(Functor m, Monad m) => Bifunctor (TransducerM m i)

Monad m => Functor (TransducerM m i o)

Monad m => Extend (TransducerM m i o)

class ToTransducerM m t where

Helps converting pure transducers into monadic ones.

Methods

toTransducerM :: t i o r -> TransducerM m i o r

Instances

Monad m => ToTransducerM m Transducer

(~) (* -> *) m m' => ToTransducerM m (TransducerM m')

Applying transducers

transduce :: ToTransducer t => t i o s -> Transduction i o

Apply a Transducer to a Fold, discarding the return value of the Transducer.

>>> L.fold (transduce (Transducer (\_ i -> ((),[i],[])) () (\_ -> ('r',[],[]))) L.list) [1..7]
[1,2,3,4,5,6,7]

transduce' :: ToTransducer t => t i o s -> Transduction' i o s

Generalized version of transduce that preserves the return value of the Transducer.

>>> L.fold (transduce' (Transducer (\_ i -> ((),[i],[])) () (\_ -> ('r',[],[]))) L.list) [1..7]
('r',[1,2,3,4,5,6,7])

transduceM :: (Monad m, ToTransducerM m t) => t i o s -> TransductionM m i o

Like transduce, but works on monadic Folds.

transduceM' :: (Monad m, ToTransducerM m t) => t i o s -> TransductionM' m i o s

Like transduce', but works on monadic Folds.

transduceK :: Monad m => (i -> m [o]) -> TransductionM m i o

Transduce with a Kleisli arrow that returns a list.

Folding over groups

folds :: ToTransducer t => t a b s -> Fold b c -> Transduction a c

Summarizes each of the groups demarcated by the Transducer using a Fold.

The result value of the Transducer is discarded.

>>> L.fold (folds (chunksOf 3) L.sum L.list) [1..7]
[6,15,7]

folds' :: ToTransducer t => t a b s -> Fold b c -> Transduction' a c s

Like folds, but preserves the return value of the Transducer.

>>> L.fold (folds' (chunksOf 3) L.sum L.list) [1..7]
((),[6,15,7])

foldsM :: (Applicative m, Monad m, ToTransducerM m t) => t a b s -> FoldM m b c -> TransductionM m a c

Monadic version of folds.

foldsM' :: (Applicative m, Monad m, ToTransducerM m t) => t a b s -> FoldM m b c -> TransductionM' m a c s

Monadic version of folds'.

Group operations

type Infinite e = Cofree Identity e

Infinite list of values.

newtype ReifiedTransduction a b

Helper for storing a Transduction safely on a container.

Constructors

ReifiedTransduction

Fields

getTransduction :: Transduction a b

groups

Arguments

:: ToTransducer t

=> t a b s

-> Infinite (ReifiedTransduction b c)

infinite list of transductions

-> Transduction a c

Processes each of the groups demarcated by a Transducer using a Transduction taken from an unending supply, returning a Transduction what works over the undivided stream of inputs.

The return value of the Transducer is discarded.

>>> L.fold (groups (chunksOf 2) (evenly (transduce (surround "<" ">"))) L.list) "aabbccdd"
"<aa><bb><cc><dd>"

>>> :{
    let 
      transducers = flip C.unfold 0 $ \i -> (,)
         (ReifiedTransduction (transduce (surround (show i) []))) 
         (Identity (succ i))
    in L.fold (groups (chunksOf 2) transducers L.list) "aabbccdd"
    :}
"0aa1bb2cc3dd"

evenly :: Transduction b c -> Infinite (ReifiedTransduction b c)

Use the same Transduction for each group.

bisect

Arguments

:: ToTransducer t

=> t a b s

-> Transduction b c

head

-> Transduction b c

-> Transduction a c

Use one transduction to process the first group, and another for the second and all subsequent groups.

type Moore a b = Cofree ((->) a) b

Unending machine that gives you a b whenever you give it an a.

newtype ReifiedTransduction' a b r

Helper for storing a ReifiedTransduction safely on a container.

Constructors

ReifiedTransduction'

Fields

getTransduction' :: Transduction' a b r

groups'

Arguments

:: ToTransducer t

=> t a b s

-> Fold u v

auxiliary Fold that aggregates the u values produced for each group

-> Moore u (ReifiedTransduction' b c u)

a machine that eats u values and spits transductions

-> Transduction' a c (s, v)

Generalized version of groups that preserves the return value of the Transducer.

A summary value for each group is also calculated. These values are aggregated for the whole stream, with the help of an auxiliary Fold.

>>> :{
    let 
        transductions = evenly' $ \f ->
            transduce (surround "<" ">") (liftA2 (,) L.list f)
    in  L.fold (groups' (chunksOf 2) L.list transductions L.list) "aabbccdd"
    :}
(((),["<aa>","<bb>","<cc>","<dd>"]),"<aa><bb><cc><dd>")

evenly' :: Transduction' b c u -> Moore u (ReifiedTransduction' b c u)

Use the same Transduction' for each group.

Ignores the inputs to the Moore machine.

Monadic group operations

newtype ReifiedTransductionM m a b

Helper for storing a TransductionM safely on a container.

Constructors

ReifiedTransductionM

Fields

getTransductionM :: TransductionM m a b

groupsM

Arguments

:: (Monad m, ToTransducerM m t)

=> t a b s

-> Infinite (ReifiedTransductionM m b c)

-> TransductionM m a c

Monadic version of groups.

evenlyM :: TransductionM m b c -> Infinite (ReifiedTransductionM m b c)

Monadic version of evenly.

bisectM

Arguments

:: ToTransducerM m t

=> t a b s

-> TransductionM m b c

head

-> TransductionM m b c

-> TransductionM m a c

Monadic version of bisect.

newtype ReifiedTransductionM' m a b r

Helper for storing a TransductionM' safely on a container.

Constructors

ReifiedTransductionM'

Fields

getTransductionM' :: TransductionM' m a b r

groupsM'

Arguments

:: (Monad m, ToTransducerM m t)

=> t a b s

-> FoldM m u v

-> Moore u (ReifiedTransductionM' m b c u)

a machine that eats u values and spits transductions

-> TransductionM' m a c (s, v)

Monadic version of groups'.

evenlyM' :: TransductionM' m b c u -> Moore u (ReifiedTransductionM' m b c u)

Monadic version of evenly'.

Transducers

ignore :: Transducer a b ()

Ignore all the inputs coming into the fold.

Polymorphic in both inputs and outputs.

surround :: (Traversable p, Traversable s) => p a -> s a -> Transducer a a ()

Adds a prefix and a suffix to the stream arriving into a Fold.

>>> L.fold (transduce (surround "prefix" "suffix") L.list) "middle"
"prefixmiddlesuffix"

Used as a splitter, it puts the prefix, the original stream and the suffix in separate groups:

>>> L.fold (groups (surround "prefix" "suffix") (evenly (transduce (surround "[" "]"))) L.list) "middle"
"[prefix][middle][suffix]"

surroundIO :: (Traversable p, Traversable s, Functor m, MonadIO m) => m (p a) -> m (s a) -> TransducerM m a a ()

Like surround, but the prefix and suffix are obtained using a IO action.

>>> L.foldM (transduceM (surroundIO (return "prefix") (return "suffix")) (L.generalize L.list)) "middle"
"prefixmiddlesuffix"

Splitters

chunksOf :: Int -> Transducer a a ()

Splits a stream into chunks of fixed size.

>>> L.fold (folds (chunksOf 2) L.list L.list) [1..7]
[[1,2],[3,4],[5,6],[7]]

>>> L.fold (groups (chunksOf 2) (evenly (transduce (surround [] [0]))) L.list) [1..7]
[1,2,0,3,4,0,5,6,0,7,0]

splitAt :: Int -> Transducer a a ()

Splits the stream at a given position.

>>> L.fold (bisect (splitAt 2) (transduce ignore) id L.list) [1..5]
[3,4,5]

chunkedSplitAt :: StableFactorialMonoid m => Int -> Transducer m m ()

Similar to splitAt, but works with streams of "chunked" data like bytestrings, texts, vectors, lists of lists...

>>> L.fold (bisect (chunkedSplitAt 7) (transduce ignore) id L.list) [[1..5],[6..9]]
[[8,9]]

splitWhen :: (a -> Bool) -> Transducer a a ()

>>> L.fold (bisect (splitWhen (>3)) id (transduce ignore) L.list) [1..5]
[1,2,3]

splitLast :: Transducer a a (Maybe a)

Puts the last element of the input stream (if it exists) in a separate group.

>>> L.fold (bisect splitLast id (transduce ignore) L.list) [1..5]
[1,2,3,4]

chunkedStripPrefix

Arguments

:: (LeftGCDMonoid i, StableFactorialMonoid i, Traversable t, Monad m)

=> t i

-> TransducerM (ExceptT ([i], Maybe i) m) i i ()

Strip a prefix from a stream of "chunked" data, like packed text.

If the prefix doesn't match, fail with the unmatched part of the prefix and the input that caused the error.

>>> runExceptT $ L.foldM (transduceM (chunkedStripPrefix [[1..2],[3..4]]) (L.generalize L.list)) [[1..5],[6..9]]
Right [[5],[6,7,8,9]]

>>> runExceptT $ L.foldM (transduceM (chunkedStripPrefix [[1..2],[3,77,99]]) (L.generalize L.list)) [[1..5],[6..9]]
Left ([[77,99]],Just [4,5])

Transducer utilities

foldify :: Transducer i o s -> Fold i s

Transforms a Transducer into a Fold by forgetting about the data sent downstream.

foldifyM :: Functor m => TransducerM m i o s -> FoldM m i s

Monadic version of foldify.

condense :: Fold a r -> Transducer a r r

Transforms a Fold into a Transducer that sends the return value of the Fold downstream when upstream closes.

condenseM :: Applicative m => FoldM m a r -> TransducerM m a r r

Monadic version of condense.

hoistTransducer :: Monad m => (forall a. m a -> n a) -> TransducerM m i o s -> TransducerM n i o s

Changes the base monad used by a TransducerM.

Fold utilities

quiesce :: Monad m => FoldM (ExceptT e m) a r -> FoldM m a (Either e r)

Turn a FoldM that fails abruptly into one that encodes the error into its return value.

Can be useful when combining fallible FoldMs with non-fallible ones.

>>> L.foldM (quiesce (FoldM (\_ _-> throwE ()) (return ()) (\_ -> throwE ()))) [1..7]
Left ()

quiesceWith :: (Functor m, Monad m) => FoldM m a v -> FoldM (ExceptT e m) a r -> FoldM m a (Either (e, v) r)

Generalized version of quiesce to turn a fallible FoldM into another that starts a "fallback fold" when it encounters an error.

"Start folding this way, if you encounter an error, start folding this other way".

>>> L.foldM (quiesceWith (L.generalize L.length) (FoldM (\_ _-> throwE ()) (return ()) (\_ -> throwE ()))) [1..7]
Left ((),7)

hoistFold :: Monad m => (forall a. m a -> n a) -> FoldM m i r -> FoldM n i r

Changes the base monad used by a FoldM.

Re-exports

module Data.Functor.Extend

module Control.Foldl

module Control.Comonad.Cofree