Recursions and Reductions
In both cases, the result is iterable. We must do something following this to
materialize a sequence object:
list(mapg(lambda x:2**x, [0, 1, 2, 3, 4]))
[1, 2, 4, 8, 16]
For performance and scalability, this kind of tail-call optimization is essentially
required in Python programs. It makes the code less than purely functional.
However, the benefit far outweighs the lack of purity. In order to reap the benefits of
succinct and expression functional design, it is helpful to treat these less-than-pure
functions as if they were proper recursions.
What this means, pragmatically, is that we must avoid cluttering up a collection
processing function with additional stateful processing. The central tenets of
functional programming are still valid even if some elements of our programs are
less than purely functional.
Reductions and folding – from many to one
We can consider the sum() function to have the following kind of definition:
We could say that the sum of a collection is 0 for an empty collection. For a non-empty
collection the sum is the first element plus the sum of the remaining elements.
()
[] ()[]()
()(^00)
sum
0 sum 1: 0
C
C
CC C
=
=
+ >
if len
if len
Similarly, we can compute the product of a collection of numbers recursively using
two cases:
()
[] ()[]
()
()
(^10)
prod
0 prod 1: 0
C
C
CC C
=
=
× >
if len
if len
The base case defines the product of an empty sequence as 1. The recursive case
defines the product as the first item times the product of the remaining items.
We've effectively folded in × or + operators between each item of the sequence.
Further, we've grouped the items so that processing will be done right-to-left.
This could be called a fold-right way of reducing a collection to a single value.