Control.Foldl.Transduce

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

>>> L.fold (transduce (surround "[" "]") L.list) "middle"
"[middle]"

>>> L.fold (folds (chunksOf 2) L.length L.list) "aabbccdd"
[2,2,2,2]

>>> L.fold (groups (chunksOf 2) (surround "[" "]") L.list) "aabbccdd"
"[aa][bb][cc][dd]"

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

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

Instances

ToTransductions' Transducer

Methods

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

ToTransducer Transducer

Methods

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

Monad m => ToTransductionsM' m Transducer

Methods

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

Monad m => ToTransducerM m Transducer

Methods

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

Bifunctor (Transducer i)

Methods

bimap :: (a -> b) -> (c -> d) -> Transducer i a c -> Transducer i b d

first :: (a -> b) -> Transducer i a c -> Transducer i b c

second :: (b -> c) -> Transducer i a b -> Transducer i a c

Functor (Transducer i o)

Methods

fmap :: (a -> b) -> Transducer i o a -> Transducer i o b

(<$) :: a -> Transducer i o b -> Transducer i o a

Comonad (Transducer i o)

Methods

extract :: Transducer i o a -> a

duplicate :: Transducer i o a -> Transducer i o (Transducer i o a)

extend :: (Transducer i o a -> b) -> Transducer i o a -> Transducer i o b

Extend (Transducer i o)

Methods

duplicated :: Transducer i o a -> Transducer i o (Transducer i o a)

extended :: (Transducer i o a -> b) -> Transducer i o a -> Transducer i o b

class ToTransducer t where

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

Minimal complete definition

toTransducer

Methods

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

Instances

ToTransducer Transducer

Methods

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

ToTransducer (TransducerM Identity)

Methods

toTransducer :: TransducerM Identity i o r -> Transducer i o r

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

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

Instances

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

Methods

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

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

Methods

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

ToTransducer (TransducerM Identity)

Methods

toTransducer :: TransducerM Identity i o r -> Transducer i o r

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

Methods

bimap :: (a -> b) -> (c -> d) -> TransducerM m i a c -> TransducerM m i b d

first :: (a -> b) -> TransducerM m i a c -> TransducerM m i b c

second :: (b -> c) -> TransducerM m i a b -> TransducerM m i a c

Monad m => Functor (TransducerM m i o)

Methods

fmap :: (a -> b) -> TransducerM m i o a -> TransducerM m i o b

(<$) :: a -> TransducerM m i o b -> TransducerM m i o a

Monad m => Extend (TransducerM m i o)

Methods

duplicated :: TransducerM m i o a -> TransducerM m i o (TransducerM m i o a)

extended :: (TransducerM m i o a -> b) -> TransducerM m i o a -> TransducerM m i o b

class ToTransducerM m t where

Helps converting pure transducers into monadic ones.

Minimal complete definition

toTransducerM

Methods

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

Instances

Monad m => ToTransducerM m Transducer

Methods

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

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

Methods

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

Applying transducers

transduce :: ToTransducer t => t i o () -> Transduction i o

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

>>> L.fold (transduce (Transducer (\_ i -> ((),[i],[])) () (\_ -> ((),[],[]))) 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 () -> 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 ()

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

-> 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 Transduction' safely on a container.

Constructors

ReifiedTransduction'

Fields

• getTransduction' :: Transduction' a b r

Instances

ToTransductions' ReifiedTransduction'

Methods

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

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

Methods

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

class ToTransductions' t where

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

Minimal complete definition

toTransductions'

Methods

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

Instances

ToTransductions' Moore

Methods

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

ToTransductions' Transducer

Methods

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

ToTransductions' ReifiedTransduction'

Methods

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

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

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

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

Methods

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

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

Methods

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

class Monad m => ToTransductionsM' m t where

Monadic version of ToTransductions'.

Minimal complete definition

toTransductionsM'

Methods

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

Instances

Monad m => ToTransductionsM' m Transducer

Methods

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

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

Methods

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

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

Methods

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

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

Methods

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

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

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

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

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

>>> L.fold (folds (split (==2)) L.list L.list) [1,2,2,1,1,2,1]
[[1],[],[1,1],[1]]

>>> L.fold (folds (split (==2)) L.list L.list) [2,1,1,2]
[[],[1,1],[]]

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 (void 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

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.

Another name for hoists.

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.

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

newtype Fallible m r i e

Constructors

Fallible

Fields

• getFallible :: FoldM (ExceptT e m) i r

Instances

(Functor m, Monad m, Monoid r) => Choice (Fallible m r)

Fail immediately when an input comes in the wrong branch.

Methods

left' :: Fallible m r a b -> Fallible m r (Either a c) (Either b c)

right' :: Fallible m r a b -> Fallible m r (Either c a) (Either c b)

(Functor m, Monad m) => Profunctor (Fallible m r)

Methods

dimap :: (a -> b) -> (c -> d) -> Fallible m r b c -> Fallible m r a d

lmap :: (a -> b) -> Fallible m r b c -> Fallible m r a c

rmap :: (b -> c) -> Fallible m r a b -> Fallible m r a c

(#.) :: Coercible * c b => (b -> c) -> Fallible m r a b -> Fallible m r a c

(.#) :: Coercible * b a => Fallible m r b c -> (a -> b) -> Fallible m r a c

(Functor m, Monad m) => Monad (Fallible m r i)

>>= continues folding after an error using a Fallible constructed from the error.

Methods

(>>=) :: Fallible m r i a -> (a -> Fallible m r i b) -> Fallible m r i b

(>>) :: Fallible m r i a -> Fallible m r i b -> Fallible m r i b

return :: a -> Fallible m r i a

fail :: String -> Fallible m r i a

(Functor m, Monad m) => Functor (Fallible m r i)

Methods

fmap :: (a -> b) -> Fallible m r i a -> Fallible m r i b

(<$) :: a -> Fallible m r i b -> Fallible m r i a

(Functor m, Monad m) => Applicative (Fallible m r i)

pure creates a Fallible that starts in a failed state.

Methods

pure :: a -> Fallible m r i a

(<*>) :: Fallible m r i (a -> b) -> Fallible m r i a -> Fallible m r i b

liftA2 :: (a -> b -> c) -> Fallible m r i a -> Fallible m r i b -> Fallible m r i c

(*>) :: Fallible m r i a -> Fallible m r i b -> Fallible m r i b

(<*) :: Fallible m r i a -> Fallible m r i b -> Fallible m r i a

class ToFold t where

Minimal complete definition

toFold

Methods

toFold :: t i r -> Fold i r

Instances

ToFold Fold

Methods

toFold :: Fold i r -> Fold i r

ToFold (FoldM Identity)

Methods

toFold :: FoldM Identity i r -> Fold i r

class ToFoldM m t where

Minimal complete definition

toFoldM

Methods

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

Instances

Monad m => ToFoldM m Fold

Methods

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

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

Methods

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

Deprecated

Re-exports

module Data.Functor.Extend

module Control.Foldl

module Control.Comonad.Cofree

Orphan instances

Extend (Fold a)

Methods

duplicated :: Fold a a -> Fold a (Fold a a)

extended :: (Fold a a -> b) -> Fold a a -> Fold a b

Monad m => Extend (FoldM m a)

Methods

duplicated :: FoldM m a a -> FoldM m a (FoldM m a a)

extended :: (FoldM m a a -> b) -> FoldM m a a -> FoldM m a b