Python: Unfolding the power of fold

This content originally appeared on Level Up Coding - Medium and was authored by Klaus Cinibulk

Or: How to loop in a fancy way

We will discuss loops in a functional way. “Why do we want to do that?”, you might ask. Well, because we can. And we can do it in a very fancy and flexible manner, just by using functions and expressions instead of repeating imperative statements.

While digging deeper, we will gradually uncover one of the most controversially discussed functions ever. Guido van Rossum himself once posted: “The one I’ve always hated most…”. So, my article — 17 years later — tries to turn this statement into something like “The one I’m appreciating a lot…”.

Note: The examples presented in this article are intentionally kept as simple as possible and can easily be executed in your Python REPL.

I assume you have heard of the built-in sum() function:

>>> sum([1, 2, 3, 4, 5])
15

How could we write our own (simplified) version of sum?

def sum_(xs):
    result = 0
    for x in xs:
        result += x
    return result

>>> sum_([1, 2, 3, 4, 5])
15

Easy. What if we needed product_()?

def product_(xs):
    result = 1
    for x in xs:
        result *= x
    return result

>>> product_([1, 2, 3, 4, 5])
120

Easy. What if we wanted to write a function that creates a string by concatenating the individual string representations of list elements?

def concat_(xs):
    result = ""
    for x in xs:
        result += str(x)
    return result

>>> concat_([1, 2, 3, 4, 5])
'12345'

Easy. What if we wanted to convert a list of tuples into a dictionary?

def dictify_(xs):
    result = {}
    for k, v in xs:
        result.update({k: v})
    return result

>>> dictify_([("A", 1), ("B", 2), ("C", 3)])
{'A': 1, 'B': 2, 'C': 3}

Easy. What if…. Easy. What if … Easy…

Despite being super easy, taking a closer look at our implementations we notice, that we are producing a lot of boilerplate code over and over again. Here’s the pattern:

def some_looping_function(iterable):
    result = some_initial_value
    for item in iterable:
       result = operation(result, item)
    return result

As we have learned in the beginner’s class of programming, we should factor out the common parts into a function and pass the variable parts (an initial value, an operation and an iterable) as parameters, just to adhere to the DRY principle. Let’s do so:

def fold(initial_value, operation, iterable):
    result = initial_value
    for item in iterable:
        result = operation(result, item)
    return result

And there it is: Proudly presenting our super-power-function called fold() as the functional, generic way of writing loops.

Remark: In a pure functional world, fold() — like any other loop — would be implemented using recursion. But, as we know, Python and recursion are not best friends, so we stick to the imperative fold() implementation here. Having that said, you won’t encounter any for-statement in this article anymore :-)

The function takes 3 arguments. The initial value, an operation and an iterable. First, let’s draw our attention to the operation:

result = operation(result, item)

The operation takes exactly(!) 2 parameters and produces a result by combining them in some way, no more, no less. fold() calls this function repeatedly for every item in the iterable, always passing the computed result as the first parameter into the next iteration. By that, the result “accumulates” over time as the iteration progresses. As we need something to start with, we preset the accumulated state with the initial value.

Because of the fact that the operation returns a single value by combining the two arguments, it is also called a “reducer” function.

IMPORTANT: The reducer function never ever mutates the accumulated state in place, it always returns a new(!) version of the state!

Let’s visualize this process for our sum_() function step by step. The operation is a simple add() function:

def add(a, b):
    return a + b

>>> result1 = add(0,       1) # = 0 + 1
>>> result2 = add(result1, 2) # = 1 + 2
>>> result3 = add(result2, 3) # = 3 + 3
>>> result4 = add(result3, 4) # = 6 + 4
>>> result5 = add(result4, 5) # = 10 + 5

We end up with a number of equations. If we now substitute the results by their right hand sides, we get the following representation:

>>> result5 = add(add(add(add(add(0, 1), 2), 3), 4), 5)
>>> result5
15

Or, the other way round, when replacing add() by its corresponding “+” operator we receive this equation:

>>> result5 = (((((0 + 1) + 2) + 3) + 4) + 5)
>>> result5
15

It becomes clear now, that fold() is a left-associative operation, i.e. the final result is computed starting from the left (like Pacman eating monsters left to right…). That’s why fold() is also known as foldLeft (in Scala) or foldl (in Haskell).

And that’s the whole magic of fold(). We are now able to re-define our functions from above in terms of fold() as simple one-liners:

