Introduction
reduce
or foldleft
is a very powerful function, but it can be quite tricky to understand and use. In fact, I used to think that reduce
was an obscure function, that reduced (hehe) the readability of a program. If you ever want to make it as a functional programmer, understanding reduce
is as important as important as knowing how to reverse linked list. I’m joking, knowing how to reverse a linked list is not that important, and it can be done with reduce!
Let’s have a look at the function signature of reduce.
def reduce(reducing_function, iterable, initial_value):
reduce
takes in three arguments, a reducing function, an iterable (like lists, arrays), and an optional initial value.
The reducing function is key to understanding reduce. All reducing functions have a similar form, they take in two arguments and return the result of some computation involving the two arguments.
def reducing_function(previous_result, element):
Essentially it’s reducing two values into one value. The last point would trip me up many times. We intuitively think one value means one number, or one string, or any other atom; but it can also refer to a collection, like lists and arrays (which may contain multiple values). Let’s quickly look at two reducing functions.
def add(a, b):
return a+b
def concat(array, element):
# appends element to the end of array
return array + [element]
Both of them pretty straightforward to understand. The key thing to notice is these functions are binary functions (i.e. they only taketwo arguments), and they return one value.
Coming back to reduce
, all that reduce
does is it takes the initial_value
, and an element from the iterable
and passes it to the reducing_function
, then takes the result and passes it along with thenext element in the iterable
.
Looking at an imperative definition of reduce will make it more obvious what’s going on.
def imperative_reduce(reducing_function, iterable, initial_value):
# assumes that initial_value is not none
result = initial_value
for element in iterable:
result = reducing_function(result, element)
return result
Implementing simple functions with reduce
Fire up your text editor and copy the add
and concat
function, and then import reduce. This is what your file should look like.
# fold.py
from functools import reduce
def add(a, b):
return a+b
def concat(array, element):
return array + [element]
Implementing sum with reduce.
The sum function adds all the elements in the list and returns It’s result.
>>> sum([1,2,3])
6
Implementing this with the reduce is rather straightforward.
# fold.py
def my_sum(arr):
return reduce(add, arr, 0)
# test it in the repl
>>> my_sum([1,2,3])
6
Let’s walk through what happens here, reduce takes 0 and 1 and passes it to add, Then takes that result (1+0=1) along with the next item in the array (2) and passes it to add, then it takes the result along with the next element i.e 3 and passes it to add again, finally says elements in the array are exhausted it returns the result.
In fact, since the type of the return value is the same as that of the element in an array (both are int
s) we can omit the initial value. Note that this won’t always be the case but this is a good rule of thumb. When you don’t provide an initial_value,
reduce
passes thefirst two elements of the iterable to the reducing function.
# fold.py
def my_sum(arr):
return reduce(add, arr)
If you’re interested in seeing a visual demonstration of my_sum
, see my tweet Visualizing folds
Implementing a tuple to list Converter
This is a bit of a contrived example because we have builtin list constructors but let’s pretend we don’t. Whenever I’m trying to use reduce, I like to think about the final result. Specifically, the type of the final result, because the type of the final result determines the type of the initial_value
. In this case, the final result is of type list. So initial_value
is going to also be a list (an empty list). We can use concat
as our reducing function.
def tuple_to_list(tup):
return reduce(concat, tup, [])
>>> tuple_to_list((1,2,3))
[1, 2, 3]
tuple_to_list
might seem like a useless function but it helps illustrate an important point that reduce can be used to construct lists. For a beginner this is one of the most counterintuitive uses of reduce
. It took me a long time to get used to it so don’t worry if it doesn’t click immediately.
A 3 step approach to implement functions with reduce.
I have a threestep process when I’m implementing something using reduce
. Don’t worry if you don’t understand the entire thing, it will make sense when we start implementing the functions. If you like, just read the steps in brief and skip ahead to the next section, and you can refer back later on.
 Think about the return value.
 Think about the
initial_value.
 Think about the
reducing_function.
1 Think about the return value.
 What’s the type of my return value? is it a list, linked list, or an atom( number, string, boolean, etc)?
 If my item is a list, is it a constant sized list or does its size depend on the size of
iterable
2 Think about the initial_value
.
 The type of my
initial_value
depends on the type of my return value.  If the type of your return value is the same as that of an element in the
iterable
then you can omit theinitial_value
.  Generally, initial values tend to be empty lists, but this doesn’t have to be the case.
3 Think about the reducing_function
.
 How am I going to use the result of the previous computation and the current element, to get what I want?
 How do I return the result of the new computation? Do I add it to a list containing previous computations, or do I just return the result as is?
Implementing other higherorder functions with reduce
Let’s see how the threestep approach works in practice. Hopefully, by the end of this section, you will have a better understanding of how reduce
works and you’ll be able to appreciate its power.
accumulate
accumulate
is a higherorder function that takes in another function and an iterable and returns a list of all the intermediate values of the computation. Here’s an example to make it clear.
>>> from itertools import accumulate
>>> list(accumulate([1,2,3,4], add))
[1, 3, 6, 10]
# [ 1, # Insert the first element
# 3, # add(1, 2)
# 6, # add(3, 3)
# 10 # add(6, 4)
# ]
As you can see the intermediate values of the computation are stored. This combines with the concepts we learned when implemented sum
and tuple_to_list.
We are reusing the value of a previous computation and constructing a list. Let’s try implementing this.
Step one: think about the type of the return value  it’s a list
step Two: think about what the initial_value
 The return value is a list, so most likely the initial value must be an empty list
