Introduction to Functional Programming

The previous lesson noted that objects carry state and that a program splits into many pieces of mutable state. Tracing how far a change spreads becomes harder as the program grows.

Functional programming answers this problem at the root: never change values. Computation is not updating something that already exists but producing a new value from the input.

The Pure Function

A function is pure if it satisfies two conditions:

1. It always returns the same result for the same input.
2. It has no observable side effect — it does not change its argument, does not update outside state, does not print to the screen.

def average(measurements: list[int]) -> float:      # pure
    return sum(measurements) / len(measurements)

total_count = 0

def dirty_average(measurements: list[int]) -> float:   # not pure
    global total_count
    total_count += 1                                    # outside state changed
    measurements.sort()                                 # argument changed
    return sum(measurements) / len(measurements)

Purity has four practical consequences. A function can be tested independently of its context: input goes in, output is checked. Its result can be memoized — the memoization technique from the recursion lesson only holds for pure functions. Because its calls are independent of one another, it can be run in parallel across threads. And reading it requires looking only at itself; there is no need to know the state of anything remote.

Immutability

Purity’s precondition is that values are not changed. Instead of adding an element to a list, a new list is produced that contains the old elements plus the new one.

measurements = [12, 18, 7]

extended = measurements + [25]           # a new list was produced
print(measurements, extended)            # [12, 18, 7] [12, 18, 7, 25]

sorted_measurements = sorted(measurements)   # a new list
print(measurements, sorted_measurements)     # [12, 18, 7] [7, 12, 18]

At first glance this means a copying cost. Functional languages reduce this cost with persistent data structures: the new version shares the unchanged parts of the old one, and only the changed path is copied. These structures are covered in the data structures course.

The gain of immutability is that the sharing problem from the variables lesson disappears. Sharing an immutable value is safe; no one can change it out from under someone else. The same reasoning also removes the need for a defensive copy.

Functions Are Values

The second core idea of the functional approach is that a function is also a value: it can be bound to a variable, passed as an argument, returned as a result. The closure example from the scope lesson was the first application of this.

A function that takes or returns a function is called a higher-order function. Three occur in nearly every language:

• Map: Passes each element through a function, producing a new sequence of the same length.
• Filter: Selects the elements that satisfy a condition.
• Reduce: Collapses a sequence into a single value with a combining function.

from functools import reduce

raw = [12, -1, 18, -1, 25, 14]

valid = list(filter(lambda m: m >= 0, raw))            # filter
print(valid)                                             # [12, 18, 25, 14]

metric = list(map(lambda m: m / 100, valid))            # map
print(metric)                                             # [0.12, 0.18, 0.25, 0.14]

total = reduce(lambda a, b: a + b, valid, 0)             # reduce
largest = reduce(lambda a, b: a if a > b else b, valid)

print(total, total / len(valid), largest)                # 69 17.25 25

These three operations are named versions of the accumulator pattern. In the loop version, what is being done is buried in the body; here, the name of the operation is visible directly: is it filtering, transforming, or totaling.

The starting value of reduce is the same issue as the identity-element discussion from the loops lesson; if no starting value is given for an empty sequence, the reduction is undefined.

Composition

Small, pure functions are chained so that the output of one becomes the input of the next. This chain is called composition and is the basic organizing form of functional programs.

def valid_ones(measurements: list[int]) -> list[int]:
    return [m for m in measurements if m >= 0]

def average(measurements: list[int]) -> float:
    return sum(measurements) / len(measurements)

def summary(raw: list[int]) -> tuple[float, int]:
    """Produces the average and the largest value from raw data; changes nothing."""
    valid = valid_ones(raw)
    return average(valid), max(valid)

raw = [12, -1, 18, -1, 25, 14]
print(summary(raw))              # (17.25, 25)
print(raw)                       # [12, -1, 18, -1, 25, 14]  — input unchanged

In the object-oriented solution, data sat inside an object and changed through messages; here, data flows between functions and each step produces a new value.

Lazy Evaluation

Transformation chains tend to produce an intermediate collection at every step: filter produces one new list, map another. If the input is large, these intermediate results take up unnecessary space in memory.

The lazy iteration introduced in the loop-control lesson solves this problem: values are produced as they are requested, and each step of the chain flows through a single element at a time. No intermediate list is ever created.

The second consequence of laziness is that infinite sequences can be defined. The first five elements of a sequence with no end can be taken; because the elements not taken are never computed, the computation is finite even though the definition is not. Some functional languages make laziness the default behavior; in most languages it is offered as a separate construct.

Its cost is that when the computation happens becomes uncertain: it runs not when the chain is built but when the result is requested. Combined with side-effecting code, this leads to behavior whose order cannot be predicted — which is why laziness is discussed together with pure functions.

Where Side Effects Go

A program with no side effects at all is useless: a result has to be written somewhere, an input has to be read from somewhere. The functional approach does not ignore side effects; it moves them to a boundary.

The common layout is this: the core of the program consists of pure functions, an outer shell handles input and output. The shell reads data, hands it to the core, writes the returned result. This keeps the entire business logic testable; the part that is hard to test is kept thin.

This layout applies not only in functional languages but in any language. That none of the computation functions written throughout this course print to the screen was a deliberate application of this separation.

Limits

The functional approach has costs of its own. Problems that are inherently stateful — a game’s current state, whether a connection is open — require turning state into a value and producing a new version at every step; this can, at times, produce an unnatural model.

Performance also does not always come for free: although sharing persistent structures is good, updating a mutable array in place is generally cheaper.

For this reason, most languages do not commit to a single paradigm. Combining a pure core with a stateful edge, objects together with functions, is common practice.

Summary

• A pure function returns the same result for the same input and has no side effect; testability, memoization, and parallelism all follow from these two conditions.
• Immutability means producing a new value instead of updating one; it makes sharing safe and removes the need for a defensive copy.
• Functions are values; map, filter, and reduce are named forms of the accumulator pattern.
• Composition is the chaining of small pure functions and is the basic organizing form of a functional program.
• Side effects are not ignored but moved to the boundary of the program: a pure core, a stateful shell.
• The approach carries a cost for inherently stateful problems and where in-place updates are cheap.

Next Step

All three paradigms solved the same problem, and all three are supported with different weight across different languages. The final lesson of the course takes up the axes along which a language differs and how to choose a language to learn, then states which course carries forward the concepts built in this course.