Any dynamic language should do, kind of :)

For example, the following code needs Higher Ranked Types to typecheck:

    id :: forall t. t -> t
    id x = x

    -- mk_pair's type is a rank-2 type, because its
    -- f parameter is a polymorphic function that gets applied
    -- to different types inside mk_pair.
    mk_pair :: (forall t. t -> t) -> (Int, String)
    mk_pair f = (f 10, f "str")

    a_pair :: (Int, String)
    a_pair = mk_pair id

But it can obviously be written in an untyped language if you wanted to. Just erase all those type annotations:

    function id(x){ return x}

    function mk_pair(f){ return [f(10), f("hello")] }

    var a_pair = mk_pair(id);

The deal with higher-ranked types is basically a tradeoff between the flexibility of the type system and the power of type inference. If you restrict yourself to rank-1 types (that is, none of your function arguments are polymorphic) then the compiler can infer all all types in the program without you having to write any type signatures. If you want to use higher ranked types then the compiler can't infer everything anymore so you might need to add some type annotations yourself.

The "kind of" being really pertinent. In particular, this forgoes the guarantee that the only thing the transducer is allowed to do is return a value from the reduction. Hickey notes that this is a law of writing a proper transducer. Higher rank types ensure that this law is properly encoded directly into the system.

That said, I'm pretty sure you know this :)

To code typed transducers we only need "for all" generics.

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

This may seems unusual or complex but is available in mainstream languages. In java:

   interface Transducer<A,B> {
      <R> Reducer<B,R> transduce(Reducer<A,R> reducer);
   }

See https://gist.github.com/didier-wenzek/07faa3990ff03fdea372 for a more complete java implementation of transducers.

You can encode them in Scala: http://apocalisp.wordpress.com/2010/07/02/higher-rank-polymo...

I'm not sure offhand. Even if your language lacks it, however, you can usually get away without it. The following works

    Transducer r a b = (r -> b -> r) -> (r -> a -> r)

but if you even accidentally specialize the `r` while constructing Transducers then you will have reduced their ability to generalize over input and output containers. In other words, it'll be up to you to maintain the universality of `r`.

You can easily do this even in a language like C#, it's just that the syntactic overhead can be a bit much:

    interface Transducer<A,B> {
        Func<R,B,R> Apply<R>(Func<R,A,R> f);
    }

That's awesome! I wasn't aware C# had them.

I took this as a challenge. I wasn't entirely confident with my understanding, so I created a fully realized version in C# available here: https://github.com/bmurphy1976/transducers-dotnet

Yes, higher rank types are no problem for C# or Java generics. It's higher-kinder types that are unavailable.