Create succinct and expressive implementations with functional programming in Python
Key Features
Learn how to choose between imperative and functional approaches based on
expressiveness, clarity, and performance
Get familiar with complex concepts such as monads, concurrency, and immutability
Apply functional Python to common Exploratory Data Analysis (EDA) programming
problems
Book Description
If you're a Python developer who wants to discover how to take the power of functional programming (FP) and bring it into your own programs, then this book is essential for you, even if you know next to nothing about the paradigm.
Starting with a general overview of functional concepts, you'll explore common functional features such as first-class and higher-order functions, pure functions, and more. You'll see how these are accomplished in Python 3.6 to give you the core foundations you'll build upon. After that, you'll discover common functional optimizations for Python to help your apps reach even higher speeds.
You'll learn FP concepts such as lazy evaluation using Python's generator functions and expressions. Moving forward, you'll learn to design and implement decorators to create composite functions. You'll also explore data preparation techniques and data exploration in depth, and see how the Python standard library fits the functional programming model. Finally, to top off your journey into the world of functional Python, you'll at look at the PyMonad project and some larger examples to put everything into perspective.
What you will learn
Use Python's generator functions and generator expressions to work with collections in a non-strict (or lazy) manner
Utilize Python library modules including itertools, functools, multiprocessing, and concurrent features to ensure efficient functional programs
Use Python strings with object-oriented suffix notation and prefix notation
Avoid stateful classes with families of tuples
Design and implement decorators to create composite functions
Use functions such as max(), min(), map(), filter(), and sorted()
Write higher-order functions
Who this book is for
This book is for Python developers who would like to perform Functional programming with Python. Python Programming knowledge is assumed.
In this chapter, we'll look at some optimizations that we can make to create high-performance functional programs. We will look at the following topics:
We'll expand on using the @lru_cache decorator from Chapter 10, The Functools Module. We have a number of ways to implement the memoization algorithm.
We'll also discuss how to write our own decorators. More importantly, we'll see how to use a Callable object to cache memoized results.
We'll also look at some optimization techniques that were presented in Chapter 6, Recursions and Reductions. We'll review the general approach to tail recursion optimization. For some algorithms, we can combine memoization with a recursive implementation and achieve good performance. For other algorithms, memoization isn't really very helpful and we have to look elsewhere for performance improvements.
We'll look at an extensive case study in optimizing accuracy by using the Fraction class.
In most cases, small changes to a program will only lead to small improvements in performance. Replacing a function with a lambda object will have a tiny impact on performance. If we have a program that is unacceptably slow, we often have to locate a completely new algorithm or data structure. Replacing an
algorithm with one that's
is the best way to create a dramatic improvement in performance.
One place to start on redesign is http://www.algorist.com. This is a resource that may help to locate better algorithms for a given problem.
Memoization and caching
As we saw in Chapter 10, The Functools Module, many algorithms can benefit from memoization. We'll start with a review of some previous examples to characterize the kinds of functions that can be helped with memoization.
In Chapter 6, Recursions and Reductions, we looked at a few common kinds of recursions. The simplest kind of recursion is a tail recursion with arguments that can be easily matched to values in a cache. If the arguments are integers, strings, or materialized collections, then we can compare arguments quickly to determine if the cache has a previously computed result.
We can see from these examples that integer numeric calculations, such as computing factorial or locating a Fibonacci number, will be obviously improved. Locating prime factors and raising integers to powers are more examples of numeric algorithms that apply to integer values.
When we looked at the recursive version of a Fibonacci number,
, calculator, we saw that it contained two tail-call recursions. Here's the definition:
This can be turned into a loop, but any design change requires some thinking. The memoized version of a recursive definition can be quite fast and doesn't require quite so much thinking to design.
The Syracuse function is an example of the kind of function used to compute fractal values. Here's the Syracuse function,
.
Applied recursively, there's a chain of values, C, from a given starting value, n.
The Collatz conjecture is the Syracuse function always leads to 1. The values starting with
form a loop of 1, 4, 2, 1, ... Exploring the behavior of this function requires memoized intermediate results. An interesting question is locating the extremely long sequences. See https://projecteuler.net/problem=14 for an interesting problem that requires careful use of caching.
The recursive application of the Syracuse function is an example of a function with an "attractor," where the value is attracted to 1. In some higher dimensional functions, the attractor can be a line or perhaps a fractal curve. When the attractor is a point, memoization can help; otherwise, memoization may actually be a hindrance, since each fractal value is unique.
When working with collections, the benefits of caching may vanish. If the collection happens to have the same number of integer values, strings, or tuples, then there's a chance that the collection is a duplicate and time can be saved. However, if a calculation on a collection will be needed more than once, manual optimization is best: do the calculation once and assign the results to a variable.
When working with iterables, generator functions, and other lazy objects, caching or memoization is not going to help at all. Lazy functions already do the least amount of work to provide the next value from a source sequence.
Raw data that includes measurements often use floating point values. Since an exact equality comparison between floating point values may not work out well, memoizing intermediate results may not work out well, either.
Raw data that includes counts, however, may benefit from memoization. These are integers, and we can trust exact integer comparisons to (potentially) save recalculating a previous value. Some statistical functions, when applied to counts, can benefit from using the fractions module instead of floating point values. When we replace x/y with the Fraction(x,y) method, we've preserved the ability to do exact value matching. We can produce the final result using the float(some_fraction) method.
Specializing memoization
The essential idea of memoization is so simple that it can be captured by the @lru_cache decorator. This decorator can be applied to any function to implement memoization. In some cases, we may be able to improve on the generic idea with something more specialized. There are a large number of potentially optimizable multivalued functions. We'll pick one here and look at another in a more complex case study.
The binomial,
, shows the number of ways n different things can be arranged in groups of size m. The value is as follows:
Clearly, we should cache the individual factorial calculations rather than redo all those multiplications. However, we may also benefit from caching the overall binomial calculation, too.
We'll create a Callable object that contains multiple internal caches. Here's a helper function that we'll need:
from functools import reduce from operator import mul from typing import Callable, Iterable
The prod() function computes the product of an iterable of numbers. It's defined as a reduction using the * operator.
Here's a Callable object with two caches that uses this prod() function:
class Binomial: def __init__(self): self.fact_cache = {} self.bin_cache = {} def fact(self, n: int) -> int: if n not in self.fact_cache: self.fact_c...
