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