Reducers - A Library and Model for Collection Processing

The story starts best at the bottom.

Clojure and other functional languages have a function called map that takes a function and a collection/list.

The classic recursive functional definition of map is to apply f to the first thing in the collection, then cons the result onto the result of mapping f on the rest of the collection. This definition includes plenty of 'how':

Newer OO frameworks will often remove some of these problems by having map be a function of fn * Coll → Coll for any type of Coll, removing the sequentiality but also losing the laziness, and they still specify a concrete collection result.

Semantically, and minimally, map means "apply-to-all" e.g. (map inc coll) means give me a (logical) collection where every item is one greater than it was in coll. But, map doesn’t know how to navigate around every collection - the use of seqs/lists/iterators/streams etc forces a shared known representation. Nor does inc (or any function) know how to apply itself to every collection representation, else we could just say (inc coll).

The only thing that knows how to apply a function to a collection is the collection itself.

What is the generic gateway to a collection applying things to itself? In Clojure, it is (internal) reduce.

We now have a new super-generalized and minimal abstraction for collections - a collection is some set of things that, when given a function to apply to its contents, can do so and give you the result, i.e. a collection is (at minimum) reducible. In other words, you can call reduce on it.

Thus, core.reducers/map is a function of fn * reducible → reducible. (Whereas core/map is a function of fn * seqable → seqable.)

Now, how? If someone is going to ask the result of (map inc coll) to reduce itself with some function f, map must ultimately ask coll to do the job. Rather than pass coll f, map passes coll a new, transformed, reducing function that takes what coll supplies, calls inc on it, and then calls f on that.

i.e. the core work of map f looks like this:

It takes a reducing function f1, and returns a new reducing function that calls f1 after applying f to its input.

Thus you can define map as a function of fn * reducible → reducible by merely transforming the reducing function. Mapping is semantically a function of the function of one step of a reduction. This transformation is decomplected from both representation and order. We call functions such as this map, that take a reducible, and in turn return something reducible via transformation of the reducing function, reducers.

Now let’s revisit the hows above…​

It is important to note that now, when (map f coll) is called nothing happens except the creation of a recipe for a new collection, a recipe that is itself reducible. No work is done yet to the contained elements and no concrete collection is produced.

The beautiful thing is that this 'transformation of reducing function' mechanism also works for many of the traditional seq functions, like filter, take, flatten etc. Note the fact that filter is (potentially) contractive, and flatten is (potentially) expansive per step - the mechanism is general and not limited to 1:1 transformations. And other reducer definitions are as pretty as map’s - none of the imperativeness of iterators, or generators with yield.

If map doesn’t do the work of mapping, but merely creates a recipe, when does the work get done? When you reduce its result:

That should look familiar - it’s the same named functions, applied in the same order, with the same arguments, producing the same result as the Clojure’s seq-based fns. The difference is that, reduce being eager, and these reducers fns being out of the seq game, there’s no per-step allocation overhead, so it’s faster. Laziness is great when you need it, but when you don’t you shouldn’t have to pay for it.

The reducer fns are curried, and they can be easily composed:

Thus reduction 'recipes' (reducers) are first class.

What if we want a collection result? It’s good to know that into uses reduce:

Note there are no intermediate collections produced.

And, of course, you don’t always want a result of the same collection type:

Decomplecting the core operations from representation and laziness has given us some speed, but what about the elimination of order? It should open the door to parallelism, but we are stuck with the semantics of reduce being foldl, i.e. it uses an accumulator and is fundamentally serial. We can parallelize reduction by using independent sub-reductions and combining their results, and the library defines a function that does just that: fold.

The primary signature of fold takes a combining function, a reducing function, and a collection and returns the result of combining the results of reducing subsegments of the collection, potentially in parallel. Obviously if the work is to occur in parallel, the functions must be associative, but they need not be commutative - fold preserves order. Note that there is no initial 'seed' or 'accumulator' value, as there may be with reduce and foldl. But, since the subsegments are themselves reduced (with reduce), it raises the question as to what supplies the seed values for those reductions?

The combining function (an associative binary fn) must have some 'identity' value, a value that, when combined with some X, yields X. 0 is an identity value for +, as is 1 for *. The combining fn must supply an identity value when called with no arguments (as do + and *). It will be called with no arguments to supply a seed for each leaf reduction. There is a fn (called monoid, shh!) to help you build such combining functions.

If no combining fn is supplied, the reducing fn is used. Simple folds look like reduces:

But by promising less (i.e. not promising stepwise reduction from left or right) fold can do more - run in parallel. It does this when the collection is amenable to parallel subdivision. Ideal candidates are data structures built from trees. Clojure vectors and maps are trees, and have parallel implementations of fold based upon the ForkJoin framework.

What if the underlying collection is not amenable (e.g. is a sequence)? fold just devolves into reduce, producing the same semantic, if not physical, result.

There’s a tremendous amount you can accomplish with this reduce+combine strategy, especially when you consider that the map, filter etc reducers will not constitute independent layers of parallel jobs - they just transform the reducing fn working on the leaves.

You can have a look at the cat function included in the library for an interesting example of a combining fn. cat quickly gathers up the fold results, forming a binary tree with the reductions as leaves. It returns a highly abstract, yet now quite useful 'collection' that is just counted, reducible, foldable and seqable.

Oh yeah, perf. Don’t be surprised to see things become 2-3X faster, or more with more cores.

As much fun as this is, there’s still more fun to be had by those so inclined:

By adopting an alternative view of collections as reducible, rather than seqable things, we can get a complementary set of fundamental operations that tradeoff laziness for parallelism, while retaining the same high-level, functional programming model. Because the two models retain the same shape, we can easily choose whichever is appropriate for the task at hand.

See the follow up blog post for more details about what constitutes a reducer, as well as some background about the library.

Rich