def sum_(xs):
    return fold(0, lambda acc, item: acc + item, xs)

def product(xs):
    return fold(1, lambda acc, item: acc * item, xs)

def concat_(xs):
    return fold("", lambda acc, item: acc + str(item), xs)

def dictify_(xs):
    return fold({}, lambda acc, item: {**acc, item[0]: item[1]}, xs)

Instead of lambdas we can use any other “callable” object, as long as its signature follows the characteristics of a reducer function:

>>> fold(0, add, [1, 2, 3, 4, 5])
15

Finally, let’s spend some thoughts on the initial element. Here, we have to answer two questions: What’s the type of the initial element and what’s the value of the initial element?

Usually, the type of the initial element is the same as the type of the first argument expected by the reducer function. Type annotations are helpful for visualizing that:

from typing import Callable, Iterable, TypeVar

A = TypeVar("A")
B = TypeVar("B")

def fold(
         initial_value: B,
         reducer: Callable[[B, A], B],
         iterable: Iterable[A]
) -> B:
    ...

The value of the initial element depends on what the reducer function is expected to return when called for the very first time. For arithmetic operations the initial element is commonly equal to the “neutral element” (or identity element) with regard to the operation of the reducer function.

For instance, the neutral element for addition is 0, because 0 + x = x. For multiplication it is 1 because 1 * x = x. For string concatenation it is the empty string (“” + “a string” = “a string”), while for list concatenation it’s the empty list ([] + [a, b, c] = [a, b, c]). You get the idea.

Sometimes we want to start off with something more complex:

def add_mapping(d, item):
   return {**d, item.upper(): ord(item.upper())}

>>> fold({"@": 64}, add_mapping, ["A", "b", "C"])
{'@': 64, 'A': 65, 'B': 66, 'C': 67}

In this — admittedly contrived — example we are presetting the initial dictionary with some values.

The next question coming up might be: Are there situations where we don’t need an explicit initial value and just take the first element of the iterable as the initial value? That’s a valid question and the answer is: Yes, that’s basically the original idea of our beloved reduce() function, which is nothing more than a special form of fold().

from typing import Callable, TypeVar, Iterable

B = TypeVar("B")

def reduce_(reducer: Callable[[B, B], B], iterable: Iterable[B]):
    it = iter(iterable)
    result = next(it)
    for item in it:
        result = reducer(result, item)
    return result

>>> reduce_(add, [1, 2, 3, 4, 5])
15

Looking at the type annotations we notice that reduce() works with a single type B. For instance, reducing an iterable of type List[int] will always result in a single int value.

So, calculating the sum (or product) perfectly works without explicitly passing the neutral element, whereas creating a string from a list of integers doesn’t work without explicit initial value:

>>> reduce_(lambda acc, item: acc + str(item), [1, 2, 3, 4, 5])
...
TypeError: unsupported operand type(s) for +: 'int' and 'str'

The reason is that in the initial invocation of the lambda, acc has type int (the initial 1 in the sequence), and we are trying to add str(2). That’s exactly what the error message is telling us.

When to specify a dedicated initial value, then? Whenever the resulting type is different than the type of the elements of the iterable, you will most likely need an initial value of the same type as the resulting value.

Note that, in Python there’s only reduce() available as a member of the standard functools package, but we don’t have fold(). Python’s reduce() takes the initial value as an optional parameter, whose default value is None. So, if you pass an initial value to reduce(), it behaves like fold().

From now on I will use Python’s native functools.reduce() in the code examples. To save space I’m importing functools as “f”.

import functools as f

>>> f.reduce(lambda acc, item: acc + item, [1, 2, 3, 4, 5])
15

>>> f.reduce(lambda acc, item: acc + str(item), [1, 2, 3, 4, 5], "")
'12345'

Personally, I prefer to always pass an initial value to reduce() as it makes the intended result type more explicit.

We can now summarize the basic properties of reduce():

• The implementation of reduce itself is super simple, as it delegates the “reduction” to another function. This makes reduce() a higher-order function.
• The reducer function computes a new state by subsequently combining accumulated state with every item of an iterable sequence.
• The return type of the reducer function is the same as the type of its first argument.
• The initial value in the standard reduce() function is optional. If omitted, the function takes the first item of the iterable as the initial value.

When to use reduce()

In general, reduce() can be considered a generic, functional way of writing loops that are meant to produce a result by iterating over a collection.

