I just want to mention that the `foldl` library already has a type that
is similar to a `Transduction`: the `Handler` type, which is one type of
"lens":
type Handler a b = forall x. (b -> Constant (Endo x) b) -> a ->
Constant (Endo x) a
... and the `handles` function, which converts it to a function between
`Fold`s:
handles :: Handler a b -> Fold b r -> Fold a r
handles k (Fold step begin done) = Fold step' begin done
where
step' = flip (appEndo . getConstant . k (Constant . Endo . flip
step))
This means that every lens that type-checks as a `Handler` is a
transducer for free. For example:
handles _1 :: Fold a b -> Fold (a, x) b
handles _Just :: Fold a b -> Fold (Maybe a) b
handles _traverse :: Fold a b -> Fold [a] b
The easy way to reason about how this type works is to write the
`Handler` type as the following isomorphic type:
type Handler a b ≅forall x . (x -> b -> x) -> (x -> a -> x)
In other words, a `Handler` is just a transformation of a `Fold`'s step
function. In theory this means that a `Handler` is almost as powerful
as the `Transduction` type. The one thing the `Handler` cannot do is
transform the `Fold`'s initial state (i.e. the "begin" field). Note
that the `Handler` also cannot transform the `done` function, but
neither can `Transduction` (because of parametricity).
It's not clear to me whether `Handler` is as powerful as the
`Transducer` type, but I'm guessing that it is not.
Also, it's totally fine if you use `foldl-transduce`. I wasn't planning
on using that module name and I'm creative at naming things anyway in
the presence of name conflicts.
On 8/23/2015 3:47 AM, Daniel Díaz wrote:
Hi,
I was watching Rich Hickey's presentations on transducers and decided
to implement something like it for foldl folds, as an exercise.
The repo is here: https://github.com/danidiaz/foldl-transduce
import qualified Control.Foldl as L
import Control.Foldl.Transduce
import Control.Foldl.Transduce.Text
The main types are
type Transduction a b = forall x. Fold b x -> Fold a x
data Transducer i o r
= forall x. Transducer (x -> i -> (x,[o])) x (x -> (r,[o]))
A Transducer is like a Fold that can emit output downstream. A
Transducer can be applied to a Fold with the "transduce" function:
transduce :: Transducer i o r -> Transduction i o
A very simple Transducer is "surround" that adds a prefix and a suffix
to the stream of data coming to a Fold:
>>> L.fold (transduce (surround "prefix" "suffix") L.list) "middle"
"prefixmiddlesuffix"
Then there's also decoding transducers:
>>> L.fold (transduce utf8lenient L.list) (map fromString
["decode","this"])
["decode","this"]
And also transducer analogues of some functions from pipes-group
(they're less powerful though, in that they force you to treat every
group the same way):
>>> L.fold (groups (chunksOf 2) (transduce (surround [] [0]))
L.list) [1..7]
[1,2,0,3,4,0,5,6,0,7,0]
The existence of pipes makes transducers a bit superflous I suppose.
Anyway, once I add some tests and iron out the (very likely) space
leaks, I was thinking of putting this on Hackage as foldl-transduce
(if Gabriel doesn't mind, I don't want to "name squat" on the foldl-*
namespace.)
Any comments or bug reports welcome!
--
You received this message because you are subscribed to the Google
Groups "Haskell Pipes" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to haskell-pipes+unsubscr...@googlegroups.com
<mailto:haskell-pipes+unsubscr...@googlegroups.com>.
To post to this group, send email to haskell-pipes@googlegroups.com
<mailto:haskell-pipes@googlegroups.com>.
--
You received this message because you are subscribed to the Google Groups "Haskell
Pipes" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to haskell-pipes+unsubscr...@googlegroups.com.
To post to this group, send email to haskell-pipes@googlegroups.com.
