Fold Left and Right in Python
Last updated
Last updated
exposes a number of enriched with a plethora of modules composing . It is a pragmatic language that does not confine the developer in a specific programming paradigm. A Python developer can write imperative, procedural, object oriented or functional code. In Python, common functional constructs are available as (e.g. map
, filter
, all
, any
, sum
...). Additional higher-order functions are regrouped in the module (e.g. reduce
, partial
...). Prior to crafting some Python code, let's take a detour in some potentially more arcane areas of functional programming, in particular surrounding the fold
concepts.
Despite being primary a Python article, some of the initial code examples are in . Haskell is the perfect cradle for concepts like Folding. In addition, Haskell code, like Python code, reads like pseudo-code.
regroups a family of pertaining to the functional programming domain. At a high level, folding allows to deconstruct or reduce data. A typical signature for a generic fold function is the following: fold f z xsfold f z xs
Where:
f
is a higher-order function taking two arguments, an accumulator and an element of the list xs
. It is applied recursively to each element of xs
.
z
is the initial value of the accumulator and an argument of the function f
.
xs
is a collection.
Fold functions come in different kinds, the two main linear ones are foldl
and foldr
.
foldl
, for "fold left", is left associative. Think of foldl as "fold from the left" (image courtesy of Wikipedia):
Let ⊗
be a variable bound to the function of two arguments f
in the diagram above. The foldl
function can be defined as follows:
foldl (⊗) z [1,2,3,4,5]=((((z ⊗ 1) ⊗ 2) ⊗ 3) ⊗ 4) ⊗ 5foldl (⊗) z [1,2,3,4,5]=((((z ⊗ 1) ⊗ 2) ⊗ 3) ⊗ 4) ⊗ 5
To cement the concept, here is an example in Haskell with the subtraction operator:
foldr
, for "fold right", is right associative. Think of foldr
as "fold from the right" (image courtesy of Wikipedia):
As for foldl
in the previous section, let ⊗
be a variable bound to the function of two arguments f
. The foldr
operator can be defined as:
foldr (⊗) z [1,2,3,4,5]=1 ⊗ (2 ⊗ (3 ⊗ (4 ⊗ (5 ⊗ z))))foldr (⊗) z [1,2,3,4,5]=1 ⊗ (2 ⊗ (3 ⊗ (4 ⊗ (5 ⊗ z))))
Following is an example with the division operator:
For all finite lists xs
, foldr f e xs = foldl (flip f) e (reverse xs)foldr f e xs = foldl (flip f) e (reverse xs)
where, flip f x y=f y xflip f x y=f y x
Note: The snippets of code used as examples in this article target Python 3.
Or more formally as a function:
Relying on the third duality theorem evoked in the Laws of fold section above, foldr
can be crafted as a lambda:
Lambdas implemented as above are not generally conducive of good code readibilty. The following code, although longer, may be arguably more maintainable:
We now have new toy functions in Python, foldl
and foldr
, what can we do with those?
The folding concept opens the doors to build many other functions. It allows to be done without having recourse to writing explicit recursive code or managing loops. For example, max
, min
, sum
, prod
, any
, all
, map
, filter
among others, can all be defined with folding/reduce functions.
Here are some simplistic examples, using lambdas for conciseness:
first
and last
don't require any loop or explicit recursion. first
uses foldr
taking advantage of the right folding whereas last
relies on foldl
.
In this era of rediscovery of functional programming, there is much more to explore and to apply to languages that are not inherently functional. Arguably, from a pragmatic perspective, there may be little we need that is not already provided in the current versions of Python and that would require some sophisticated folding mechanisms. Further more, other higher-order functions flagships along with fold
, like map
and filter
, can be expressed in Python with elegant list comprehensions and generator expressions, but this should be the subject of a different article.
In the book , the authors and wrote a section on the Laws of fold. The first three laws are called duality theorems and concern the relationship between foldl
and foldr
. For simplification and in the context of this article, let's focus on the first and third duality theorems.
For all finite lists xs
, if f
is and has identity element e
, then foldr f e xs = foldl f e xsfoldr f e xs = foldl f e xs
To concretely illustrate this principle in the , see the following example using the addition as operation and 0 as the for addition:
To illustrate this principle, let's take another simple example in , this time with subtraction that is not associative:
Despite some resistance from Guido Van Rossum (see ), Python has a Fold function. It is named and is a built-in function in Python 2. In Python 3, it can be found in the module: .
Python already has foldl
because is a foldl
construct. As an exercise and to mimic Haskell, a foldl
function can be written as follows with a lambda:
Note: xs[::-1]
is the Python idiomatic way to return the reverse of a list (see this ). The other option, more readable, is to use the built-in function.
Note: the flip
function above is courtesy of
All the examples above, except product
(in that regard see ), have an existing implementation in Python. Also, all of the functions above are relying on reduce
(foldl
) and none are taking advantage of foldr
.
To avoid ending on a dried note and to justify the functional workout executed in the sections above, here is a simple scenario that may demonstrate a decent usage of foldl
and foldr
in Python. Peter Drake presents this construct in his . Imagine that, given a list, we need to identify the last and/or the first element that satisfies a certain predicate. This could be written as follows: