1
Understanding Functional Programming

Functional programming defines a computation using expressions and evaluation; often, they are encapsulated in function definitions. It de-emphasizes or avoids the complexity of state change and mutable objects. This tends to create programs that are more succinct and expressive. In this chapter, we’ll introduce some of the techniques that characterize functional programming. We’ll identify some of the ways to map these features toPython. Finally, we’ll also address some ways in which the benefits of functional programming accrue when we use these design patterns to build Python applications.

This book doesn’t contain a tutorial introduction to the Python language. We assume the reader knows some Python. In many cases, if the reader knows a functional programming language, then that knowledge can be applied to Python via the examples in this book. For background information on Python, seePython in a Nutshell, 4th Edition, or any of the Python introductions from Packt Publishing.

Python has a broad variety of programming features, including numerous ways to support functional programming. As we will see throughout this book, Python is not apurelyfunctional programming language; instead, it relies on a mixture of features. We’ll see that the language offers enough of the right kinds of features to provide the benefits of functional programming. It also retains all the optimization power of an imperative programming language. Further, we can mix the object-oriented and functional features to make use of the best aspects of both paradigms.

We’ll also look at a problem domain that we’ll use for many of the examples in this book. We’ll try to stick closely toExploratory Data Analysis (EDA). For more information, seehttps://www.itl.nist.gov/div898/handbook/eda/eda.htm. The idea of ”exploratory” means doing data collection followed by analysis, with a goal of inferring what model would be appropriate to describe the data. This is a helpful domain because many of the algorithms are good examples of functional programming. Furthermore, the benefits of functional programming accrue rapidly when exploring data to locate trends and relationships.

Our goal is to establish some essential principles of functional programming. The more serious Python code will begin inChapter 2,Introducing EssentialFunctional Concepts.

In this chapter, we’ll focus on the following topics:

• Comparing and contrasting the functional paradigm with other ways of designing software. We’ll look at how Python’s approach can be called a ”hybrid” between functional programming and object-oriented programming.

• We’ll look in depth at a specific example extracted from the functional programming literature.

• We’ll conclude with an overview of EDA and why this discipline seems to provide numerous examples of functional programming.

1.1The functional style of programming

We’ll define functional programming through a series of examples. The distinguishing feature between these examples is the concept ofstate, specifically the state of the computation.

Python’s strong imperative traits mean that the state of a computation is defined by the values of the variables in the various namespaces. Some kinds of statements make a well-defined change to the state by adding, changing, or removing a variable. We call thisimperativebecause specific kinds of statements change the state.

In Python, the assignment statement is the primary way to change the state. Python has other statements, such asglobal ornonlocal, which modify the rules for variables in a particular namespace. Statements such asdef,class, andimport change the processing context. The bulk of the remaining statements provide ways to choose which assignment statements get executed. The focus of all these various statement types, however, is on changing the state of the variables.

In a functional language, we replace the state—the changing values of variables—with a simpler notion of evaluating functions. Each function evaluation creates a new object or objects from existing objects. Since a functional program is a composition of functions, we can design lower-level functions that are easy to understand, and then create compositions of functions that can also be easier to visualize than a complex sequence of statements.

Function evaluation more closely parallels mathematical formalisms. Because of this, we can often use simple algebra to design an algorithm that clearly handles the edge cases and boundary conditions. This makes us more confident that the functions work. It also makes it easy to locate test cases for formal unit testing.

It’s important to note that functional programs tend to be relatively succinct, expressive, and efficient compared to imperative (object-oriented or procedural) programs. The benefit isn’t automatic; it requires careful design. This design effort for functional programming is often smaller than for procedural programming. Some developers experienced in imperative and object-oriented styles may find it a challenge to shift their focus from stateful designs to functional designs.

1.2Comparing and contrasting procedural and functional styles

We’ll use a tiny example program to illustrate a non-functional, or procedural, style of programming. This example computes a sum of a sequence of numbers. Each of the numbers has a specific property that makes it part of the sequence.

def sum_numeric(limit: int = 10) -> int:     s = 0     for n in range(1, limit):         if n % 3 == 0 or n % 5 == 0:             s += n     return s

The sum computed by this function includes only numbers that are multiples of 3 or 5. We’ve made this program strictly procedural, avoiding any explicit use of Python’s object features. The function’s state is defined by the values of the variabless andn. The variablen takes on values such that 1≤n <10. As the iteration involves an ordered exploration of values for then variable, we can prove that it will terminate when the value ofn is equal to the value oflimit.

