That said.

I somewhat disliked Hickey's presentation of typing transducers here. I feel as though he builds a number of strawmen toward typing and then tries to knock them down and suggest that either Clojure has some kind of mystical mechanism that is ineffable to types or that the exercise of typing transducers is wasteful. I disagree on both accounts, I suppose. I think types are useful for analysis and teaching.

The two major points he seems to make is that in order to "properly type" transducers you must

    1. Index the type of the "accumulation so far" so 
       that it cannot be transformed out-of-order
    2. Implement early stopping "without wrapping anything
       except for the reduced value"

With respect to the first point, the major concern appears to be prohibiting behavior loosely described as "applying the reducing function, say, 3 times and then returning the first resulting accumulation". In some sense, the idea is to force us to be faithful in passing on the accumulating parameter. In code, a pathological setting is the following:

    transduce :: (r -> a -> r) -> (r -> a -> r)
    transduce reduce accu0 a = 
      let acc1 = reduce acc0 a
          acc2 = reduce acc1 a
          acc3 = reduce acc2 a
      in  acc1

    transduce :: (r -> a -> r) -> (r -> a -> r)
    transduce reduce accu0 a = 
      let acc1 = reduce acc0 a
      in  acc1

    type Transducer a b = forall r . (r -> b -> r) -> (r -> a -> r)

(It must be noted that the model given above is isomorphic to a "Kleisli arrow on the list monad" which I described a little bit here http://jspha.com/posts/typing-transducers/. It should also be noted that this model includes neither (a) the ability to use local state to capture time-varying transductions or (b) the ability to terminate early)

With respect to the second point, I'd like to suggest that there is a difference between the semantic weight of wrapping the result types in an Either in order to indicate early termination and the implementation weight. I completely agree that using an Either to implement early stopping (as it's easy, if finicky for the library implementor, to do) will involve wrapping and unwrapping the "state" of the transduction continuously. I also would like to suggest that it's a very natural way of representing the "accumulation | reduction" notion Hickey uses in his own "Omnigraffle 8000 type system".

We really would like to capture the idea of the transducer state as being "either" in-progress or fully-reduced and act accordingly. If Clojure's implementation of that requires fewer runtime tags than an Either, so be it, but I personally fail to see a semantic difference except in the way one can play fast-and-loose with dynamic types over static types to begin with.

---

So, I gave above an implementation of Transducers in types which has some of their properties, but certainly not all. In fact, I abused the fact that there is no ambient state in Haskell in order to ensure that a certain property would hold (notably this doesn't require a type system at all, just purity). I also argued that using Either is a perfectly natural way to implement early termination in such a transduction pipeline.

I've also made an extension to the `(r->b->r) -> (r->a->r)` mechanism which enables local state to be enabled for various components of the transduction pipeline. A version without early termination is available here:

https://gist.github.com/tel/714a5ea2e015d918f135

Notably, this uses most of the same typing tricks as `(r->b->r) -> (r->a->r)` but adds a "reduction local hidden state" variable which lets us implement `take` and `partition`. This takes Hickey's notion of needing to be explicit about the state being used to a whole new level.

---

So what is the point of all this?

I'd like to argue that Transducers do not present such a mysterious mechanism that they cannot be sanely typed in a reasonably rich language. I believe that I can capture most of their salient features in types without using the dependent indexing Hickey suggested was necessary.

More than this, the compartmentalized, hidden reducer-local state in the Gist implementation allows for each reduction step to include fairly exotic local states in their state machine. You could implement a kind of type indexing here if desired and no end-user would ever know of its existence.

I also absolutely concede that many type systems people regularly use could not achieve this kind of encoding.

Finally, what I really want to say is that type systems are not something to be denigrated. I believe some of the earliest "transducers v. types" argumentation took a nasty turn as amateur type theorists (myself included) rushed to write things like "Transducers are just X".

I want to apologize for any kind of bad feelings my own writing in that thread may have stirred up. I try not to be haughty or dismissive with this kind of writing, but I also make mistakes.

So what I'd really like to suggest is that types should not be taken as reductivist on interesting techniques like Transducers but instead as a tool for analyzing their construction and either improving it or better teaching it. Hickey himself often turns to some kind of "pseudotyping" to talk about how Transducers work---formalizing those notions should only lead to greater clarity.

Of course, implementations will differ in small ways. As I've noted abundantly here, a major difference between the Haskell and Clojure implementations is driven more by Haskell's purity than its typing. Hopefully, however, exploration of alternative implementations and the rich analysis produced by their typing can help to introduce new ideas.

For instance, the Gist implementation, if you strip the types away, is an interesting divergence in raw functionality from Clojure Transducers---if Clojure Transducers are "reduction function transformers" than the Gisted Transducers are "Moore-style (Infinite) State Machine transformers" and that difference allows the implementer to be extra explicit about the use of local state.

I'd rather see discussion about whether such InFSM transformation techniques have a place in Transducers literature than a fight over whether or not its possible or reasonable to "type transducers".