Safe Haskell | Safe |
---|---|
Language | Haskell98 |
Control.Foldl.Transduce
Contents
Description
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]"
- type Transduction a b = forall x. Fold b x -> Fold a x
- type Transduction' a b r = forall x. Fold b x -> Fold a (r, x)
- data Transducer i o r = forall x . Transducer (x -> i -> (x, [o], [[o]])) x (x -> (r, [o], [[o]]))
- class ToTransducer t where
- toTransducer :: t i o r -> Transducer i o r
- type TransductionM m a b = forall x. Monad m => FoldM m b x -> FoldM m a x
- type TransductionM' m a b r = forall x. FoldM m b x -> FoldM m a (r, x)
- data TransducerM m i o r = forall x . TransducerM (x -> i -> m (x, [o], [[o]])) (m x) (x -> m (r, [o], [[o]]))
- class ToTransducerM m t where
- toTransducerM :: t i o r -> TransducerM m i o r
- transduce :: ToTransducer t => t i o () -> Transduction i o
- transduce' :: ToTransducer t => t i o s -> Transduction' i o s
- transduceM :: (Monad m, ToTransducerM m t) => t i o () -> TransductionM m i o
- transduceM' :: (Monad m, ToTransducerM m t) => t i o s -> TransductionM' m i o s
- transduceK :: Monad m => (i -> m [o]) -> TransductionM m i o
- folds :: (ToTransducer t, ToFold f) => t a b () -> f b c -> Transduction a c
- folds' :: (ToTransducer t, ToFold f) => t a b s -> f b c -> Transduction' a c s
- foldsM :: (Applicative m, Monad m, ToTransducerM m t, ToFoldM m f) => t a b () -> f b c -> TransductionM m a c
- foldsM' :: (Applicative m, Monad m, ToTransducerM m t, ToFoldM m f) => t a b s -> f b c -> TransductionM' m a c s
- newtype ReifiedTransduction' a b r = ReifiedTransduction' {
- getTransduction' :: Transduction' a b r
- reify :: Transduction a b -> ReifiedTransduction' a b ()
- reify' :: Transduction' a b r -> ReifiedTransduction' a b r
- newtype Moore a b u = Moore {
- getMoore :: Cofree ((->) u) (ReifiedTransduction' a b u)
- class ToTransductions' t where
- toTransductions' :: t a b u -> Moore a b u
- moveHead :: (ToTransductions' h, ToTransductions' t) => h a b u -> t a b u -> Moore a b u
- groups :: (ToTransducer s, ToTransductions' t) => s a b () -> t b c () -> Transduction a c
- bisect :: (ToTransducer s, ToTransductions' h, ToTransductions' t) => s a b () -> h b c () -> t b c () -> Transduction a c
- groups' :: (ToTransducer s, ToTransductions' t, ToFold f) => s a b r -> t b c u -> f u v -> Transduction' a c (r, v)
- newtype ReifiedTransductionM' m a b r = ReifiedTransductionM' {
- getTransductionM' :: TransductionM' m a b r
- reifyM :: Monad m => TransductionM m a b -> ReifiedTransductionM' m a b ()
- reifyM' :: TransductionM' m a b r -> ReifiedTransductionM' m a b r
- newtype MooreM m a b u = MooreM {
- getMooreM :: Cofree ((->) u) (ReifiedTransductionM' m a b u)
- class Monad m => ToTransductionsM' m t where
- toTransductionsM' :: t 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
- groupsM :: (Monad m, ToTransducerM m s, ToTransductionsM' m t) => s a b () -> t b c () -> TransductionM m a c
- bisectM :: (Monad m, ToTransducerM m s, ToTransductionsM' m h, ToTransductionsM' m t) => s a b () -> h b c () -> t b c () -> TransductionM m a c
- groupsM' :: (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)
- ignore :: Transducer a b ()
- surround :: (Traversable p, Traversable s) => p a -> s a -> Transducer a a ()
- surroundIO :: (Traversable p, Traversable s, Functor m, MonadIO m) => m (p a) -> m (s a) -> TransducerM m a a ()
- chunksOf :: Int -> Transducer a a ()
- split :: (a -> Bool) -> Transducer a a ()
- splitAt :: Int -> Transducer a a ()
- chunkedSplitAt :: StableFactorialMonoid m => Int -> Transducer m m ()
- splitLast :: Transducer a a (Maybe a)
- break :: (a -> Bool) -> Transducer a a ()
- chunkedStripPrefix :: (LeftGCDMonoid i, StableFactorialMonoid i, Traversable t, Monad m) => t i -> TransducerM (ExceptT ([i], Maybe i) m) i i ()
- foldify :: Transducer i o s -> Fold i s
- foldifyM :: Functor m => TransducerM m i o s -> FoldM m i s
- condense :: Fold a r -> Transducer a r r
- condenseM :: Applicative m => FoldM m a r -> TransducerM m a r r
- hoistTransducer :: Monad m => (forall a. m a -> n a) -> TransducerM m i o s -> TransducerM n i o s
- hoistFold :: Monad m => (forall a. m a -> n a) -> FoldM m i r -> FoldM n i r
- unit :: Fold a ()
- trip :: Monad m => FoldM (ExceptT a m) a ()
- quiesce :: Monad m => FoldM (ExceptT e m) a r -> FoldM m a (Either e r)
- newtype Fallible m r i e = Fallible {
- getFallible :: FoldM (ExceptT e m) i r
- class ToFold t where
- class ToFoldM m t where
- module Data.Functor.Extend
- module Control.Foldl
- module Control.Comonad.Cofree
Transducer types
type Transduction a b = forall x. Fold b x -> Fold a x Source
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) Source
A more general from of Transduction
that adds new information to the
return value of the Fold
.
data Transducer i o r Source
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.
Transducer
s 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 Transducer
s 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 Source | |
ToTransducer Transducer Source | |
Monad m => ToTransductionsM' m Transducer Source | |
Monad m => ToTransducerM m Transducer Source | |
Bifunctor (Transducer i) Source | |
Functor (Transducer i o) Source | |
Comonad (Transducer i o) Source | |
Extend (Transducer i o) Source |
class ToTransducer t where Source
Helps converting monadic transducers (over Identity
) into pure ones.
Methods
toTransducer :: t i o r -> Transducer i o r Source
Instances
Monadic transducer types
type TransductionM m a b = forall x. Monad m => FoldM m b x -> FoldM m a x Source
Like Transduction
, but works on monadic Fold
s.
type TransductionM' m a b r = forall x. FoldM m b x -> FoldM m a (r, x) Source
Like Transduction'
, but works on monadic Fold
s.
data TransducerM m i o r Source
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') Source | |
(~) (* -> *) m m' => ToTransducerM m (TransducerM m') Source | |
ToTransducer (TransducerM Identity) Source | |
(Functor m, Monad m) => Bifunctor (TransducerM m i) Source | |
Monad m => Functor (TransducerM m i o) Source | |
Monad m => Extend (TransducerM m i o) Source |
class ToTransducerM m t where Source
Helps converting pure transducers into monadic ones.
Methods
toTransducerM :: t i o r -> TransducerM m i o r Source
Instances
Monad m => ToTransducerM m Transducer Source | |
(~) (* -> *) m m' => ToTransducerM m (TransducerM m') Source |
Applying transducers
transduce :: ToTransducer t => t i o () -> Transduction i o Source
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 Source
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 Source
transduceM' :: (Monad m, ToTransducerM m t) => t i o s -> TransductionM' m i o s Source
Like transduce'
, but works on monadic Fold
s.
transduceK :: Monad m => (i -> m [o]) -> TransductionM m i o Source
Transduce with a Kleisli arrow that returns a list.
Folding over groups
Arguments
:: (ToTransducer t, ToFold f) | |
=> t a b () |
|
-> 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]
Arguments
:: (ToTransducer t, ToFold f) | |
=> t a b s |
|
-> 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])
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
.
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 Source
Helper for storing a Transduction'
safely on a container.
Constructors
ReifiedTransduction' | |
Fields
|
Instances
reify :: Transduction a b -> ReifiedTransduction' a b () Source
Convenience constructor, often useful with pure functions like id
.
reify' :: Transduction' a b r -> ReifiedTransduction' a b r Source
An unending machine that eats u
values and returns
ReifiedTransduction'
s whose result type is also u
.
Constructors
Moore | |
Fields
|
Instances
class ToTransductions' t where Source
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 Source
moveHead :: (ToTransductions' h, ToTransductions' t) => h a b u -> t a b u -> Moore a b u Source
Prepend the head of the first argument to the second argument.
Arguments
:: (ToTransducer s, ToTransductions' t) | |
=> s a b () |
|
-> 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"
Arguments
:: (ToTransducer s, ToTransductions' h, ToTransductions' t) | |
=> s a b () |
|
-> 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"
Arguments
:: (ToTransducer s, ToTransductions' t, ToFold f) | |
=> s a b r |
|
-> t b c u | machine that eats |
-> f u v | auxiliary |
-> 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 Source
Helper for storing a TransductionM'
safely on a container.
Constructors
ReifiedTransductionM' | |
Fields
|
Instances
((~) (* -> *) m m', Monad m') => ToTransductionsM' m (ReifiedTransductionM' m') Source |
reifyM :: Monad m => TransductionM m a b -> ReifiedTransductionM' m a b () Source
Monadic version of reify
.
reifyM' :: TransductionM' m a b r -> ReifiedTransductionM' m a b r Source
Monadic version of reifyM
.
Monadic version of Moore
.
Constructors
MooreM | |
Fields
|
Instances
((~) (* -> *) m m', Monad m') => ToTransductionsM' m (MooreM m') Source |
class Monad m => ToTransductionsM' m t where Source
Monadic version of ToTransductions'
.
Methods
toTransductionsM' :: t a b u -> MooreM m a b u Source
Instances
Monad m => ToTransductionsM' m Transducer Source | |
((~) (* -> *) m m', Monad m') => ToTransductionsM' m (ReifiedTransductionM' m') Source | |
((~) (* -> *) m m', Monad m') => ToTransductionsM' m (TransducerM m') Source | |
((~) (* -> *) m m', Monad m') => ToTransductionsM' m (MooreM m') Source |
moveHeadM :: (Monad m, ToTransductionsM' m h, ToTransductionsM' m t) => h a b u -> t a b u -> MooreM m a b u Source
Monadic version of moveHead
.
Arguments
:: (Monad m, ToTransducerM m s, ToTransductionsM' m t) | |
=> s a b () | |
-> t b c () | |
-> TransductionM m a c |
Monadic version of groups
.
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
.
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 () Source
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 () Source
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 () Source
Splitters
chunksOf :: Int -> Transducer a a () Source
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 () Source
>>>
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 () Source
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 () Source
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) Source
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 () Source
>>>
L.fold (bisect (break (>3)) (reify id) ignore L.list) [1..5]
[1,2,3]
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 Source
Transforms a Transducer
into a Fold
by forgetting about the data sent
downstream.
condense :: Fold a r -> Transducer a r r Source
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 Source
Monadic version of condense
.
hoistTransducer :: Monad m => (forall a. m a -> n a) -> TransducerM m i o s -> TransducerM n i o s Source
Changes the base monad used by a TransducerM
.
Fold utilities
trip :: Monad m => FoldM (ExceptT a m) a () Source
A fold that fails if it receives any input at all. The received input is used as the error.
newtype Fallible m r i e Source
Constructors
Fallible | |
Fields
|
Instances
(Functor m, Monad m, Monoid r) => Choice (Fallible m r) Source | Fail immediately when an input comes in the wrong branch. |
(Functor m, Monad m) => Profunctor (Fallible m r) Source | |
(Functor m, Monad m) => Monad (Fallible m r i) Source |
|
(Functor m, Monad m) => Functor (Fallible m r i) Source | |
(Functor m, Monad m) => Applicative (Fallible m r i) Source |
Deprecated
Re-exports
module Data.Functor.Extend
module Control.Foldl
module Control.Comonad.Cofree