There are two explicit assignment statements, both setting values for thes variable. These state changes are visible. The value ofn is set implicitly by thefor statement. The state change in thes variable is an essential element of the state of the computation.

Now let’s look at this again from a purely functional perspective. Then, we’ll examine a more Pythonic perspective that retains the essence of a functional approach while leveraging a number of Python’s features.

from collections.abc import Sequence def sumr(seq : Sequence[int]) -> int:     if len(seq) == 0:         return 0     return seq[0] + sumr(seq[1:])

>>> sumr([7, 11]) 18 >>> sumr([11]) 11 >>> sumr([]) 0

from collections.abc import Sequence, Callable def until(         limit: int,         filter_func: Callable[[int], bool],         v: int ) -> list[int]:     if v == limit:         return []     elif filter_func(v):         return [v] + until(limit, filter_func, v + 1)     else:         return until(limit, filter_func, v + 1)

def mult_3_5(x: int) -> bool:     return x % 3 == 0 or x % 5 == 0

>>> until(10, mult_3_5, 0) [0, 3, 5, 6, 9]

def sum_functional(limit: int = 10) -> int:     return sumr(until(limit, mult_3_5, 0))

def sum_hybrid(limit: int = 10) -> int:     return sum(         n for n in range(1, limit)         if n % 3 == 0 or n % 5 == 0     )

>>> sum( ...     n for n in range(1, 10) ...     if n % 3 == 0 or n % 5 == 0 ... ) 23 >>> n Traceback (most recent call last):    File "<stdin>", line 1, in <module> NameError: name ’n’ is not defined

1.3A classic example of functional programming

As part of our introduction, we’ll look at a classic example of functional programming. This is based on the paperWhy Functional Programming Matters by John Hughes. The article appeared in a paper calledResearch Topics inFunctional Programming, edited by D. Turner, published by Addison-Wesley in 1990.

Here’s a link to one of the papers inResearch Topics in FunctionalProgramming, “Why Functional Programming Matters”:http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

This paper is a profound discussion of functional programming. There are several examples given. We’ll look at just one: theNewton-Raphson algorithmfor locating any roots of a function. In this case, we’ll define a function that will compute a square root of a number.

It’s important because many versions of this algorithm rely on the explicit state managed via loops. Indeed, the Hughes paper provides a snippet of theFortran code that emphasizes stateful, imperative processing.

The backbone of this approximation is the calculation of the next approximation from the current approximation. Thenext_() function takesx, an approximation to thesqrt(n) value, and calculates a next value that brackets the proper root. Take a look at the following example:

def next_(n: float, x: float) -> float:     return (x + n / x) / 2

This function computes a series of values that will quickly converge on some valuexsuch thatx=, which meansx=.

Here’s how the function looks when used in Python’s interactive REPL:

>>> n = 2 >>> f = lambda x: next_(n, x) >>> a0 = 1.0 >>> [round(x, 4) ... for x in (a0, f(a0), f(f(a0)), f(f(f(a0))),) ... ] [1.0, 1.5, 1.4167, 1.4142]

We defined thef() function as a lambda that will converge on wheren= 2. We started with 1.0 as the initial value fora₀. Then we evaluated a sequence of recursive evaluations:a₁ =f(a₀),a₂ =f(f(a₀)), and so on. We evaluated these functions using a generator expression so that we could round each value to four decimal places. This makes the output easier to read and easier to use withdoctest. The sequence appears to converge rapidly on. To get a more precise answer, we must continue to perform the series of steps after the first four shown above.

We can write a function that will (in principle) generate an infinite sequence ofa_i values. This series will converge on the proper square root:

from collections.abc import Iterator, Callable def repeat(         f: Callable[[float], float],         a: float ) -> Iterator[float]:     yield a     yield from repeat(f, f(a))

This function will generate a sequence of approximations using a function,f(), and an initial value,a. If we provide thenext_() function defined earlier, we’ll get a sequence of approximations to the square root of then argument.

Therepeat() function expects thef() function to have a single argument; however, ournext_() function has two arguments. We’ve used a lambda object,lambda x: next_(n, x), to create a partial version of thenext_() function with one of two variables bound.

