Functional Programming Foundations
Introduction
Functional programming (FP) is a programming paradigm that treats computation as the evaluation of mathematical functions, avoiding mutable state and side effects. This reading covers core FP concepts and their benefits for writing correct, maintainable code.
Learning Objectives
By the end of this reading, you will be able to:
- Understand pure functions and referential transparency
- Apply immutability patterns
- Use first-class and higher-order functions
- Implement recursion and tail recursion
- Recognize the benefits of functional style
1. Pure Functions
Definition
A pure function has two properties:
- Same inputs always produce the same output (deterministic)
- No side effects (doesn't modify external state)
# PURE: Output depends only on inputs
def add(a: int, b: int) -> int:
return a + b
def square(x: float) -> float:
return x * x
def greet(name: str) -> str:
return f"Hello, {name}!"
# IMPURE: Depends on external state
counter = 0
def increment_counter() -> int:
global counter
counter += 1 # Side effect: modifies external state
return counter
# IMPURE: Same input, different output
import random
def random_add(x: int) -> int:
return x + random.randint(1, 10) # Non-deterministic
# IMPURE: Side effect (I/O)
def log_and_return(x: int) -> int:
print(f"Value: {x}") # Side effect: I/O
return x
Benefits of Pure Functions
# 1. TESTABILITY: Easy to test, no setup needed
def test_add():
assert add(2, 3) == 5
assert add(-1, 1) == 0
assert add(0, 0) == 0
# No mocking, no state setup!
# 2. REASONING: Can substitute equals for equals
def example():
x = add(2, 3) # x = 5
y = add(2, 3) # y = 5
# We KNOW x == y, always
# 3. PARALLELIZATION: Safe to run concurrently
from concurrent.futures import ThreadPoolExecutor
def parallel_pure_operations(numbers):
"""Pure functions can run in parallel safely"""
with ThreadPoolExecutor() as executor:
# No race conditions because square is pure
results = list(executor.map(square, numbers))
return results
# 4. MEMOIZATION: Safe to cache results
from functools import lru_cache
@lru_cache(maxsize=128)
def fibonacci(n: int) -> int:
"""Pure function can be memoized"""
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Works because fib(5) ALWAYS returns the same value
Referential Transparency
An expression is referentially transparent if it can be replaced with its value without changing program behavior.
# Referentially transparent
def double(x):
return x * 2
# This:
result = double(5) + double(5)
# Can be replaced with:
result = 10 + 10
# Or even:
result = 20
# NOT referentially transparent
def get_time():
import time
return time.time()
# This:
# result = get_time() + get_time()
# CANNOT be replaced with a single value
# because each call returns different result
2. Immutability
Concept
Immutability means data cannot be changed after creation. Instead of modifying, we create new values.
from typing import NamedTuple, FrozenSet
from dataclasses import dataclass
# MUTABLE approach (imperative)
class MutablePerson:
def __init__(self, name: str, age: int):
self.name = name
self.age = age
def have_birthday(self):
self.age += 1 # Mutates in place
# IMMUTABLE approach (functional)
class ImmutablePerson(NamedTuple):
name: str
age: int
def have_birthday(self) -> 'ImmutablePerson':
# Returns NEW person, doesn't mutate
return ImmutablePerson(self.name, self.age + 1)
# Usage
person1 = ImmutablePerson("Alice", 30)
person2 = person1.have_birthday()
print(person1.age) # 30 (unchanged)
print(person2.age) # 31 (new object)
Immutable Data Structures
from typing import Tuple, FrozenSet
from collections import namedtuple
# Tuple (immutable list)
coordinates = (10, 20, 30)
# coordinates[0] = 5 # Error! Tuples are immutable
# FrozenSet (immutable set)
tags = frozenset(['python', 'functional', 'programming'])
# tags.add('new') # Error! FrozenSets are immutable
# Named tuples
Point = namedtuple('Point', ['x', 'y'])
p1 = Point(3, 4)
p2 = p1._replace(x=5) # Create new point with different x
# Frozen dataclass
@dataclass(frozen=True)
class Vector:
x: float
y: float
def add(self, other: 'Vector') -> 'Vector':
return Vector(self.x + other.x, self.y + other.y)
def scale(self, factor: float) -> 'Vector':
return Vector(self.x * factor, self.y * factor)
v1 = Vector(1, 2)
v2 = Vector(3, 4)
v3 = v1.add(v2) # New vector, v1 and v2 unchanged
Immutable Collections in Practice
from typing import List, Dict, Tuple
def immutable_list_operations():
"""Functional operations on lists return new lists"""
original = [1, 2, 3, 4, 5]
# Adding element: create new list
with_six = original + [6]
# Or: [*original, 6]
# Removing element: create new list
without_first = original[1:]
# Transforming: create new list
doubled = [x * 2 for x in original]
# Original is unchanged
print(original) # [1, 2, 3, 4, 5]
def immutable_dict_operations():
"""Functional operations on dicts"""
original = {'a': 1, 'b': 2}
# Adding/updating: create new dict
with_c = {**original, 'c': 3}
# Removing: create new dict
without_a = {k: v for k, v in original.items() if k != 'a'}
# Original unchanged
print(original) # {'a': 1, 'b': 2}
# Efficient immutable updates with structural sharing
class ImmutableList:
"""Simple immutable list with structural sharing"""
def __init__(self, items: tuple = ()):
self._items = items
def append(self, item) -> 'ImmutableList':
"""O(n) - in practice, use persistent data structures"""
return ImmutableList(self._items + (item,))
def prepend(self, item) -> 'ImmutableList':
"""O(n) - in practice, use persistent data structures"""
return ImmutableList((item,) + self._items)
def __iter__(self):
return iter(self._items)
def __repr__(self):
return f"ImmutableList({list(self._items)})"
3. First-Class Functions
Functions as Values
In FP, functions are first-class citizens: they can be assigned to variables, passed as arguments, and returned from other functions.
from typing import Callable
# Assign function to variable
def add(a, b):
return a + b
operation = add
result = operation(2, 3) # 5
# Store functions in data structures
operations = {
'add': lambda a, b: a + b,
'sub': lambda a, b: a - b,
'mul': lambda a, b: a * b,
'div': lambda a, b: a / b if b != 0 else None
}
def calculate(op: str, a: float, b: float) -> float:
return operations[op](a, b)
print(calculate('add', 10, 5)) # 15
print(calculate('mul', 10, 5)) # 50
Functions as Arguments
from typing import List, Callable, TypeVar
T = TypeVar('T')
U = TypeVar('U')
def apply_to_all(func: Callable[[T], U], items: List[T]) -> List[U]:
"""Apply function to each item"""
return [func(item) for item in items]
# Usage
numbers = [1, 2, 3, 4, 5]
squared = apply_to_all(lambda x: x ** 2, numbers)
stringified = apply_to_all(str, numbers)
# Custom filter
def filter_by(predicate: Callable[[T], bool], items: List[T]) -> List[T]:
"""Keep items that satisfy predicate"""
return [item for item in items if predicate(item)]
evens = filter_by(lambda x: x % 2 == 0, numbers)
Functions as Return Values
from typing import Callable
def make_multiplier(factor: int) -> Callable[[int], int]:
"""Return a function that multiplies by factor"""
def multiplier(x: int) -> int:
return x * factor
return multiplier
double = make_multiplier(2)
triple = make_multiplier(3)
print(double(5)) # 10
print(triple(5)) # 15
# Practical example: validation factory
def make_range_validator(min_val: float, max_val: float) -> Callable[[float], bool]:
"""Return a function that validates if value is in range"""
def validator(value: float) -> bool:
return min_val <= value <= max_val
return validator
is_valid_percentage = make_range_validator(0, 100)
is_valid_temperature = make_range_validator(-273.15, 1000)
print(is_valid_percentage(50)) # True
print(is_valid_percentage(150)) # False
Closures
A closure is a function that captures variables from its enclosing scope.
def make_counter(start: int = 0) -> Callable[[], int]:
"""Create a counter function (note: this uses mutation!)"""
count = [start] # Use list to allow mutation in closure
def counter() -> int:
count[0] += 1
return count[0]
return counter
counter1 = make_counter()
counter2 = make_counter(100)
print(counter1()) # 1
print(counter1()) # 2
print(counter2()) # 101
print(counter1()) # 3
# Pure functional counter (no mutation)
def pure_counter(count: int) -> tuple:
"""Return (current_count, next_counter_function)"""
return count, lambda: pure_counter(count + 1)
value, next_counter = pure_counter(0)
print(value) # 0
value, next_counter = next_counter()
print(value) # 1
4. Recursion
Basic Recursion
Functional programming favors recursion over loops for iteration.
# Imperative loop
def sum_list_imperative(numbers: List[int]) -> int:
total = 0
for n in numbers:
total += n
return total
# Functional recursion
def sum_list_recursive(numbers: List[int]) -> int:
if not numbers:
return 0
return numbers[0] + sum_list_recursive(numbers[1:])
# Common recursive patterns
def factorial(n: int) -> int:
if n <= 1:
return 1
return n * factorial(n - 1)
def length(lst: list) -> int:
if not lst:
return 0
return 1 + length(lst[1:])
def reverse(lst: list) -> list:
if not lst:
return []
return reverse(lst[1:]) + [lst[0]]
Tail Recursion
Tail recursion is when the recursive call is the last operation. It can be optimized to use constant stack space.
# NOT tail recursive (multiplication after recursive call)
def factorial_not_tail(n: int) -> int:
if n <= 1:
return 1
return n * factorial_not_tail(n - 1) # * happens AFTER return
# Tail recursive (recursive call is last operation)
def factorial_tail(n: int, accumulator: int = 1) -> int:
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator) # Nothing after this
# Tail recursive sum
def sum_tail(numbers: List[int], accumulator: int = 0) -> int:
if not numbers:
return accumulator
return sum_tail(numbers[1:], accumulator + numbers[0])
# Note: Python doesn't optimize tail calls, but the pattern is still useful
# for reasoning and can be converted to loops
Converting Recursion to Iteration
# Recursive fibonacci (exponential time)
def fib_recursive(n: int) -> int:
if n < 2:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
# Tail recursive fibonacci
def fib_tail(n: int, a: int = 0, b: int = 1) -> int:
if n == 0:
return a
return fib_tail(n - 1, b, a + b)
# Equivalent iterative (derived from tail recursive)
def fib_iterative(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# Trampoline for Python (manual tail call optimization)
class TailCall:
def __init__(self, func, *args):
self.func = func
self.args = args
def trampoline(result):
"""Execute tail calls without growing stack"""
while isinstance(result, TailCall):
result = result.func(*result.args)
return result
def factorial_trampoline(n: int, acc: int = 1):
if n <= 1:
return acc
return TailCall(factorial_trampoline, n - 1, n * acc)
# Usage
result = trampoline(factorial_trampoline(1000)) # Won't overflow stack
5. Expression-Oriented Style
Expressions vs Statements
Functional programming prefers expressions (which return values) over statements (which perform actions).
# Statement-oriented (imperative)
def get_grade_imperative(score: int) -> str:
if score >= 90:
grade = 'A'
elif score >= 80:
grade = 'B'
elif score >= 70:
grade = 'C'
elif score >= 60:
grade = 'D'
else:
grade = 'F'
return grade
# Expression-oriented (functional)
def get_grade_functional(score: int) -> str:
return (
'A' if score >= 90 else
'B' if score >= 80 else
'C' if score >= 70 else
'D' if score >= 60 else
'F'
)
# Using pattern matching (Python 3.10+)
def get_grade_match(score: int) -> str:
match score:
case s if s >= 90: return 'A'
case s if s >= 80: return 'B'
case s if s >= 70: return 'C'
case s if s >= 60: return 'D'
case _: return 'F'
Declarative Style
# Imperative: HOW to do it
def find_adults_imperative(people: List[dict]) -> List[str]:
result = []
for person in people:
if person['age'] >= 18:
result.append(person['name'])
return result
# Declarative: WHAT we want
def find_adults_declarative(people: List[dict]) -> List[str]:
return [
person['name']
for person in people
if person['age'] >= 18
]
# Even more declarative with functions
from functools import partial
def is_adult(person: dict) -> bool:
return person['age'] >= 18
def get_name(person: dict) -> str:
return person['name']
def find_adults_composed(people: List[dict]) -> List[str]:
adults = filter(is_adult, people)
names = map(get_name, adults)
return list(names)
Exercises
Basic
Identify which of the following functions are pure:
def f(x): return x + 1def g(x): print(x); return xdef h(x): return random.random() + x
Rewrite this mutable class as immutable:
class Rectangle: def __init__(self, w, h): self.width = w self.height = h def scale(self, factor): self.width *= factor self.height *= factorImplement
mapusing recursion.
Intermediate
Convert this loop to a pure recursive function:
def sum_squares(n): total = 0 for i in range(1, n+1): total += i * i return totalImplement a tail-recursive version of list reversal.
Create a function factory that generates validators for different data types.
Advanced
Implement a persistent (immutable) linked list with O(1) prepend.
Write a memoization decorator that works with recursive functions.
Design an immutable binary tree with update operations.
Summary
- Pure functions always return the same output for the same input
- Immutability prevents bugs from shared mutable state
- First-class functions enable powerful abstractions
- Recursion replaces loops in functional programming
- Expression-oriented style leads to more declarative code