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
(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))
(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
g;f - is
(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)
(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.
(sequence (comp (map f) (map g)) aseq)
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.
aseq can reduce itself given a reducing function for as (r
-> a -> r). So whatever it is that
comp delivers to
transduce must be of the type (r -> a -> r).
f knows anything at all about as so it must be
(map f) that
returns an (r -> a -> r). And for composability with other
know that it must accept something of the same shape.
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 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
aseq‘s 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.