Of course, we don’t want the entire infinite sequence created by therepeat() function. It’s essential to stop generating values when we’ve found the square root we’re looking for. The common symbol for the limit we can consider “close enough” is the Greek letterepsilon,𝜖.

In Python, we have to be a little clever when taking items from an infinite sequence one at a time. It works out well to use a simple interface function that wraps a slightly more complex recursion. Take a look at the following code snippet:

from collections.abc import Iterator def within(         𝜖: float,         iterable: Iterator[float] ) -> float:     def head_tail(             𝜖: float,             a: float,             iterable: Iterator[float]     ) -> float:         b = next(iterable)         if abs(a-b) <= 𝜖:             return b         return head_tail(𝜖, b, iterable)      return head_tail(𝜖, next(iterable), iterable)

We’ve defined an internal function,head_tail(), which accepts the tolerance,𝜖, an item from the iterable sequence,a, and the rest of the iterable sequence,iterable. The first item from the iterable, extracted with thenext() function, is bound to a name,b. If|a−b|≤𝜖, the two values ofa andb are close enough to call the value ofb the square root; the difference is less than or equal to the very small value of𝜖. Otherwise, we use theb value in a recursive invocation of thehead_tail() function to examine the next pair of values.

Ourwithin() function properly initializes the internalhead_tail() function with the first value from theiterable parameter.

We can use the three functions,next_(),repeat(), andwithin(), to create a square root function, as follows:

def sqrt(n: float) -> float:     return within(         𝜖=0.0001,         iterable=repeat(             lambda x: next_(n, x),             1.0         )     )

We’ve used therepeat() function to generate a (potentially) infinite sequence of values based on thenext_(n,x) function. Ourwithin() function will stop generating values in the sequence when it locates two values with a difference less than𝜖.

This definition of thesqrt() function provides useful default values to the underlyingwithin() function. It provides an𝜖value of 0.0001 and an initiala₀ value of 1.0.

A more advanced version could use default parameter values to make changes possible. As an exercise, the definition ofsqrt() can be rewritten so an expression such assqrt(1.0, 0.000_01, 3) will start with an approximation of 1.0 and compute the value of to within 0.00001. For most applications, the initiala₀ value can be 1.0. However, the closer it is to the actual square root, the more rapidly this algorithm converges.

The original example of this approximation algorithm was shown in the Miranda language. It’s easy to see there are some profound differences between Miranda and Python. In spite of the differences, the similarities give us confidence that many kinds of functional programming can be easily implemented in Python.

Thewithin function shown here is written to match the original article’s function definition. Python’sitertools library provides atakewhile() function that might be better for this application than thewithin() function. Similarly, themath.isclose() function may be better than theabs(a-b) <= 𝜖 expression used here. Python offers a great many pre-built functional programming features; we’ll look closely at these functions inChapter 8,The ItertoolsModule andChapter 9,Itertools for Combinatorics – Permutations andCombinations.

1.4Exploratory data analysis

Later in this book, we’ll use the field of exploratory data analysis as a source for concrete examples of functional programming. This field is rich with algorithms and approaches to working with complex datasets; functional programming is often a very good fit between the problem domain and automated solutions.

While details vary from author to author, there are several widely accepted stages of EDA. These include the following:

• Data preparation: This might involve extraction and transformation for source applications. It might involve parsing a source data format and doing some kind of data scrubbing to remove unusable or invalid data. This is an excellent application of functional design techniques.

• Data exploration: This is a description of the available data. This usually involves the essential statistical functions. This is another excellent place to explore functional programming. We can describe our focus as univariate and bivariate statistics, but that sounds too daunting and complex. What this really means is that we’ll focus on mean, median, mode, and other related descriptive statistics. Data exploration may also involve data visualization. We’ll skirt this issue because it doesn’t involve very much functional programming.

• Data modeling and machine learning: This tends to be prescriptive as it involves extending a model to new data. We’re going to skirt around this because some of the models can become mathematically complex. If we spend too much time on these topics, we won’t be able to focus on functional programming.

• Evaluation and comparison: When there are alternative models, each must be evaluated to determine which is a better fit for the available data. This can involve ordinary descriptive statistics of model outputs, which can benefit from functional design techniques.

One goal of EDA is often to create a model that can be deployed as a decision support application. In many cases, a model might be a simple function. A functional programming approach can apply the model to new data and display results for human consumption.

1.5Summary

