Understanding Clojure transducers through types

Yesterday, Rich Hickey published a blog post, “Transducers are Coming”, which attracted a lot of attention.

I have a confession to make, which I have made before: I find it very difficult to understand ideas or code not presented with types. So I decided that the only way I could possibly understand what “transducers” are would be to actually implement them in a typed language. I ended up doing so and am sharing my findings here.

Vague types in the original blog post

Rich informally gave some type signatures in his blog post:

;;reducing function signature
whatever, input -> whatever

;;transducer signature
(whatever, input -> whatever) -> (whatever, input -> whatever)

This was, unfortunately, not very helpful. It is hard to make sense of this pseudo-notation for types. What is quantified over what? And what is bound to what? I’ll explain later what I mean by these questions.

First discussion thread I saw

There was much tweeting online about transducers after Rich Hickey’s initial announcement; the tweets did not help me, except for links posted to discussion elsewhere.

One of them was on Hacker News. I browsed through it but found it mostly not useful. The problem was that although a lot of interesting Haskell code was thrown around, it tended to be related to transducers but not an exact translation of the concept. I already had my own intuitions about transducers being related to well-known types such as foldables, iteratees, lenses, etc. That “ordinary function composition” was involved immediately suggested the connections, because function composition is huge in these existing Haskell libraries.

But what I wanted was to understand transducers as they are, before even thinking about generalizations and comparisons.

What are the types?

Rich Hickey informally offered some types (which he said were “a la Haskell”) to try to help out:

    ;;reducing fn
    x->a->x

    ;;transducer fn
    (x->a->x)->(x->b->x)

OK, by using type variables a, b, and x, that indicates what is bound to what. The blog post should have used this notation rather than

;;transducer signature
(whatever, input -> whatever) -> (whatever, input -> whatever)

Sample Clojure code

He also posted some sample Clojure code: