Transducers (reducing function transformers) are apparently coming to Clojure in v1.7 - but what is a transducer? Are they some sort of a continuum transfunctioner? Some say they are perverse lenses, others that they are monoidals. I have no idea, but I want to find out! So let's figure out what's changed and play with them for a bit.
Here's the work in progress commit that added them to clojure.core. A few signatures were changed, and a few functions were added. In particular, it seems like most of the higher order functions that works on top of the sequence abstractions were altered - map, filter, reduce + friends. So, what's the new signature of map?
clojure.core/map
([f] [f coll] [f c1 c2] [f c1 c2 c3] [f c1 c2 c3 & colls])
Added in 1.0
Returns a lazy sequence consisting of the result of applying f to
the set of first items of each coll, followed by applying f to the
set of second items in each coll, until any one of the colls is
exhausted. Any remaining items in other colls are ignored. Function
f should accept number-of-colls arguments. Returns a transducer when
no collection is provided.
Okay! The first signature here is new. If you apply map to a function - and NO collection, it will return a transducer.
(def increment (map inc))
What do we actually have now? Is this simply partial function application (partial map inc) or currying or something like that? Let's naively give it a collection and see what happens.
(increment [1 2 3 4 5]) ;; Don't use them like this..
#<core$map$fn__4338$fn__4339 clojure.core$map$fn__4338$fn__4339@2e2f4944>
Hmm, no, this is defiantly not partial application of map, we get a function in return here, so I'm pretty sure this is not how they should be used. Let's look at how you are supposed to use them.
;; We can get a sequence of something via a transducer function.
(sequence increment [1 2 3 4 5])
;; => (2 3 4 5 6)
;; We can transduce into a collection:
(into [] increment [1 2 3 4 5])
;; => [2 3 4 5 6]
;; We can transform and reduce a collection:
(transduce increment + [1 2 3 4 5])
;; => 20
But.. I can already do all of these steps using the existing sequence abstractions.. Example:
(reduce + (map inc [1 2 3 4 5]))
;; => 20
Transducers got one nice trick up their sleeve, they have a really nice composability.
;; Transducer functions:
(def add-2 (map (partial + 2)))
(def keep-odd (filter odd?))
(def square (map #(* % %)))
;; Composing multiple transducers
(def add-2-keep-odd-squared (comp add-2
keep-odd
square))
(sequence add-2-keep-odd-squared (range 1 100))
;; => (9 25 49 81 121 169 225 289 361 441 529 625 729 841 961 1089 ....
But.. similar stuff can already be done using existing functionality..
(->> (range 1 100)
(map (partial + 2))
(filter odd?)
(map #(* % %)))
;; => (9 25 49 81 121 169 225 289 361 441 529 625 729 841 961 1089 ....
So, what's the point here really? I'm going to assume that there is a really good point, since the people creating this stuff are way smarter than me.. So let's dig deeper. Why couldn't we use the transducers directly earlier? Let's have a look at the signatures of these functions:
map f: (a->b)->(x->b->x)->(x->a->x)
filter pred: (a->bool)->(x->a->x)->(x->a->x)
flatmap f: (a->[b])->(x->b->x)->(x->a->x)
Aha, that's a bit clearer. Filter might be the easiest to look at, it takes a predicate and returns a
transducer function. The transducer itself has signature (x->b->x)->(x->a->x) where a = b for filter. It takes another function that
takes something and an item type b, and returns something. The result of this again is another function that takes
something and item a.. and output something. However, I still find this a bit confusing.
It might be easier if we have a look at what x might be here: collections, sequences, and so on. So, for a vector, I need to give a transducer a function that operates on a vector and on an item, and outputs a vector. Let's try to do that!
;; let's call the x->b->x part "builder"..
;; and the x->a->x "applier".. for a lack of better names.
;; Filtering transducer, remove even numbers:
(def keep-odd (filter odd?))
;; A simple vector builder, takes x and b, returns x.
(defn builder [v b]
(vec (conj v b)))
;; Now, let's give the builder to the transducer..
(def applier (keep-odd builder))
We now have access to the inner function with signature x->a->x, let's try to use it to filter a list of numbers,
manually. It takes a something, and an item. We don't have this something yet, so let's give it nil, and let's give it
the first number from our list as b.
;; Vector of numbers: [1 2 3 4 5]
(applier nil 1)
;; => [1]
(applier [1] 2)
;; => [1]
(applier [1] 3)
;; => [1 3]
(applier [1 3] 4)
;; => [1 3]
(applier [1 3] 5)
;; => [1 3 5]
Do you see what's going on? We are driving the vector collection logic here (deconstruction and construction). The transducer itself has zero knowledge about the collection it's working on!
Why is this a good thing?
In clojure there are a couple of different abstractions over collections of data. We have the sequence abstraction, allowing us to work on lazy sequences of data using operations like map, filter, reduce, take, etc - all chilled out working lazily hammock-style. Then we have reducers, a highly efficient (potentially concurrent/parallel) way of operating on collections through r/map, r/fold, r/filter, r/flatten, r/reduce, etc. We also have core.async, which work by shuffling data through channels (CSP-style), core.async has functions like map<, map>, filter<, filter>.
Do you see a pattern? Yes? Cool! Let's play with core.async a bit. The latest development-version of core.async that is.
Let's look up the documentation for chan
clojure.core.async/chan
([] [buf-or-n] [buf-or-n xform] [buf-or-n xform ex-handler])
Creates a channel with an optional buffer, an optional transducer
(like (map f), (filter p) etc or a composition thereof), and an
optional exception-handler. If buf-or-n is a number, will create
and use a fixed buffer of that size. If a transducer is supplied a
buffer must be specified. ex-handler must be a fn of one argument -
if an exception occurs during transformation it will be called with
the Throwable as an argument, and any non-nil return value will be
placed in the channel.
Hey! there's an optional transducer here now.
(require '[clojure.core.async :as async :refer [chan onto-chan <!!]])
;; Create a channel, buffer size 10, with a transducer added
(def c (chan 10 add-2-keep-odd-square))
;; Dump all the numbers from 1 to 100 into the channel (this runs in a go-block)
(onto-chan c (range 1 100))
;; Pull all the transformed numbers out of the channel, into a vector.
(<!! (async/into [] c))
;; => [9 25 49 81 121 169 225 289 361 441 529 625 729 841 961 1089 .... ]
Before transducers we would have had to express the add-2-keep-odd-square logic using core async's higher order functions, but now we can instead reuse the transducer we've already created. Here the transducer is used to map and filter over something that isn't even a collection/sequence. The transducer has no idea that it's handling data on a core.async channel, we didn't have to change the map/filter/etc logic in any way to make it work on channels instead of sequences.
This means that all the code for higher order convenience functions in core.async (map<>, mapcat<>, filter<>, etc) now basically is deprecated - and it has now been labeled as such in the documentation. Boom!
Conclusion
Transducers makes it so that that the logic you express using filter, map, reduce, take, random-sample, partition-by, etc, etc, etc, can be re-used in completely different contexts. The logic is all isolated, transducers are oblivious to the underlying collection, stream, observable, iterateable, whatever context. That's an useful abstraction if you ask me :)
For an example of how to make a transducer, head over to: Boiling Sous-Vide Eggs using Clojure's Transducers.
5 comments
Thank you, it's the first clear explanation of transducers I've read. Article shared on Twitter.
I thought I read somewhere that a transducer that is a composition of functions like map, filter & co differs from a normal composition, in such a way that in a normal composition if a sequence is passed it will be iterated many times, whereas with a transducer it will be iterated only once. Is it true ?
Thank you :)
Yeah, like reducers they do not need to create intermediate sequences - so in many cases they'll be faster than old core map/reduce/filter when composed.
First of all, I really appreciated your post! It was well-written and easy to understand. And I share your opinion - I can already do all of these steps using the existing sequence abstractions.
To be quite honest, I'm not sure how transducers are much of a game-changer for me.
I was really excited for them, because when I discovered reducers, they really changed the way I coded. In fact, given that reducers are usually faster than lazy core collections functions, especially on large collections, I refactored my code base to use almost exclusively the reducers functions when operating on collections (plus a few others I've gleaned from various sources such as a reducers version of |range|, which is significantly faster than its lazy counterpart), unless I explicitly want laziness.
There are three reasons that stand between me and using transducers:
1) Given cursory benchmarks using Criterium, the difference in performance between reducers and transducers seems to be negligible. (Correct me if I'm wrong.) This is even taking into account the |volatile|s used instead of |atom|s.
2) It seems to be the case that transducers are, by definition, for single-threaded use only. Even for this reason alone I would never use them, because parallelization is a must-have for me; it's sped up my code by a factor of at least 2, and oftentimes around 5 (it depends on the number of cores I'm using, the size of the collections operated on, and a number of other factors). In my understanding, that was essentially the reason that the reducers library was created; transducers would undo that change.
3) I appreciate the fact that function composition seems to be central to the transducers paradigm and I do see the elegance in it, but that's because I already use it everywhere. I just want to know - what is the difference between:
(def xform1 (fn->> (r/map inc) (r/filter even?)))
(def result1 (->> [1 2 3 4 5] xform1 (into []))
(Here (fn->> ...) is equivalent to #(->> % ...))
and
(def xform2 (comp (map inc) (filter even?))
(def result2 (into [] xform2 [1 2 3 4 5]))
?
I know that transducers can be used lazily via the sequence function, which is quite useful and which the reducers library doesn't include (although Christophe Grand posted a function to output a lazy sequence from a reducer, which I occasionally use), and they integrate core.async's collection functions into an overall unified core collections abstraction. By comparison, the reducers library isn't integrated all that well into the core library. But then again, I rarely use the core functions anymore anyway unless I want laziness.
In short, I wish transducers, reducers, and the core collections functions were unified under one abstraction to be able to choose among processing the collection lazily (via |sequence|, etc.), outputting all elements into a specific type of collection (|vector|, |hash-map|, etc.), and/or processing a collection in parallel by being able to use an equivalent of |reducers/fold|.
Thank you,
I think that if you're heavily invested in reducers for a project for performance reasons then there's not much reason to rewrite it to use transducers. If your specific problem is able to exploit the out-of-order processing of r/fold, then reducers probably are faster anyway.
Transducers were definitely inspired by reducers, they share many of the same ideas. They both compose really well (slightly different syntax, but end result is about the same) and work efficiently while composed, minimal use of unnecessary intermediate data-structures for each step, etc.
One really nice thing transducers bring to the table is how well the fit into clojure.core compared to reducers. Most stuff in core that used to work on seqs now support transducers directly. core.async supports transducers directly. And I'm betting that third party libraries also will start supporting transducers directly. Either by returning transducers you can compose with your own transducers, or by accepting a transducers (as core.async does). Reducers feel more out of place. Transducers feel as home in core as the Seq stuff, and have comparable performance as reducers (with the exception of folding).
So what I think we'll see is that people will use transducers for most stuff, but because they're single threaded by nature, people will break out reducers for the magical properties of r/fold if they have a foldable problem with large amounts of data.
It's also possible to r/fold using transducers (bit ugly):
1. Yeah, I think performance will for the most part be comparable. If you can exploit r/fold then reducers can be faster.
2. Again I think it will depend on your problem domain and application. In some applications it's a good fit to do concurrency through core.async.. then transducers definitely is the way to go. But if you're after raw parallel power, then reducers is the go to bag of tools. Some programs need concurrency by nature, others need parallelism.
3. In practice these are really quite similar. The method of composition is different, but the end result is about the same. into is a reduction, and both of these offer a way to reduce the data, but through different protocols/abstractions.
There's a good discussion on how the reduction differs here: https://gist.github.com/run...
--
I also hope that reducers and transducers will be brought closer together in the future, it's still very early - especially for transducers - not even released yet. I bet we will see gradual change over the next couple of clojure releases affecting both reducers and transducers.
v/ nice.
You have a minor typo. look for "squared"