Transducers II: Filter and map transducers
In the Transducers I: Introduction to map, filter, and reduce blog, we introduced the map, filter, and reduce functions, and observed why there’s no simple way of chaining filter and map operations without producing intermediate lists. We saw this example:
from functools import reducedef compose(*functions):return lambda x: reduce(lambda val, func: func(val),functions,x)numbers = [1, 3, 4, 7, 8, 11, 12, 15]# compose the functions provided to the filter# and map functionscomposed = compose(lambda x: x % 2 == 0, lambda x: x**2)# compute the final result in one goresult_map = map(composed, numbers)result_filter = filter(composed, numbers)print(list(result_map))print(list(result_filter))
We saw that the reason why this doesn’t work is that the functions provided to the map and the filter functions are of different types: the former is a transformation function whereas the latter is a criterion function.
What are transducers?#
This is where transducers come to the rescue. Let’s start with the definition:
Transducers are functions that take a reducer function as input and return another reducer function.
Recall that a reducer is any function that takes two parameters and reduces them to a single value.
Having a reducer as both the input and output makes transducers composable. This is how we'll use them.
But first we need to figure out how we can translate the filter and map functions we saw earlier into transducers.
The map transducer#
We’ll start with the map transducer. Recall that this is how we implemented the map function using the reduce function:
from functools import reduce# define the map function using the reduce functiondef my_map(func, l):return reduce(lambda x, y: x + [func(y)],l,[])numbers = [1, 3, 4, 7, 8, 11, 12, 15]# compute squares of all numberssquares = my_map(lambda x: x**2, numbers)print(list(squares))
The mapping function#
Let’s define a mapping function, that takes a transformation function func as input (like the ones used to call the map function) and returns a map transducer, as follows:
from functools import reduce# the mapping function takes a transformation function# as input, and returns a map transducerdef mapping(func):return (lambda input_reducer:(lambda a, x:input_reducer(a, func(x))))numbers = [1, 3, 4, 7, 8, 11, 12, 15]# obtain the map transducermap_transducer = mapping(lambda x: x**2)# define the append function so that we can# use it as our input reducerdef append(l, x):l.append(x)return l# we provide the append function as the input reducer# indicating that the final result is supposed to be a listoutput_reducer = map_transducer(append)# we can now use this returned value with the reduce# function to implement the map function as explained earliersquares = reduce(output_reducer, numbers, [])print(list(squares))
There’s a lot going on here. Let’s unravel it.
First of all, verify that the function being returned by the mapping function on lines 6–8 is actually a transducer function. Note the signature, it takes a reducer named input_reducer as input, and returns another reducer as output:
(lambda a, x:input_reducer(a, func(x))
As this function takes two inputs and produces one output, it’s a reducer.
Note: We’ll see later what the significance of
input_reducer(a, func(x))is.
The function returned by mapping takes a reducer as an input and returns a reducer, so it is a transducer by definition.
But how do we use it?
Given a transformation function, we call the mapping function on it, and we get a transducer (map_transducer) as the result. We can then use the map_transducer to obtain the output_reducer function that we’ll use with the reduce function to implement the map function, as shown earlier.
But in order to make use of map_transducer, we need to supply an input reducer function input_reducer to it. What should this function be?
Recall that in our implementation of the my_map function using reduce earlier, we were appending the newly computed results to the accumulator to produce the final output (using the + operator):
lambda x, y: x + [func(y)]
We can observe that this appending step is actually a reducing operation, where we are taking two values—the accumulator a and the newly computed value func(x)—and producing the output list by the append operation. So the append function defined in lines 17–19 can be passed as the input input_reducer to the map_transducer function, and we do so on line 23 of the code to obtain the output_reducer function.
The effect of this reducer is that we would get append(a, func(x)) on line 8, which is equivalent to the reducer we passed in the implementation of the my_map function earlier.
One benefit of this abstraction#
This abstraction is born out of necessity, as we needed to provide some reducer as input to our map transducer, but it offers us an additional flexibility in manipulating the final result. For instance, we can add up the computed values func(x)—instead of appending them—with just one small change. We can provide an add function instead of the append function as our input reducer and adjust the initial value, from [] to 0 on line 26.
from functools import reduce# mapping function takes a transformation function# as input, and returns a map transducerdef mapping(func):return (lambda input_reducer:(lambda a, x:input_reducer(a, func(x))))numbers = [1, 3, 4, 7, 8, 11, 12, 15]# obtain the map transducermap_transducer = mapping(lambda x: x**2)# define the add function so that we can# use it as our input reducerdef add(a, x):return a + x# we provide the add function as the input reducer# indicating that the final result is supposed to be a numberoutput_reducer = map_transducer(add)# we can now use this returned value with the reduce# function to implement the map function as explained earliersum_squares = reduce(output_reducer, numbers, 0)print(sum_squares)
How nifty is that!
The filter transducer#
We can define the filter transducer more or less similarly, as shown below:
from functools import reduce# filtering function takes a criterion function# as input, and returns a filter transducerdef filtering(func):return (lambda input_reducer:(lambda a, x:input_reducer(a, x) if func(x) else a))numbers = [1, 3, 4, 7, 8, 11, 12, 15]# obtain the filter transducerfilter_transducer = filtering(lambda x: x % 2 == 0)# define the append function so that we can# use it as our input reducerdef append(l, x):l.append(x)return l# we provide the append function as the input reducer# indicating that the final result is supposed to be a listoutput_reducer = filter_transducer(append)# we can now use this returned value with the reduce# function to implement the filter function as explained earlierevens = reduce(output_reducer, numbers, [])print(list(evens))
Note that the only essential difference is in line 8, where we apply the input_reducer to reduce conditionally.
Defining a transduce function#
Let’s now define a transduce function that makes it easy to deal with transducers. It would work like the reduce function.
from functools import reduce# mapping function takes a transformation function# as input, and returns a map transducerdef mapping(func):return (lambda input_reducer:(lambda a, x:input_reducer(a, func(x))))# define the transduce function that takes# as input a transducer function, a reducer,# the input list to be processed,# and an initial valuedef transduce(transducer, reducer, input_list, initial=None):return reduce(transducer(reducer), input_list, initial)# define the append function so that we can# use it as our input reducerdef append(l, x):l.append(x)return l# the input listnumbers = [1, 3, 4, 7, 8, 11, 12, 15]# we can now use the transduce functionsquares = transduce(mapping(lambda x: x**2), # the transducerappend, # the initial reducernumbers, # the input list[]) # the initial valueprint(list(squares))
It starts by using the provided reducer function with the transducer function to obtain a reducer function that we can use with the reduce function.
Composing transducers#
We now get to our main objective, that is, chaining transducers. Let's see how our simple example can be solved using transducers. In the following code widget, we’re defining the compose function in the transducer.py file, where we’ve moved some of the core functions.
from transducer import compose, filtering, mapping, transduce, appendnumbers = [1, 3, 4, 7, 8, 11, 12, 15]# compose the filter and map transducers# note that composed_transducer itself is a transducercomposed_transducer = compose(filtering(lambda x: x % 2 == 0),mapping(lambda x: x**2))# we can now use the transduce functionsquare_of_evens = transduce(composed_transducer, # the transducerappend, # the initial reducernumbers, # the input list[]) # the initial valueprint(list(square_of_evens))
Note that when defining the compose function in the transducer.py file, we are reversing the functions input parameters list on line 6, something that we didn’t do in our original implementation of the compose function. Can you explain why that is?
Composing more than two transducers#
We can, of course, use this machinery to compose any number of transducers:
from transducer import compose, filtering, mapping, transduce, appendnumbers = [1, 3, 4, 7, 8, 11, 12, 15]# compose a few transducerscomposed_transducer = compose(filtering(lambda x: x % 2 == 0), # filter evensmapping(lambda x: x**2), # then compute squaresfiltering(lambda x: x > 50), # then filter > 50 numbersmapping(lambda x: x + 1)) # then add 1# we can now use the transduce functionresult = transduce(composed_transducer, # the transducerappend, # the initial reducernumbers, # the input list[]) # the initial valueprint(list(result))
Note: When executing this code, no intermediate lists are generated and each number is processed only once! This makes transducers of particular importance in processing streaming data.
If you want to learn more about how we can simplify programming using functions, these ideas are explored in a more systematic way in the functional programming paradigm. Consider taking the following courses on Educative:
Learn Functional Programming in Python
The functional programming paradigm can be a powerful tool, especially as it can be integrated seamlessly with procedural and object-oriented code in Python. In this course, you’ll learn what functional programming is, how it’s used, and the features of Python that support it. To start, you’ll learn how functions act as objects, the role of mutability, and how to perform recursion. In the latter half of the course, you’ll focus on closures, iterables & iterators, generators, and more. Throughout the course will be three exams which will test your understanding and really drive home what you’ve learned. By the end, you’ll have a new programming paradigm to add under your belt and have the confidence to start using functional programming in your own projects.
Learn Functional Programming with Elixir
Elixir is a functional programming language that runs in the Erlang VM, a powerful environment to run distributed systems. This course uses Elixir because of its fun syntax, vibrant community, and production-ready tooling. Elixir syntax lets you focus on what’s important while learning functional programming. Starting from scratch, you will learn the fundamentals of Elixir including expressions, modules, conditional statements, and recursion. Towards the end of the course, you will focus on more advanced material like higher-order functions, how to handle impure functions, and lastly how to design an application using Elixir and functional programming principles. By the end, you will be able to write basic Elixir programs that follow the functional programming paradigm.
Learn Functional Programming in Haskell
Functional programming is a problem-solving paradigm that differs drastically from the imperative programming style of languages like C++ or Java. While functional programming principles have invaded most modern programming languages to some degree, there is no language that embraces this paradigm quite as Haskell does. As a result, Haskell code can reach a level of expressiveness, safety, and elegance that is difficult to achieve in other programming languages. This course will introduce you to the core concepts of functional programming in Haskell. You will learn how to write pure functions using techniques such as pattern matching and recursion, and how to work with Haskell's powerful List data type. You will understand the basics of Haskell's powerful type system and define your own data types. Finally, you’ll learn how to perform IO operations the Haskell way. By the end of this course, you’ll have a new paradigm to add under your belt and you can start using functional programming in your own projects.
Free Resources
