Functional programming I: pure functions and higher-order functions

Functional programming builds programs out of functions in the mathematical sense: rules that map each input to exactly one output and do nothing else. This lesson introduces the two ideas that everything else in the paradigm rests on. The first is purity: a pure function's result depends only on its arguments, and calling it has no effect on the rest of the world. The second is that functions are values: they can be stored in variables, passed as arguments, returned as results and built at run time. Functions that take or return other functions are called higher-order functions, and they let you express whole families of loops as single, reusable operations.

Pure functions and side effects

A function is pure when two conditions hold. Its result is determined entirely by its arguments, so the same arguments always give the same result. And it has no side effects: it does not modify global variables, mutate its arguments, print, read files, depend on the clock or random numbers, or otherwise interact with anything outside itself. The function \(f(x) = x^2 + 1\) is pure. A function that appends to a list passed in, or that returns a different value each time because it reads the current time, is not.

import random
counter = 0

def area(w, h):              # pure: result depends only on arguments
    return w * h

def area_logged(w, h):       # impure: changes global state
    global counter
    counter += 1
    return w * h

def add_item(cart, item):    # impure: mutates its argument
    cart.append(item)
    return cart

def roll():                  # impure: result is not determined by arguments
    return random.randint(1, 6)

print(area(3, 4), area(3, 4))
print(area_logged(3, 4), area_logged(3, 4), "counter =", counter)
c = ["pen"]; add_item(c, "ink"); print("cart after call:", c)

12 12
12 12 counter = 2
cart after call: ['pen', 'ink']

Side effects are not bad in themselves; a program with no effects at all could never show its result. The functional discipline is to push effects to the edges of a program. A core of pure functions does the computation, and a thin outer layer reads input, calls the core, and writes output. The core is then easy to test, because each function can be checked by comparing outputs for given inputs, with no setup or clean-up of external state.

Referential transparency

An expression is referentially transparent if it can be replaced by its value without changing what the program does. If `area(3, 4)` is pure, then anywhere it appears you may write `12` instead, and nothing changes. This property lets you reason about code the way you simplify algebra: substitute equals for equals. It also lets compilers and libraries optimize safely, by caching results, reordering calls or evaluating them in parallel.

Functions as first-class values

A language treats functions as first-class values when functions can be used anywhere other values can: bound to names, stored in data structures, passed to and returned from other functions. Python, JavaScript, Rust and modern Java all do this. In Python, `def` creates a function object and binds it to a name; `lambda` creates an anonymous function from a single expression. Both produce values of the same kind.

def double(x):
    return 2 * x

square = lambda x: x * x
ops = {"double": double, "square": square, "negate": lambda x: -x}

for name, f in ops.items():          # functions stored in a dictionary
    print(f"{name:>6}(7) = {f(7)}")

g = double                           # another name for the same function object
print(g is double, type(g).__name__)

double(7) = 14
square(7) = 49
negate(7) = -7
True function

Storing functions in a dictionary is a common way to replace a long `if`/`elif` chain that dispatches on a command name. Adding a new operation means adding one entry instead of editing a branching statement. This idea, choosing behaviour by looking up a function, reappears in lesson 6 as the strategy and command patterns.

Higher-order functions: map, filter and reduce

A higher-order function takes a function as an argument or returns one. Three classic higher-order functions capture the most common loop shapes. `map(f, xs)` applies `f` to every element. `filter(p, xs)` keeps the elements for which the predicate `p` is true. `reduce(f, xs, init)`, in Python's `functools`, combines the elements into a single value by repeatedly applying a two-argument function. Once you recognize these shapes, many loops collapse into one line that says what is being computed.

from functools import reduce
from operator import add, mul

readings = [12.5, -1.0, 14.2, 13.8, -1.0, 15.1]       # -1.0 marks a failed sensor read

valid = list(filter(lambda r: r >= 0, readings))
in_f = list(map(lambda c: round(c * 9 / 5 + 32, 1), valid))
total = reduce(add, valid, 0.0)
product = reduce(mul, [1, 2, 3, 4, 5], 1)

print("valid:", valid)
print("fahrenheit:", in_f)
print("mean:", round(total / len(valid), 2))
print("5! =", product)

