As a lecturer at the Hogeschool Utrecht, I teach Python to students who are mostly new to programming. Having recently restarted my attempts to learn Haskell, I can relate to students’ feelings of being lost or overwhelmed. It takes me back to when I first started writing code. Not only does it give me the joy of learning something new, the process gives me insight in the things we take for granted when talking about code and learning a language: syntax, problem decomposition, patterns and approaches.
In this post, we explore the similarities and differences in imperative and functional approaches to accumulating values over a sequence using Python and Haskell.
For illustration purposes,
we are going to calculate the sum of a
sequence (list) of integers without using the
sum function in either language.
Accumulation through iteration
The accumulator pattern
is used to collect
information from a sequence and store the
result in a variable. Core to the idea is
that we initiate an accumulator variable
(in the following examples called
and modify that variable when iterating over
To calculate the sum of a list of numbers using the accumulator pattern, one would start counting at 0 and, for each number in the list, add said number to the accumulator value, updating the accumulator value in each iteration. This is an imperative way of thinking: instructions are written in a concrete, step-by-step fashion, modifying a program's state during execution.
In Python, this sum implementation would look as follows:
def acc_sum(numbers): acc = 0 for number in numbers: acc = acc + number return acc result = acc_sum([1, 2, 3]) # Prints: 6 print(result)
Accumulation through recursion
Another way of accumulating values without modifying state can be found in recursion. Using recursion, a problem's solution depends on solutions to smaller instances of the same problem.
There are three rules in order for a recursive function to be effective:
- The function must have a base case
- The function has a recursive case (also: inductive case) that moves towards the base case
- The function calls itself recursively
In imperative languages like Python, recursion can be accomplished by making a function call itself until some form of base case is encountered: a single value is returned instead of calling itself again.
def rec_sum(numbers): # Base case if numbers == : return 0 # Split head and tail x, *xs = numbers # Recursive case return x + rec_sum(xs) result = rec_sum([1, 2, 3]) # Prints: 6 print(result)
We check whether our base case is found
using an if-statement: if we encounter an empty list,
we return 0. If that is not the case, we continue to
the recursive case.
We then split up the input numbers into a head
x) and a tail (called
Then, the result of adding
x to the result of
rec_sum on the tail,
To be able to return a single value,
Python will perform the same operation on the
tail (adding the head to the application of the function
on that respective tail) until the base case is met.
The steps the interpreter will take
rec_sum([1, 2, 3]) recursively
looks somewhat like this:
rec_sum([1, 2, 3]) # Base condition not met: take head, call function on tail 1 + rec_sum([2, 3]) # Base condition not met: take head, call function on tail 2 + 1 + rec_sum() # Base condition met: add 0 to all previous heads 3 + 2 + 1 + rec_sum() # Resulting expression 3 + 2 + 1 + 0
As you can see, the expression
rec_sum([1, 2, 3]) is
resolved, step-by-step, into a resulting expression that
sums them all up:
3 + 2 + 1 + 0.
In Python, we need to use an if-statement to determine our base case. Haskell supports pattern matching, meaning we can define our base case in terms of a certain pattern to match against and our alternate case as another pattern. Pattern matching is a bit like function overloading in C-based languages like C, C++, C# and Java, but more powerful as it not only matches based on type but does some structural matching as well.
rec_sum :: [Int] -> Int rec_sum  = 0 rec_sum (x:xs) = x + rec_sum xs main = do -- Prints: 6 print $ rec_sum [1,2,3] 0
In Haskell, we start with a type definition to establish what our function should be doing: going from a sequence of integers to a single integer.
We define our
rec_sum function twice. The
first definition is our base case: an empty list results
in 0. The second definition is our recursive case:
the input sequence is split up in
a single-value head (called
and a tail sequence (called
We add our integer value from the head to
the result of (recursively) calling the same function
on the tail.
Haskell looks a lot cleaner when doing recursion than Python. This should be no surprise given Haskell's functional nature.
One could imagine that recursion can be expensive with regards to memory, as the interpreter (or compiler) would need to perform a lot of consequent function calls that each operate on the call stack, building up a stack of calls to itself. This is why some programming languages have techniques in place that optimize some forms of recursion by making it look more like its imperative accumulator counterpart.
This can usually only be done when doing tail recursion,
meaning the last call (the tail call)
is the recursion.
In our case, the last operation is not our call to
To make the recursion behave in a tail-recursive manner,
we can pass the accumulator into the function
on each call. This way, the accumulation happens
before each recursive function call.
Runtime or compiler optimizers can then
do tail-call optimization.
In Python, it would look like this:
def trec_sum(numbers, acc = 0): if len(numbers) == 0: return acc return trec_sum(numbers[1:], acc + numbers) result = trec_sum([1, 2, 3]) # Prints: 6 print(result)
However, be advised that Python does not optimize tail calls. This has been a deliberate choice by Guido van Rossum, primary author of Python, as he believes recursion to be unpythonic and tail recursion elimination (TRE) would come at the cost of debuggability. From a language design standpoint, this is understandable: although Python has some functional and declarative constructs, its main philosophy is imperative in nature.
Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)
Although Haskell optimizes in different ways because of the referential transparent properties that come with the purity of the language, we can define an explicit tail-recursive function following the same principle: make sure the function call is the last call that occurs within the function. It looks like this:
trec_sum :: [Int] -> Int -> Int trec_sum  acc = acc trec_sum (x:xs) acc = trec_sum xs (x + acc) main = do -- Prints: 6 print $ trec_sum [1,2,3] 0
You can notice two things. First of all, we explicitly pass in the accumulator between calls. Secondly, the function's type signature has changed. This is because we have to pass in the accumulator's initial value every time. This can be mitigated by introducing another function that refers to the function with explicit tail-call-recursion:
rec_sum :: [Int] -> Int rec_sum xs = trec_sum xs 0 trec_sum :: [Int] -> Int -> Int trec_sum  acc = acc trec_sum (x:xs) acc = trec_sum xs (x + acc) main = do -- Prints: 6 print $ rec_sum [1,2,3]
As we have seen, recursion is a general pattern for breaking up a problem in pieces and introducing a function that can solve each piece by calling itself.
Accumulation through reduction
There is also a functional pattern that specifically tends towards cases of reducing a sequence of values to a single value. In some languages, this is called a reduction or reduce. In other languages this is known as a fold.
The reduce function is a higher-order function, meaning that it takes another function. It applies the given function on each value in order to accumulate a final resulting value.
Because Python is mostly imperative,
reduce function has been hidden away in the
As you can see in the example below,
the reduce function takes a combining function
and an iterable to apply the function on.
Optionally, it takes an
initializer value as a third argument.
from functools import reduce def plus(num, acc): return acc + num def fold_sum(numbers): return reduce(plus, numbers) result = fold_sum([1, 2, 3]) # Prints: 6 print(result)
from functools import reduce def fold_sum(numbers): return reduce(lambda num, acc: num + acc, numbers) result = fold_sum([1, 2, 3]) # Prints: 6 print(result)
Finally, you can refer to the plus operator in Python instead of defining the operation manually. Using the operator module, one can refer to an operator as if it were a function. This reads quite clearly: reduce all numbers by adding them together.
from functools import reduce from operator import add def fold_sum(numbers): return reduce(add, numbers) result = fold_sum([1, 2, 3]) # Prints: 6 print(result)
reduce in a function like
no real value in this case if one can assume
knowledge about what
In Haskell, a fold is used to “process a data structure in some order and build a return value.” It takes a combining function, an initial value and a data structure and combines the values in that data structure when evaluated.
fold_sum :: [Int] -> Int fold_sum = foldl (+) 0 main = do -- Prints: 6 print $ fold_sum [1,2,3]
Types of folds
Fundamentally, there are two types of folds: left folds and right folds.
A left fold combines all elements until the last with the last (left associativity), while a right fold combines the head with the results of combining the tail (right associativity):
-- Left fold: (((1 + 2) + 3) + 4) + 5 foldl (+) 0 [1,2,3,4,5] -- Right fold: 1 + (2 + (3 + (4 + 5))) foldr (+) 0 [1,2,3,4,5]
For commutative operations, operations for which the order does not matter, it does not matter whether you use a left or right fold. For non-commutative operations, like subtraction or division, it does:
-- Left fold: (((1 - 2) - 3) - 4) - 5 -- Results in: -13 (-8 - 5) foldl (-) 0 [1,2,3,4,5] -- Right fold: 1 - (2 - (3 - (4 - 5))) -- Results in: 3 (1 - -2) foldr (-) 0 [1,2,3,4,5]
Just so you know, Python's reduce is a left fold.
from operator import sub # (((1 - 2) - 3) -4) - 5 result = reduce(sub, [1, 2, 3, 4, 5]) # Prints: -13 print(result)
There is also foldl’ (left fold prime).
The use of
to do with strict operator application
and efficiency in relation to Haskell's
Basically, foldl’ is a left fold that prevents stack
overflows because it reduces the chain of calls
early instead of keeping a large call stack
and resolving it in the end.
More information on folds can be found on the
Notice that functional constructs like reduce are more declarative than their imperative counterparts. Instead of stating each individual instruction, you express your intention and the compiler or runtime will figure it out: reduce the list numbers to a single number by adding them together. By using a common language to solve problems that are similar in shape, you can use solutions that are similar in abstraction – like design patterns. These abstractions are composable in nature and ideal for reuse.
This results in less code, but requires familiarity with these higher-level concepts in order to understand it. The cognitive load of stepping through detailed steps in imperative solutions is traded against prior knowledge of common abstractions in more functional approaches. In other words: the “complexity” shifts from what is on the screen to what concepts you know.
I think it is too bad that Python hides away the reduce function in favor of a more imperative approach to accumulation. That being said, Python does have list, set and generator comprehensions. Comprehensions are a declarative way of programming also found in functional languages like Haskell. They are useful to create a new sequence based on an existing sequence and applying a transformation and/or a filter or selection to it. However, comprehensions cannot easily be used to accumulate values, so one of the above patterns would still be necessary. Perhaps we will check out comprehensions in a later post.
Accumulating a single value based on a sequence of values can be done via the imperative accumulator pattern or through functional patterns like recursion or folds.
Functional constructs can be applied to achieve a more declarative style: state your intent and the compiler or runtime will follow. However, this requires a familiarity with these higher-level concepts on the side of the developer.
As we have seen, although functional programming is doable, Python is not really a functional language. It is imperative in nature and avoids typical functional concepts like recursion and folds because of it being “unpythonic” and because of the lack of tail-call optimisation.