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 ints) 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 built-in 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 three-step 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 the initial_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 higher-order functions with reduce

Let’s see how the three-step 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 higher-order 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 question-answering 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 your iterable. answer is here
Fibonacci Sequence. Hint: use range() as your iterable. And [0,1] as you initial_value
Reversing linked-list!

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.

Introduction#

Implementing simple functions with reduce#

Implementing sum with reduce.#

Implementing a tuple to list Converter#

A 3 step approach to implement functions with reduce.#

1 Think about the return value.#

2 Think about the initial_value.#

3 Think about the reducing_function.#

Implementing other higher-order functions with reduce#

accumulate#

map#

filter#

Implementing our own version of reduce#

Thinking about the base case.#

thinking of the recursive case#

Further exercises#

Closing thoughts#