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?
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 (.).