Chapter 6Following is a purely recursive function version of the older map() function:
def mapr(f, collection):
if len(collection) == 0: return []
return mapr(f, collection[:-1]) + [f(collection[-1])]
The value of the mapr(f,[]) method is defined to be an empty list object. The
value of the mapr() function with a non-empty list will apply the function to the
last element in the list and append this to the list built recursively from the mapr()
function applied to the head of the list.
We have to emphasize that this mapr() function actually creates a list object,
similar to the older map() function in Python. The Python 3 map() function is an
iterable, and isn't as good an example of tail-call optimization.
While this is an elegant formalism, it still lacks the tail-call optimization required.
The tail-call optimization allows us to exceed the recursion depth of 1000 and also
performs much more quickly than this naïve recursion.
Tail-call optimization for collections
We have two general ways to handle collections: we can use a higher-order function
which returns a generator expression or we can create a function which uses a for
loop to process each item in a collection. The two essential patterns are very similar.
Following is a higher-order function that behaves like the built-in map() function:
def mapf(f, C):
return (f(x) for x in C)
We've returned a generator expression which produces the required mapping.
This uses an explicit for loop as a kind of tail-call optimization.
Following is a generator function with the same value:
def mapg(f, C):
for x in C:
yield f(x)
This uses a complete for statement for the required optimization.