Functional Programming

Functional Programming

Functional programming (FP) is a declarative paradigm where programs are built from pure functions without mutable state or side effects. It contrasts with imperative programming (step-by-step instructions) and is a key A-Level topic for understanding different programming approaches.

Key Concepts

1. First-Class Functions

Functions are treated as first-class citizens — they can be:

• Assigned to variables
• Passed as arguments to other functions
• Returned as results from functions
• Stored in data structures

square = lambda x: x ** 2      # function assigned to a variable
numbers = [1, 2, 3, 4]
result = list(map(square, numbers))  # function passed as argument
# result = [1, 4, 9, 16]

2. Pure Functions

A pure function has two properties:

• Its return value depends only on its arguments (no reading global state)
• It has no side effects (no modifying external state, no I/O, no printing)

Pure	Impure
def add(a, b): return a + b	def add(a): total += a (modifies global)
def double(x): return x * 2	def log(x): print(x) (side effect: I/O)
Same input → always same output	Same input → may give different output

Benefits of pure functions:

• Predictable: Easy to test and debug (no hidden dependencies)
• Parallelisable: Can run on multiple cores without data races
• Cacheable: Results can be memoised (cached) since they never change

3. Immutability

In FP, data is never modified after creation. Instead of changing a value, you create a new value.

# Imperative (mutable)
numbers = [1, 2, 3]
numbers.append(4)       # modifies the original list

# Functional (immutable)
numbers = (1, 2, 3)     # tuple - immutable
new_numbers = numbers + (4,)  # creates a new tuple

4. Recursion (not iteration)

FP avoids loops (which require mutable counter variables). Instead, it uses recursion:

# Imperative
def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

# Functional
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Higher-Order Functions

A higher-order function either takes a function as an argument or returns a function. The three most important are:

map(f, list) — applies f to every element:

list(map(lambda x: x * 2, [1, 2, 3]))  # [2, 4, 6]

filter(f, list) — keeps elements where f returns True:

list(filter(lambda x: x > 2, [1, 2, 3, 4]))  # [3, 4]

reduce(f, list) — combines all elements into one value:

from functools import reduce
reduce(lambda acc, x: acc + x, [1, 2, 3, 4])  # 10 (sum)
reduce(lambda acc, x: acc * x, [1, 2, 3, 4])  # 24 (product)

Function Composition

Combining simple functions to build complex ones:

compose(f, g)(x) = f(g(x)) — apply g first, then f

def compose(f, g):
    return lambda x: f(g(x))

double = lambda x: x * 2
add_one = lambda x: x + 1
double_then_add = compose(add_one, double)
double_then_add(3)  # add_one(double(3)) = add_one(6) = 7

Partial Application and Currying

Partial application: Fixing some arguments of a function to create a new function with fewer parameters.

from functools import partial
def multiply(a, b):
    return a * b
double = partial(multiply, 2)   # fix a=2
double(5)  # 10

Currying: Transforming a function that takes multiple arguments into a chain of functions each taking one argument.

# Uncurried
def add(a, b): return a + b

# Curried
def add(a):
    return lambda b: a + b

add(3)(5)   # 8
add_three = add(3)
add_three(5)  # 8

Functional vs Imperative Comparison

Aspect	Imperative	Functional
State	Mutable variables	Immutable values
Control flow	Loops (for, while)	Recursion
Functions	May have side effects	Pure functions
Data	Modified in place	New copies created
Focus	How to do it (steps)	What to compute (declarations)
Example languages	C, Java, Python	Haskell, Lisp, Erlang

Advantages of Functional Programming

• Fewer bugs: No mutable state means no unexpected state changes
• Easier testing: Pure functions are tested by checking input→output (no setup/teardown)
• Parallelism: Immutable data eliminates race conditions
• Mathematical reasoning: Programs can be proved correct using mathematical logic
• Modularity: Small, composable functions encourage reuse

Disadvantages

• Performance: Creating new data structures instead of modifying existing ones uses more memory
• Steep learning curve: Thinking recursively is harder for many programmers
• I/O handling: Input/output is inherently impure; FP languages need special mechanisms (monads in Haskell)
• Some problems are more naturally expressed imperatively (e.g., in-place sorting)

Functional Features in Python

Python is multi-paradigm — it supports both imperative and functional styles:

Feature	Python support
First-class functions	✓ (lambda, def)
Higher-order functions	✓ (map, filter, reduce)
Immutable data	Partial (tuples, frozensets)
List comprehensions	✓ (Pythonic alternative to map/filter)
Pure functions	Convention (not enforced)
Tail-call optimisation	✗ (Python has a recursion limit)

Exam Tips

• Know the definitions of: pure function, first-class function, higher-order function, immutability, function composition, partial application, currying
• Be able to trace map, filter, and reduce on a given list with a given function
• Compare functional and imperative approaches for the same problem — show both solutions
• Common exam question: "Explain why pure functions are easier to test/debug" — answer: no side effects, same input always gives same output, no hidden state dependencies
• Haskell is the canonical functional language in UK specs — you may be asked to identify functional features in pseudocode or Haskell-like syntax
• Remember that Python's lambda creates anonymous functions: lambda x: x + 1