transducers for foldl Folds

[Daniel Díaz]

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!

[Gabriel Gonzalez]

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.

--
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-pipe...@googlegroups.com.
To post to this group, send email to haskel...@googlegroups.com.

[Daniel Díaz]

> It's not clear to me whether `Handler` is as powerful as the `Transducer` type, but I'm guessing that it is not.

I think `Transducer` is a bit more general. It can maintain its own state (allowing stuff like stateful decoders). And while it can't change the "done" function of the Fold, it can delay invoking it, potentially generating more input for the Fold after entering its own "done" (like the "surround" transducer does).