Step three. Think about the reducing_function
this is the most difficult part. We need to accomplish three things in this function 
 get the last value in the list and pass it on to the function passed to accumulate
 append the result of calling the accumulating_function to the list.
 return the list.
Let’s see what this looks like.
def my_accumulate(accumulating_function, iterable):
# inner function because we need access to
# accumulating_function
def reducing_function(accumulating_list, element):
if not accumulating_list:# if empty list
accumulating_list.append( element )
else:
previous_result = accumulating_list[1] # get the last element
current_result = accumulating_function(previous_result, element)
accumulating_list.append(current_result)
return accumulating_list
return reduce(reducing_function, iterable, [])
map
the map function, takes in another function and iterates through a collection and applies that function to each element, and collects the results in another collection.
Just a quick example to see how this works.
>>> list(map(lambda x: x+1, [1,2,3,4,5]))
[2, 3, 4, 5, 6]
Stop and try to think about how you would implement this.
Let’s try implementing this.
Step 1: think about the type of the return value  it’s a list
step 2: think about what the initial_value
 The return value is a list most likely the initial value must be an empty list
Step 3. Think about the reducing_function
 Pass the element to the function that was passed to map,
 Append its result to list that’s accumulating the values.
If you haven’t already implemented the function try it now.
def my_map(fn, iterable):
def reducing_fn(accumulator, element):
return accumulator + [fn(element)]
return reduce(reducing_fn, iterable, [])
>>> my_map(lambda x: x+1, [1,2,3,4,5])
[2, 3, 4, 5, 6]
filter
the filter function a predicate and an iterable and filters out all elements that don’t satisfy the predicate. A predicate is a questionanswering function. For example
def is_even(num):
return num % 2 == 0
this tells you whether the number is even or not. Predicates always return a Boolean value.
Let’s quickly see how the filter function works
>>> list(filter(is_even, [1,2,3,4,5,6]))
[2, 4, 6]
Try implementing filter
on your own.
Step 1: think about the type of the return value  it’s a list
step 2: think about what the initial_value
 The return value is a list most likely the initial value must be an empty list
Step three. Think about the reducing_function

 we need to test whether the element satisfies the predicate
 if it does then append to the accumulating list, if it doesn’t, return the accumulating list as it is.
def my_filter(predicate, iterable):
def reducing_fn(accumulator, element):
if predicate(element):
# if element satisfies predicate
# add to the Accumulating list
return accumulator +[element]
else:
return accumulator
return reduce(reducing_fn, iterable, [])
>>> my_filter(is_even, [1,2,3,4,5,6])
[2, 4, 6]
Implementing our own version of reduce
Reduce is essentially a recursive function. (Though it might not be implemented this way). But let’s implement it in a recursive fashion.
Thinking about the base case.
Sometimes it helps to think of the base case as the stop condition, in this case, you want to stop recursing when you reach the end of the list, i.e. iterable is empty. And since we need to return something, it would be the initial_value
So let’s add that in.
def my_reduce(reducing_function, iterable, initial_value):
# let's assume that iterable is a python list.
# let's assume that inital_value is not None.
if not iterable:
return initial_value
thinking of the recursive case
we compute the result of calling the reducing_function
with the initial_value
and the first element of the iterable.
The result becomes the initial_value
for the next recursive case along with the remaining items of the iterable (i.e the iterable without the first item).
Let’s add that.
def my_reduce(reducing_function, iterable, initial_value):
# let's assume that iterable is a python list.
# let's assume that inital_value is not None.
if not iterable:
return initial_value
else:
new_inital_value = reducing_function(initial_value,
iterable[0] # pass the first element of iterable
)
return my_reduce(reducing_function, # pass the reducing function
iterable[1:], # pass the list without the first item
new_inital_value
)
# It can be written more succinctly like this
def my_reduce(reducing_function, iterable, initial_value):
if not iterable:
return initial_value
else:
return my_reduce(reducing_function,
iterable[1:],
reducing_function(initial_value, iterable[0])
)
Further exercises
Try implementing these with reduce
 Factorial. Hint: use
range()
as youriterable.
answer is here  Fibonacci Sequence. Hint: use
range()
as youriterable.
And[0,1]
as youinitial_value
 Reversing linkedlist!
Closing thoughts
The reason reduce
is so powerful is that it abstracts away common patterns of computation like iterating through a collection and reusing previous values to compute the next value. It also hides away recursion. Almost any process that involves iterating through a collection of values can be done with reduce
.
But just because something can be done with reduce
doesn’t mean you should do it. Sometimes there are more idiomatic or expressive alternatives to your solution. For example, while it is perfectly valid to use reduce
to filter out elements based on certain conditions, it doesn’t become immediately obvious what you’re trying to do, instead if you used filter
, you’re making your intent obvious.
The best way to get comfortable with folds is by taking short imperative functions, or recursive functions, and rewriting them using reduce.