1. 4

When Rich Hickey announced Transducers a few days ago I got excited. They felt very similar to some CPS transformation tricks I’d begun to analyze deeply in Haskell. Thus, I tried to translate the concept into Haskell. This seems to have inspired a few others to examine this avenue.

This post is my current best understanding of Transducers via Haskell types. I want to emphasize that this isn’t intended to be a complete analysis—there’s a good chance that the type I give doesn’t well-represent transducers due to the loss of flexibility you get when directly translating to a strongly typed language.

My hope is that this analysis will provide a window to better understand transducers and a few avenues to try new constructions with them. For instance, I build a Haskell Arrow instance for Transducer and that suggests it might be nice to see an arrow syntax macro in Clojure.

  1.  

  2. 1

    It seems to me that the definition for the second part of this article is somewhat similar to how stream fusion is implemented in Haskell. Could someone care to discuss the relationship?

    Edit: Seems Don Stewart already picked up on this on Reddit, guess I was somewhat right.

    1. 2

      I’m not familiar exactly with stream fusion—I’ve never looked at the actual code. I usually think of it as being done as is described in this paper by Gibbons, though.

      http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf

      The closest thing between my article and Gibbon’s encoding is the

      forall r . (r -> a -> r) -> r -> r
      ==
      [a]
      

      bit. This is equivalent to the Church encoding over Gibbon’s Maybe2 Functor. He uses Maybe2 to generate a model of stream fusion but uses the Co-Church encoding instead!

      Which I’ll be doing in the next article :)