In this chapter, we’ve looked at programming paradigms with an eye toward distinguishing the functional paradigm from the imperative paradigm. For our purposes, object-oriented programming is a kind of imperative programming; it relies on explicit state changes. Our objective in this book is to explore the functional programming features of Python. We’ve noted that some parts of Python don’t allow purely functional programming; we’ll be using some hybrid techniques that meld the good features of succinct, expressive functional programming with some high-performance optimizations in Python.

In the next chapter, we’ll look at five specific functional programming techniques in detail. These techniques will form the essential foundation for our hybridized functional programming in Python.

1.6Exercises

The exercises in this book are based on code available from Packt Publishing on GitHub. Seehttps://github.com/PacktPublishing/Functional-Python-Programming-3rd-Edition.

In some cases, the reader will notice that the code provided on GitHub includes partial solutions to some of the exercises. These serve as hints, allowing the reader to explore alternative solutions.

In many cases, exercises will need unit test cases to confirm they actually solve the problem. These are often identical to the unit test cases already provided in the GitHub repository. The reader will need to replace the book’s example function name with their own solution to confirm that it works.

1.6.1Convert an imperative algorithm to functional code

The following algorithm is stated as imperative assignment statements and a while construct to indicate processing something iteratively.

What does this appear to compute? Given Python built-in functions likesum, can this be simplified?

It helps to write this in Python and refactor the code to be sure that correct answers are created.

A test case is the following:

The computed value formis approximately7.5.

1.6.2Convert step-wise computation to functional code

The following algorithm is stated as a long series of single assignment statements. The rad(x) function converts degrees to radians, rad(d) =π×. See themath module for an implementation.

Is this code easy to understand? Can you summarize this computation as a short mathematical-looking formula?

Breaking it down into sections, lines 1 to 8 seem to be focused on some conversions, differences, and mid-point computations. Lines 9 to 12 compute two values,xandy. Can these be summarized or simplified? The final four lines do a relatively direct computation ofd. Can this be summarized or simplified? As a hint, look atmath.hypot() for a function that might be applicable in this case.

It helps to write this in Python and refactor the code.

A test case is the following:

  lat₁←32.82950
  lon₁←−79.93021
  lat₂←32.74412
  lon₂←−79.85226

The computed value fordis approximately6.4577.

Refactoring the code can help to confirm your understanding.

from collections import Counter import csv from pathlib import Path  DEFAULT_PATH = Path.cwd() / "address.csv"  def main(source_path: Path = DEFAULT_PATH) -> None:     frequency: Counter[str] = Counter()     with source_path.open() as source:         rdr = csv.DictReader(source)         for row in rdr:             if "-" in row[’ZIP’]:                 text_zip = row[’ZIP’]                 missing_zeroes = 10 - len(text_zip)                 if missing_zeroes:                     text_zip = missing_zeroes*’0’ + text_zip             else:                 text_zip = row[’ZIP’]                 if 5 < len(row[’ZIP’]) < 9:                     missing_zeroes = 9 - len(text_zip)                 else:                     missing_zeroes = 5 - len(text_zip)                 if missing_zeroes:                     text_zip = missing_zeroes*’0’ + text_zip             frequency[text_zip] += 1     print(frequency)  if __name__ == "__main__":     main()

def zip_histogram(         reader: csv.DictReader[str]) -> Counter[str]:     return Counter(         zip_cleanse(             row[’ZIP’]         ) for row in reader     )

1.6.5(Advanced) Optimize this functional code

The following algorithm is stated as a single ”step” that has been decomposed into three separate formulae. The decomposition is more a concession to the need to fit the expression into the limits of a printed page than a useful optimization. The rad(x) function converts degrees to radians, rad(d) =π×.

There are a number of redundant expressions, like rad(lat₁) and rad(lat₂). If these are assigned to local variables, can the expression be simplified?

The final computation ofddoes not match the conventional understanding of computing a hypotenuse,. Should the code be refactored to match the definition inmath.hypot?

It helps to start by writing this in Python and then refactoring the code.

A test case is the following:

  lat₁←32.82950
  lon₁←−79.93021
  lat₂←32.74412
  lon₂←−79.85226

The computed value fordis approximately6.4577.

Refactoring the code can help to confirm your understanding of what this code really does.

Join our community Discord space

Join our Python Discord workspace to discuss and know more about the book:https://packt.link/dHrHU