Sign In Start Free Trial
Account

Add to playlist

Create a Playlist

Modal Close icon
You need to login to use this feature.
  • Book Overview & Buying Functional Python Programming, 3rd edition
  • Table Of Contents Toc
  • Feedback & Rating feedback
Functional Python Programming, 3rd edition

Functional Python Programming, 3rd edition

By : Steven F. Lott
4.5 (28)
close
close
Functional Python Programming, 3rd edition

Functional Python Programming, 3rd edition

4.5 (28)
By: Steven F. Lott

Overview of this book

Not enough developers understand the benefits of functional programming, or even what it is. Author Steven Lott demystifies the approach, teaching you how to improve the way you code in Python and make gains in memory use and performance. If you’re a leetcoder preparing for coding interviews, this book is for you. Starting from the fundamentals, this book shows you how to apply functional thinking and techniques in a range of scenarios, with Python 3.10+ examples focused on mathematical and statistical algorithms, data cleaning, and exploratory data analysis. You'll learn how to use generator expressions, list comprehensions, and decorators to your advantage. You don't have to abandon object-oriented design completely, though – you'll also see how Python's native object orientation is used in conjunction with functional programming techniques. By the end of this book, you'll be well-versed in the essential functional programming features of Python and understand why and when functional thinking helps. You'll also have all the tools you need to pursue any additional functional topics that are not part of the Python language.
Table of Contents (18 chapters)
close
close
Preface
16
Other Books You Might Enjoy
17
Index

1.3 A 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 paper Why Functional Programming Matters by John Hughes. The article appeared in a paper called Research Topics in Functional Programming, edited by D. Turner, published by Addison-Wesley in 1990.

Here’s a link to one of the papers in Research Topics in Functional Programming, “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: the Newton-Raphson algorithm for 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 the Fortran code that emphasizes stateful, imperative processing.

The backbone of this approximation is the calculation of the next approximation from the current approximation. The next_() function takes x, an approximation to the sqrt(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 value x such that x = n x, which means x = √-- n.

Note that the name next() would collide with a built-in function. Calling it next_() lets us follow the original presentation as closely as possible, using Pythonic names.

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 the f() function as a lambda that will converge on √ -- n where n = 2. We started with 1.0 as the initial value for a0. Then we evaluated a sequence of recursive evaluations: a1 = f(a0), a2 = f(f(a0)), 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 with doctest. The sequence appears to converge rapidly on √-- 2. 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 of ai 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 the next_() function defined earlier, we’ll get a sequence of approximations to the square root of the n argument.

The repeat() function expects the f() function to have a single argument; however, our next_() function has two arguments. We’ve used a lambda object, lambda x: next_(n, x), to create a partial version of the next_() function with one of two variables bound.

The Python generator functions can’t be trivially recursive; they must explicitly iterate over the recursive results, yielding them individually.

Attempting to use a simple return repeat(f, f(a)) will end the iteration, returning a generator expression instead of yielding values.

There are two ways to return all the values instead of returning a generator expression, which are as follows:

  • We can write an explicit for statement to yield values as follows:

    for x in some_iter: yield x
  • We can use the yield from expression as follows:

    yield from some_iter

Both techniques of yielding the values of a recursive generator function are will have similar results. We’ll try to emphasize yield from.

It turns out that yield and yield from are a bit more sophisticated than we’ve shown here. For our purposes, we’ll limit ourselves to working with recursive results. For more information on the full feature set for yield and yield from, see PEP 342 and PEP 380: https://peps.python.org/pep-0342/ and https://peps.python.org/pep-0380/.

Of course, we don’t want the entire infinite sequence created by the repeat() 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 letter epsilon, 𝜖.

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 the next() function, is bound to a name, b. If |a b|≤ 𝜖, the two values of a and b are close enough to call the value of b the square root; the difference is less than or equal to the very small value of 𝜖. Otherwise, we use the b value in a recursive invocation of the head_tail() function to examine the next pair of values.

Our within() function properly initializes the internal head_tail() function with the first value from the iterable parameter.

We can use the three functions, next_(), repeat(), and within(), 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 the repeat() function to generate a (potentially) infinite sequence of values based on the next_(n,x) function. Our within() function will stop generating values in the sequence when it locates two values with a difference less than 𝜖.

This definition of the sqrt() function provides useful default values to the underlying within() function. It provides an 𝜖 value of 0.0001 and an initial a0 value of 1.0.

A more advanced version could use default parameter values to make changes possible. As an exercise, the definition of sqrt() can be rewritten so an expression such as sqrt(1.0, 0.000_01, 3) will start with an approximation of 1.0 and compute the value of √ -- 3 to within 0.00001. For most applications, the initial a0 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.

The within function shown here is written to match the original article’s function definition. Python’s itertools library provides a takewhile() function that might be better for this application than the within() function. Similarly, the math.isclose() function may be better than the abs(a-b) <= 𝜖 expression used here. Python offers a great many pre-built functional programming features; we’ll look closely at these functions in Chapter 8, The Itertools Module and Chapter 9, Itertools for Combinatorics – Permutations and Combinations.

bookmark search playlist download font-size

Change the font size

margin-width

Change margin width

day-mode

Change background colour

Close icon Search
Country selected

Close icon Your notes and bookmarks

Delete Bookmark

Modal Close icon
Are you sure you want to delete it?
Cancel
Yes, Delete

Confirmation

Modal Close icon
claim successful

Buy this book with your credits?

Modal Close icon
Are you sure you want to buy this book with one of your credits?
Close
YES, BUY