How is a transducer different from a partially applied function?

Question

After reading this article on Clojure (http://blog.podsnap.com/ducers2.html) introducing transducers, I'm confused on what a transducer is. Is a partially applied map in Haskell, such as map (+1) a transducer? At first I thought this was a Clojure way of using partial application, but then the article goes on to implement it in Haskell with an explicit type. What use does it have in Haskell?

Answer 1

In Clojure (map inc) is a transducer, but not in Haskell, because Haskell has to obey currying but an untyped Lisp can break that curry-by-default convention. The type of transducers is instead:

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

We say that the transducer 'turns a into b'. Yes, the a and the b seem "backwards" on the right hand side. The forall means that a Transducer must leave r as a general type variable but is totally allowed to specialize on a and b.

Let me reverse two of the arguments in foldr:

-- cf. with foldr :: (x -> r -> r) -> r -> [x] -> r
ffoldr :: (x -> r -> r) -> [x] -> r -> r
ffoldr = flip . foldr

(we can also use foldl but it will tend to reverse things later). This means that a Transducer can be used to transform the first argument of ffoldr from x to y, so that we can instead process an [x] with a y -> r -> r using foldr. Transducers 'sit between' the inputs ([x], r) and the final processor (y, r) -> r.

I've flipped the second two arguments to emphasize also that, surprisingly, ffoldr :: Transducer [x] x. By using the symmetry of the arguments we also have a generic composition of transducers, which happens to be just function composition:

(.) :: Transducer a b -> Transducer b c -> Transducer a c

(If you think it's cool that giving these forall r terms lets us reverse how you normally use ., you can do it arbitrarily via a technique called "continuation passing".)

For example, here is the filter transducer:

tfilter :: (a -> Bool) -> (a -> r -> r) -> a -> r -> r 
    -- or: (a -> Bool) -> Transducer a a
tfilter predicate f a = if predicate a then f a else id

This applies the reduction function f to a and r only if the predicate holds. There is also a mapping transducer:

tmap :: (a -> b) -> (b -> r -> r) -> a -> r -> r 
tmap ba f a = f (ba a)

This gives composable map/filter semantics for any 'transducable' type: one map/filter fn can work for multiple contexts.

The Transducer type has a cute isomorphism: it turns out that the foldr of a list forall r. (x -> r -> r) -> r -> r is perfectly equivalent to that list [x] (it is the "Church encoding" of that list), and therefore swapping the argument a to the very front of the transducer definition gives us the (IMO much easier to understand!) type type TransL a b = a -> [b]. And this is much easier to understand:

tl_map f = \a -> [f a]
tl_filter predicate = \a -> if predicate a then [a] else []

To run these on a list, use concatMap... which happens to be just >>=! So you just write collection >>= transducer and you have the transduced collection. The meaning of TransL a b is then, "take each element of the original list of a, and give me 0 or more elements of type b to splice into my outgoing list." It filters by splicing 0 elements when the predicate doesn't work; it maps by yielding 1 output element for each input element; another operation tl_dupe = \a -> [a, a] is a transducer which duplicates the elements in a list, [1,2,3] >>= tl_dupe becomes [1,1,2,2,3,3].

Where foldr appears to be a Transducer [x] x it is now seen to be identical to id :: TransL [x] x which has a way of simply performing a concat operation in the middle of a computation; the identity function in this algebra is actually return = \a -> [a], also written (:[]). The only loss is that we can no longer use . to compose these, but in fact the same composition is provided in Control.Monad as the Kleisli composition operator >=>.

So long story short, transducers are functions a -> [b] cleverly transformed with a bit of Church encoding so that the Kleisli composition operator for these Kleisli arrows of the list monad, becomes simply (.).