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, along with any pending output.

Constructors

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

Instances

ToTransductions' Transducer

ToTransducer Transducer

Monad m => ToTransductionsM' m 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', Monad m') => ToTransductionsM' m (TransducerM m')

(~) (* -> *) 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

Arguments

:: (ToTransducer t, ToFold f)

=> t a b s

Transducer working as a splitter.

-> f 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'

Arguments

:: (ToTransducer t, ToFold f)

=> t a b s

Transducer working as a splitter.

-> f 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

Arguments

:: (Applicative m, Monad m, ToTransducerM m t, ToFoldM m f)

=> t a b s

-> f b c

-> TransductionM m a c

Monadic version of folds.

foldsM'

Arguments

:: (Applicative m, Monad m, ToTransducerM m t, ToFoldM m f)

=> t a b s

-> f b c

-> TransductionM' m a c s

Monadic version of folds'.

Group operations

newtype ReifiedTransduction' a b r

Helper for storing a ReifiedTransduction' safely on a container.

Constructors

ReifiedTransduction'

Fields

getTransduction' :: Transduction' a b r

Instances

ToTransductions' ReifiedTransduction'

reify :: Transduction a b -> ReifiedTransduction' a b ()

Convenience constructor, often useful with pure functions like id.

reify' :: Transduction' a b r -> ReifiedTransduction' a b r

newtype Moore a b u

An unending machine that eats u values and returns ReifiedTransduction's whose result type is also u.

Constructors

Moore

Fields

getMoore :: Cofree ((->) u) (ReifiedTransduction' a b u)

Instances

ToTransductions' Moore

class ToTransductions' t where

Helper for obtaining infinite sequences of Transduction's from suitable types (in order to avoid explicit conversions).

Methods

toTransductions' :: t a b u -> Moore a b u

Instances

ToTransductions' Moore

ToTransductions' Transducer

ToTransductions' ReifiedTransduction'

moveHead :: (ToTransductions' h, ToTransductions' t) => h a b u -> t a b u -> Moore a b u

Prepend the head of the first argument to the second argument.

groups

Arguments

:: (ToTransducer s, ToTransductions' t)

=> s a b r

Transducer working as a splitter.

-> t 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) (surround "<" ">") L.list) "aabbccdd"
"<aa><bb><cc><dd>"

>>> :{
    let transductions = Moore (C.unfold (\i ->
          (reify (transduce (surround (show i) [])), \_ -> succ i)) 0)
    in L.fold (groups (chunksOf 2) transductions L.list) "aabbccdd"
    :}
"0aa1bb2cc3dd"

bisect

Arguments

:: (ToTransducer s, ToTransductions' h, ToTransductions' t)

=> s a b r

Transducer working as a splitter.

-> h b c ()

Machine to process the first group

-> t b c ()

Machine to process the second and subsequent groups

-> Transduction a c

Use a different Transduction for the first detected group.

>>> :{
    let drop n = bisect (splitAt n) ignore (reify id)
    in L.fold (drop 2 L.list) "aabbccdd"
    :}
"bbccdd"

groups'

Arguments

:: (ToTransducer s, ToTransductions' t, ToFold f)

=> s a b r

Transducer working as a splitter.

-> t b c u

machine that eats u values and spits transductions

-> f u v

auxiliary Fold that aggregates the u values produced for each group

-> Transduction' a c (r, 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 = 
          reify' (\f -> transduce (surround "<" ">") ((,) <$> L.list <*> f))
    in L.fold (groups' (chunksOf 2) transductions L.list L.list) "aabbccdd"
    :}
(((),["<aa>","<bb>","<cc>","<dd>"]),"<aa><bb><cc><dd>")

Monadic group operations

newtype ReifiedTransductionM' m a b r

Helper for storing a TransductionM' safely on a container.

Constructors

ReifiedTransductionM'

Fields

getTransductionM' :: TransductionM' m a b r

Instances

((~) (* -> *) m m', Monad m') => ToTransductionsM' m (ReifiedTransductionM' m')

reifyM :: Monad m => TransductionM m a b -> ReifiedTransductionM' m a b ()

Monadic version of reify.

reifyM' :: TransductionM' m a b r -> ReifiedTransductionM' m a b r

Monadic version of reifyM.

newtype MooreM m a b u

Monadic version of Moore.

Constructors

MooreM

Fields

getMooreM :: Cofree ((->) u) (ReifiedTransductionM' m a b u)

Instances

((~) (* -> *) m m', Monad m') => ToTransductionsM' m (MooreM m')

class Monad m => ToTransductionsM' m t where

Monadic version of ToTransductions'.

Methods

toTransductionsM' :: t a b u -> MooreM m a b u

Instances

Monad m => ToTransductionsM' m Transducer

((~) (* -> *) m m', Monad m') => ToTransductionsM' m (ReifiedTransductionM' m')

((~) (* -> *) m m', Monad m') => ToTransductionsM' m (TransducerM m')

((~) (* -> *) m m', Monad m') => ToTransductionsM' m (MooreM m')

moveHeadM :: (Monad m, ToTransductionsM' m h, ToTransductionsM' m t) => h a b u -> t a b u -> MooreM m a b u

Monadic version of moveHead.

groupsM

Arguments

:: (Monad m, ToTransducerM m s, ToTransductionsM' m t)

=> s a b r

-> t b c ()

-> TransductionM m a c

Monadic version of groups.

bisectM

Arguments

:: (Monad m, ToTransducerM m s, ToTransductionsM' m h, ToTransductionsM' m t)

=> s a b r

-> h b c ()

-> t b c ()

-> TransductionM m a c

Monadic version of bisect.

groupsM'

Arguments

:: (Monad m, ToTransducerM m s, ToTransductionsM' m t, ToFoldM m f)

=> s a b r

-> t b c u

-> f u v

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

Monadic version of groups'.

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") (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) (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) ignore (reify 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) ignore (reify id) L.list) [[1..5],[6..9]]
[[8,9]]

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 (reify id) ignore L.list) [1..5]
[1,2,3,4]

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

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

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.

unit :: Fold a ()

The "do-nothing" fold.

trip :: Monad m => FoldM (ExceptT a m) a ()

A fold that fails if it receives any input at all. The received input is used as the error.

class ToFold t where

Methods

toFold :: t i r -> Fold i r

Instances

ToFold Fold

ToFold (FoldM Identity)

class ToFoldM m t where

Methods

toFoldM :: t i r -> FoldM m i r

Instances

Monad m => ToFoldM m Fold

(~) (* -> *) m m' => ToFoldM m (FoldM m')

Re-exports

module Data.Functor.Extend

module Control.Foldl

module Control.Comonad.Cofree

Deprecated

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

Deprecated: use break instead