I guess, you have heard of map() and filter(). map() takes a function and an iterable, applies the function to the elements of the iterable and returns a “projected” iterable.

filter() on the contrary takes a “predicate function” (a function returning bool) and an iterable, and returns a new iterable with elements the predicate function holds for.

Now, why am I mentioning map() and filter() in combination with reduce()? Well, like reduce(), both of them take a function and an iterable as input. Sound familiar? To demonstrate the generic nature of reduce(), let me show how map() and filter() can be implemented in terms of reduce().

Here’s map() for lists:

from typing import List

A = TypeVar("A")
B = TypeVar("B")

def map_(f: Callable[[A], B], seq: List[A]) -> List[B]:
    return f.reduce(lambda state, item: state + [f(item)], seq, [])

>>> map_(lambda x: x * x, [1, 2, 3, 4, 5])
[1, 4, 9, 16, 25]

And there’s filter():

def filter_(
    predicate: Callable[[A], bool], seq: List[A]
) -> List[A]:

    return f.reduce(
        lambda state, item: 
            state + [item] if predicate(item) else state,
        seq, [])

>>> filter_(lambda x: len(x) > 2, ["abc", "de", "fghi"])
['abc', 'fghi']

Note that in both cases I’m using an empty list as initial value as we want to return a list.

And there’s even more well-known functions that can be implemented using reduce.

max():

import math

def max_(seq: Iterable[int]) -> int:
    return f.reduce(
        lambda state, item: item if item > state else state,
        seq, -math.inf)

>>> max_([10, 20, 30])
30

reversed():

def reversed_(seq: List[A]) -> List[A]:
    return f.reduce(lambda state, item: [item] + state, seq, [])

>>> reversed_([10, 20, 30])
[30, 20, 10]

Again, as we create a reversed version of the input list, we set the neutral element to empty list ([] + [n] = [n]).

accumulate():

Examples taken from https://docs.python.org/3/library/itertools.html#itertools.accumulate

import operator as op

def accumulate_(seq: List[A], f=op.add) -> List[A]:
    return f.reduce(
        lambda state, item:
            [item] if not state else state + [f(state[-1], item)],
        seq, [])

>>> accumulate_([1, 2, 3, 4, 5])
[1, 3, 6, 10, 15]

>>> accumulate_([1, 2, 3, 4, 5], op.mul)
[1, 2, 6, 24, 120]

>>> cashflows = [1000, -90, -90, -90, -90]
>>> accumulate_(cashflows, lambda bal, pmt: bal*1.05 + pmt)
[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]

Function composition:

A more involved example is function composition implemented with reduce():

from typing import Any

C = TypeVar("C")

def compose2(
    g: Callable[[B], C], f: Callable[[A], B]
) -> Callable[[A], C]:
    return lambda x: g(f(x))

def compose(*f: Callable[[Any], Any]) -> Callable[[Any], Any]:
    return f.reduce(compose2, f, lambda x: x)

>>> complexlen = compose(str, complex, len)
>>> complexlen("42")
'(2+0j)'

First, we define a function compose2(g, f) which returns a new function (g . f) “g after f”. Then, we define compose() for an arbitrary number of functions to be composed using reduce().

Here, the neutral element is the identity function lambda x: x. Composing a function with the identity function returns the original function: (f . id) = f

Other Applications of reduce()

I assume you have heard of ReduxJS which is essentially based on the principles of reduce().

The reduction step in MapReduce uses a reducer function to combine intermediate results.

And many more…

Conclusion

You see, applications of fold() and reduce() are everywhere, reduce() and fold() apparently are two of those swiss army knives when it comes to transforming elements of an iterable collection into something else in a functional way.

In my experience, the reducer function is the thing people are struggling most when getting in touch with reduce() and fold(). It definitely requires some hands-on (and CodeKata). Once you get the idea, these functions will become an indispensable tool in your functional repertoire.

Always remember, the reducer is just like any other function, which is repeatedly applied to a sequence of values. So, absolutely no need for hate or anxiety.

That’s it for this article. I hope I was able to demystify fold()/reduce() and shed some light on its applications and functionality. Feel free to leave your comments and share the article if you find it useful.

Bonus material :-)

What about nested loops?

I was asked about how nested loops could be implemented using reduce(). Here’s an attempt to attack this problem purely functional. Consider the nested loop shown below:

