Why transducers compose backwards

Rich Hickey’s announcement of some upcoming changes to the seq functions in clojure.core prompted a bit of discussion.

It’s probably to be expected that a few people would mistake the behaviour of (map f) for partial application. And given that map is often understood as the action of the list functor on functions, of course there would be raised eyebrows about the dedication of the new single argument arity map function to what looks like a very different and unexpected beast.

The thing that made me gulp a little was the backwards nature of transducer composition.

If you’re not paying attention when Rich demonstrates the analogy between composing transducers and the thread-last macro, you might read straight past the similarity between:

(->> aseq (map f) (filter p))

and

(sequence (comp (map f) (filter p)) aseq)

and not even twig that this is backwards from the way that composition normally works.

(comp f g) - otherwise known as f ∘ g or fg or g;f - is g then f.

So (comp (map f) (filter p)), whilst it reads pleasantly forwards as map with f then filter with p - and that is the behaviour - is actually doing whatever it is doing in the other order - whatever (filter p) does then whatever (map f) does.

If you didn’t spot this, then Rich’s elucidation of the type signature of (map f) shouldn’t allow you to remain in ignorance:

map f: (a->b)->(x->b->x)->(x->a->x)

Yes. (map f) for an f which maps as to bs returns something that goes from b-ish things to a-ish things.

It’s not very hard to see why this has to be the case. If you can’t see it yet, let me help.

Consider:

(sequence (comp (map f) (map g)) aseq)

where aseq is a sequence of as ([a] in Haskell). f takes a to b and g takes b to c.

aseq knows how to reduce itself when given a-reducing function; that is at the heart of what reducers and transducers are about. Efficiency can be gained by letting individual sequence type handle reduction themselves.

So aseq can reduce itself given a reducing function for as (r -> a -> r). So whatever it is that comp delivers to sequence or transduce must be of the type (r -> a -> r).

Only f knows anything at all about as so it must be (map f) that returns an (r -> a -> r). And for composability with other maps we know that it must accept something of the same shape.

Hence:

map f: (r -> b -> r) -> (r -> a -> r)

…and by analogy,

map g: (r -> c -> r) -> (r -> b -> r)

…so the only way these compose is (map g) then (map f). Or (map f)(map g). Or (map g);(map f). Or:

(comp (map f) (map g))

…which really means: create something that can turn a c-reducer into a b-reducer so we can feed it into something which can turn a b-reducer into an a-reducer so aseq can reduce it. These “things” when run within the context of aseqs reduction will transform each a all the way back into a c, using the logic in each of the transducers in the stack.

There might well be deep category-theoretical reasons for the backwards composition but I find it much easier to wrap my head around simply by considering it as a means of ultimately providing an a-reducer to something that can reduce as.

Comments