valid: [12.5, 14.2, 13.8, 15.1]
fahrenheit: [54.5, 57.6, 56.8, 59.2]
mean: 13.9
5! = 120

In Python, list comprehensions often express map and filter more readably than lambda: `[c * 9 / 5 + 32 for c in readings if c >= 0]` does both at once. Built-ins such as `sum`, `max`, `min`, `any` and `all` are specialized reductions. Use `reduce` when no specialized function exists, for example to merge a list of dictionaries or to compose a list of functions. Prefer whatever reads most clearly; the paradigm is about avoiding hidden state, not about a particular syntax.

Returning functions: closures

A function defined inside another function can refer to the outer function's variables. When the inner function is returned, it keeps access to those variables even after the outer function has finished. The combination of a function and the variables it captures is called a closure. Closures let you build specialized functions from general ones at run time.

def make_converter(factor, offset=0.0):
    def convert(x):                  # captures factor and offset
        return x * factor + offset
    return convert

c_to_f = make_converter(9 / 5, 32)
km_to_mi = make_converter(0.621371)

print(c_to_f(100), c_to_f(-40))
print(round(km_to_mi(42.195), 2))
print("captured:", [cell.cell_contents for cell in c_to_f.__closure__])

212.0 -40.0
26.22
captured: [1.8, 32]

Each call to `make_converter` creates a new closure with its own captured values, which you can see in the `__closure__` attribute. Closures are the functional counterpart of objects: an object bundles data with methods, and a closure bundles data with one function. In fact, a closure can be used to make a tiny object with private state, and an object with a single method can stand in for a closure. Lesson 6 compares the two when it discusses the strategy pattern.

One trap is worth knowing. Python closures capture variables, not values. If you create several lambdas in a loop that all refer to the loop variable, they all see its final value when they are called later. The usual fix is to bind the current value as a default argument, `lambda x, k=k: x + k`, or to use a factory function as above.

Partial application and composition

Partial application fixes some arguments of a function and returns a function of the rest. Python's `functools.partial` does this without writing a closure by hand. Function composition builds a new function that applies one function and then another: \((g \circ f)(x) = g(f(x))\). Together they let you assemble processing pipelines from small, tested pieces.

from functools import partial, reduce

def power(base, exp):
    return base ** exp

square = partial(power, exp=2)
cube = partial(power, exp=3)
print(square(9), cube(4))

def compose(*fs):
    """compose(f, g, h)(x) == f(g(h(x)))"""
    return reduce(lambda f, g: lambda x: f(g(x)), fs, lambda x: x)

clean = compose(str.title, str.strip, lambda s: s.replace("_", " "))
print(repr(clean("  data_science_basics  ")))

81 64
'Data Science Basics'

Functional style in Java and the limits of purity in Python

Functional ideas are not unique to Python. Java's streams, added in Java 8, provide map, filter and reduce over collections with lambdas. The program below computes the same sensor statistics as the Python example. The stream pipeline is a description of the computation; nothing runs until the terminal operation `average` asks for a result, a form of laziness you will study in lesson 3.

import java.util.List;

public class Readings {
    public static void main(String[] args) {
        List<Double> readings = List.of(12.5, -1.0, 14.2, 13.8, -1.0, 15.1);
        double mean = readings.stream()
                .filter(r -> r >= 0)
                .mapToDouble(Double::doubleValue)
                .average()
                .orElse(Double.NaN);
        List<Double> fahrenheit = readings.stream()
                .filter(r -> r >= 0)
                .map(c -> Math.round((c * 9 / 5 + 32) * 10) / 10.0)
                .toList();
        System.out.printf("mean = %.2f%n", mean);
        System.out.println("fahrenheit = " + fahrenheit);
    }
}

mean = 13.90
fahrenheit = [54.5, 57.6, 56.8, 59.2]

Python does not enforce purity. Nothing stops a function from mutating its arguments, and lists and dictionaries are mutable by default. Functional programming in Python is therefore a discipline you choose: write functions that return new values, avoid global state, and keep effects at the boundaries. Languages such as Haskell enforce purity in the type system, marking effectful code explicitly. Lesson 7 discusses how types can carry this kind of information.