Understanding Transducers through Python
In this series we take an in-depth look at transducers. Transducers - a portmanteau of "transform reducers" - are a new functional programming concept introduced into the Clojure programming language. Although transducers are actually pretty straightforward in retrospect, wrapping your brain around them, especially if you're not already a competent Clojureist, can be challenging.
In this series, we introduce transducers by implementing them from scratch in everybody's favourite executable pseudocode, Python. We'll start with the familiar staples of functional programming, map(), filter() and reduce(), and derive transducers from first principles. We'll work towards a set of general tools which works with eager collections, lazy "pull" sequences, and "push" event streams. Along the way we"ll cover stateful transducers and transducer composition, demonstrating that transducers are both more general, and more fundamental, than the functional programming tools baked into Python and many other languages.
By the end of this series, not only should transducers make sense to you, but you"ll have a recipe for implementing transducers in your own favourite programming language.
Posted on Mon 19 January 2015 by Rob Smallshire
What is a transducer?
Transducers - a portmanteau of ‘transform reducers’ - are a new
functional programming concept introduced into the Clojure programming
language. Although transducers are actually pretty straightforward in
retrospect, wrapping your brain around them, especially if you’re not
already a competent Clojureist, can be challenging. In this series …
Posted on Mon 19 January 2015 by Rob Smallshire
In the previous article in this series we
derived a Python implementation of transducers from first principles. We
finished by showing how transducers can be composed together using regular
function call application to give us a single composite reducer which can
perform many operations with a single pass of reduce …
Posted on Mon 19 January 2015 by Rob Smallshire
In the previous article
in the series we looked at improving the experience of composing
transducers together in Python, by introducing a compose()
function. We finished by showing this snippet, which composes a
filtering transducer with a mapping transducer to produce a
prime-squaring transducer. Recalling that transducers are used to …
Posted on Mon 19 January 2015 by Rob Smallshire
In the previous article in
this series on transducers we saw how we can develop the notion of the
transducer from a single function which literally transforms reducers to a
more capable protocol which supports two further capabilities: First of all, the
association of initial 'seed' values with a reduction …
Posted on Mon 19 January 2015 by Rob Smallshire
In the previous article in this series
on transducers, we showed how to implement stateful transducers, and how to deal
with any left-over state or other clean-up operations when the reduction
operation is complete. Sometimes, however, there is no need to process a whole
series of items in order to …
Posted on Mon 19 January 2015 by Rob Smallshire
In the previous article in our
series on understanding transducers through Python we showed how to support
early termination of a reduction operation. This time, we'll demonstrate how
transducers can produce more items than they consume. Although this may seem
obvious, it leads to some important consequences for implementing lazy …
Posted on Tue 20 January 2015 by Rob Smallshire
In the previous article in this
series on transducers we looked at transducers which push more items downstream
through the reducer chain than they receive from upstream. We promised that this
would make lazy evaluation of transducer chains quite interesting.
When used with our transduce() function, our mapping and filtering …
Posted on Fri 27 March 2015 by Rob Smallshire
In the previous article in this
series on transducers we looked at lazily evaluating transducers. This time
we'll look not at pulling output through a transducer chain from downstream,
but at pushing input items into the chain from upstream.
All of the uses of transducers we've demonstrated in Python so …