result = []
for pfx in range(1, 4):
    for code in range(65, 68):
        result.append(str(pfx) + ":" + chr(code))

>>> result
['1:A', '1:B', '1:C', '2:A', '2:B', '2:C', '3:A', '3:B', '3:C']

Apart from the fact, that you could achieve the same result by writing…

>>> [str(pfx) + ":" + chr(code)
    for pfx in range(1, 4)
    for code in range(65, 68)]
['1:A', '1:B', '1:C', '2:A', '2:B', '2:C', '3:A', '3:B', '3:C']

… let’s try to do use functions. We start by creating the reducer operation which just appends a single string like ‘1:A’ to a list:

def add_prefix(pfx: int, code: int) -> str:
    return str(pfx) + ":" + chr(code)

def prefix_reducer(pfx):
    return lambda result, code: result + [add_prefix(pfx, code)]

>>> f.reduce(prefix_reducer(1), range(65, 68), [])
['1:A', '1:B', '1:C']

The interesting thing here is that we have to inject the prefix variable ‘pfx’ into the reducer function, but we cannot have a reducer function which takes 3 arguments. Remember: a reducer can only take 2 of them ;-)

We make use of ‘closures’! Instead of returning a value, we return the reducer function (i.e. a lambda), which captures the variable ‘pfx’ from the surrounding scope.

With that, we can now create a function that creates sub-lists for single prefixes:

def range_prefixer(pfx, rng):
    return functools.reduce(prefix_reducer(pfx), rng, [])

>>> range_prefixer(2, range(65, 68))
['2:A', '2:B', '2:C']

Finally, we need a reducer that produces a single list from a list generated by range_prefixer() calls.

def range_reducer(rng):
    return lambda state, pfx: state + range_prefixer(pfx, rng)

>>> functools.reduce(
        range_reducer(range(65, 68)), 
        range(1, 4), 
        [])
['1:A', '1:B', '1:C', '2:A', '2:B', '2:C', '3:A', '3:B', '3:C']

At first glance, quite some effort to convert a 4-lines-nested for-loop into something functional, huh? But, we gained a lot of reusable(!) functionality in terms of pure functions, each of which are one-liners having a clear functionality, which is easy to reason about and which can be nicely tested.

def add_prefix(pfx: int, code: int) -> str:
    return str(pfx) + ":" + chr(code)

def prefix_reducer(pfx):
    return lambda result, code: result + [add_prefix(pfx, code)]

def range_prefixer(pfx, rng):
    return f.reduce(prefix_reducer(pfx), rng, [])

def range_reducer(rng):
    return lambda state, pfx: state + range_prefixer(pfx, rng)

Also note that everything is just expressions, no statements (except the return).

Here’s the final one-liner function doing the nested calculation:

def nested_prefixer(prefix_rng, code_rng):
    return f.reduce(range_reducer(code_rng), prefix_rng, [])

>>> nested_prefixer(range(1, 4), range(65, 68))
['1:A', '1:B', '1:C', '2:A', '2:B', '2:C', '3:A', '3:B', '3:C']

We could make our solution even more flexible by injecting the add_prefix() function as parameter to nested_prefixer(), so that we could parameterize the format, e.g. ‘1__A’ or ‘1xA’ or whatever. I leave this as an exercise for the reader ;-)

Python: Unfolding the power of fold was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

This content originally appeared on Level Up Coding - Medium and was authored by Klaus Cinibulk

Print Share Comment Cite Upload Translate Updates

APA

Klaus Cinibulk | Sciencx (2022-07-21T18:45:49+00:00) Python: Unfolding the power of fold. Retrieved from https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/

MLA

" » Python: Unfolding the power of fold." Klaus Cinibulk | Sciencx - Thursday July 21, 2022, https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/

HARVARD

Klaus Cinibulk | Sciencx Thursday July 21, 2022 » Python: Unfolding the power of fold., viewed ,<https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/>

VANCOUVER

Klaus Cinibulk | Sciencx - » Python: Unfolding the power of fold. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/

CHICAGO

" » Python: Unfolding the power of fold." Klaus Cinibulk | Sciencx - Accessed . https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/

IEEE

" » Python: Unfolding the power of fold." Klaus Cinibulk | Sciencx [Online]. Available: https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/. [Accessed: ]

rf:citation

» Python: Unfolding the power of fold | Klaus Cinibulk | Sciencx | https://www.scien.cx/2022/07/21/python-unfolding-the-power-of-fold/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.