Higher-Order Functions & Functional Programming

A language feature is called first-class when that thing can be:

1. Stored in a variable
2. Passed as an argument to a function
3. Returned as a result from a function
4. Placed in a data structure (list, dict, etc.)

In most languages, integers and strings are first-class. In Python, JavaScript, Haskell, and many modern languages, functions are also first-class. In older languages like C, functions are not quite first-class — you can pass function pointers, but the mechanism is clunky and limited.

Why does this matter? It means the boundary between "code" and "data" dissolves. A function is just a value that happens to be callable. This enables an entire style of programming where you pass behavior as a parameter, not just data.

The key mental model: Think of a function as a sealed envelope containing a computation recipe. You can hand that envelope to someone else, they can store it in a drawer, and they can open it and run the recipe whenever they want. The act of calling the function is separate from the value of the function itself.

# Python: functions are first-class values

def greet(name):
    return f"Hello, {name}!"

# 1. Store in a variable
my_fn = greet
print(my_fn("Alice"))   # Hello, Alice!

# 2. Put in a data structure
operations = [greet, str.upper, str.lower]
for op in operations:
    print(op("world"))

# 3. Pass to a function
def apply(fn, value):
    return fn(value)          # fn is called here

result = apply(greet, "Bob") # passing greet as an argument
print(result)                # Hello, Bob!

# 4. Lambda: an anonymous function literal (no def needed)
add_one = lambda x: x + 1
print(add_one(5))  # 6

A higher-order function (HOF) is a function that does at least one of:

• Takes one or more functions as arguments
• Returns a function as its result

Regular functions operate on data (numbers, strings, lists). Higher-order functions operate on functions — they abstract over behavior rather than values.

Analogy: A regular function is a machine. A higher-order function is a meta-machine — a machine that accepts other machines as input and produces machines as output. The function apply_twice below takes any function f and applies it twice: apply_twice(f, x) = f(f(x)). This is an operation on functions, not on numbers.

HOFs are the mechanism that makes the rest of this module possible. map, filter, and reduce are all HOFs. So is a function that logs every call to another function (a decorator). So is a function that retries another function on failure.

The power is abstraction over behavior: instead of writing double_all, square_all, and negate_all as three separate list loops, you write map once and pass the behavior as an argument.

# Higher-order functions

# Takes a function and applies it twice
def apply_twice(f, x):
    return f(f(x))

print(apply_twice(lambda x: x + 3, 10))  # 16  (10+3+3)
print(apply_twice(str.upper, "hello"))   # HELLO (idempotent)

# Returns a function — a "function factory"
def make_multiplier(n):
    def multiplier(x):
        return x * n
    return multiplier          # returns a function!

double = make_multiplier(2)
triple = make_multiplier(3)
print(double(5))   # 10
print(triple(5))   # 15

# Decorator: the classic HOF pattern in Python
def logged(fn):
    def wrapper(*args, **kwargs):
        print(f"Calling {fn.__name__} with {args}")
        result = fn(*args, **kwargs)
        print(f"Returned {result}")
        return result
    return wrapper

@logged  # syntactic sugar for: greet = logged(greet)
def greet(name):
    return f"Hi, {name}!"

greet("Carol")

map, filter, and reduce are the canonical trio of higher-order functions that operate on collections. They capture three fundamental patterns in data transformation:

map(f, collection): Apply f to every element, producing a new collection of the same size. Each output element corresponds 1-to-1 with an input element.

• Shape: [a, b, c] → [f(a), f(b), f(c)]
• SQL analogy: the column expressions in SELECT

filter(pred, collection): Keep only elements where the predicate pred returns True. The output is a subset of the input.

• Shape: [a, b, c, d] → [a, c] (if pred is true for a and c)
• SQL analogy: the WHERE clause

reduce(f, collection, init): Fold the collection down to a single value by repeatedly applying f. Also called fold or aggregate.

• Shape: [a, b, c] with init z → f(f(f(z, a), b), c)
• SQL analogy: SUM, MAX, GROUP BY aggregations

The profound insight: Every loop over a list is doing one of these three things (or a combination). By naming them and expressing them with HOFs, we make the intent of the code explicit and eliminate boilerplate. This also makes the code more parallelizable — map over a large list can trivially run each element on a separate CPU core because the operations are independent.

MapReduce at Google scale: Google's 2004 MapReduce paper described indexing the entire web with exactly these two primitives. The map phase assigned each document to key-value pairs; the reduce phase aggregated them across thousands of machines. The framework could be written once and reused for any data processing job.

from functools import reduce

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# map: square every number
squared = list(map(lambda x: x**2, nums))
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

# filter: keep only even numbers
evens = list(filter(lambda x: x % 2 == 0, nums))
# [2, 4, 6, 8, 10]

# reduce: compute the product of all elements
product = reduce(lambda acc, x: acc * x, nums, 1)
# ((((1*1)*2)*3)*...)*10 = 3628800

# Chain them: sum of squares of even numbers
result = reduce(
    lambda acc, x: acc + x,
    map(lambda x: x**2, filter(lambda x: x % 2 == 0, nums)),
    0
)
print(result)  # 4+16+36+64+100 = 220

# In Haskell (purely functional, no mutation):
# sumOfSquaresOfEvens = foldl (+) 0 . map (^2) . filter even $ [1..10]

A closure is a function that captures variables from its surrounding (enclosing) scope, even after that scope has finished executing. The function "closes over" the free variables in its body, carrying them with it.

The mechanism: When a function is defined inside another function, the inner function holds a reference to the environment (the binding of names to values) of the outer function. When the outer function returns, its local variables would normally be garbage collected — but if a closure exists that references them, they are kept alive.

Analogy: Imagine a function as a backpack-carrying worker. A regular function only carries the tools you hand it directly (its arguments). A closure also carries whatever was on the desk when it was created — it remembers the context of its birth.

Why closures are profound: They are the mechanism behind:

• Factory functions (make_multiplier above — each returned function closes over a different n)
• Memoization (a function that closes over a cache dict)
• Private state (a counter function that closes over a count variable — no class needed)
• Decorators (the wrapper closes over the original fn)
• Callbacks and event handlers (a callback closes over the data it needs when the event fires)

In languages like JavaScript, closures are everywhere — they are how modules avoid polluting the global namespace, how React hooks track state, and how async callbacks access request data.

The subtlety — closures capture by reference, not by value (in Python/JS): This is a common source of bugs. If you create closures in a loop and close over the loop variable, all closures may see the final value of that variable. The fix is to create a new binding in each iteration (e.g., a default argument in Python, or let instead of var in JavaScript).

# Closure: the inner function 'remembers' make_counter's local variable
def make_counter(start=0):
    count = start         # this lives in make_counter's frame
    def increment():
        nonlocal count    # grab the enclosing variable
        count += 1
        return count
    return increment      # the returned function closes over 'count'

counter_a = make_counter(0)
counter_b = make_counter(100)
print(counter_a())  # 1
print(counter_a())  # 2
print(counter_b())  # 101  -- independent state!

# Classic closure bug in a loop (Python)
funcs_BAD = [lambda x: x + i for i in range(3)]
print([f(0) for f in funcs_BAD])  # [2, 2, 2] -- all see final i=2!

# Fix: capture the current value of i with a default argument
funcs_GOOD = [lambda x, i=i: x + i for i in range(3)]
print([f(0) for f in funcs_GOOD])  # [0, 1, 2] -- correct!

# In JavaScript, 'let' creates a new binding per iteration
# const fns = [];
# for (let i = 0; i < 3; i++) { fns.push(() => i); }
# fns.map(f => f()); // [0, 1, 2] -- correct because let is block-scoped

Currying (named after logician Haskell Curry) is the transformation of a function that takes multiple arguments into a sequence of functions that each take one argument.

Mathematically: a function f(a, b, c) becomes g(a)(b)(c) — you call g with a, get back a function, call it with b, get back another function, call it with c, and finally get the result.

Partial application is the related but distinct idea of fixing some arguments to a function to produce a new function with fewer parameters. partial(add, 5) fixes the first argument to 5, returning a function that adds 5 to its argument.

Why curry?

1. Reuse: From a general function like multiply(a, b), you can produce double = curry(multiply)(2) and triple = curry(multiply)(3) without writing new functions.
2. Composition with map: map takes a unary function (one argument). Currying lets you turn any multi-argument function into a unary one for use with map. For example, map(curry(add)(5), [1,2,3]) gives [6,7,8].
3. Configurability: Build a general function once, partially apply configuration parameters, and distribute the specialized version.

In Haskell, every function is curried by default. add :: Int -> Int -> Int is a function from Int to (Int -> Int). add 5 is a perfectly valid expression — it's a function from Int to Int. This is not a special case; it's the fundamental calling convention.

Partial application in Python is supported directly via functools.partial. Currying in Python is less idiomatic but achievable.

from functools import partial

# Partial application: fix some arguments early
def power(base, exponent):
    return base ** exponent

square = partial(power, exponent=2)   # fix exponent=2
cube   = partial(power, exponent=3)   # fix exponent=3
print(square(5))   # 25
print(cube(3))     # 27

# Use with map: square all numbers in a list
print(list(map(square, [1,2,3,4,5])))  # [1, 4, 9, 16, 25]

# Manual currying: transform f(a,b) into g(a)(b)
def curry(f):
    def curried(a):
        def inner(b):
            return f(a, b)
        return inner
    return curried

add = curry(lambda a, b: a + b)
add5 = add(5)        # returns a function
print(add5(3))       # 8
print(add5(10))      # 15

# Haskell (every function is automatically curried):
# add :: Int -> Int -> Int
# add x y = x + y
# add5 = add 5          -- add5 :: Int -> Int
# map add5 [1,2,3]      -- [6, 7, 8]

A pure function satisfies exactly two conditions:

1. Deterministic: Given the same inputs, it always returns the same output.
2. No side effects: It does not modify any external state — no modifying global variables, no I/O, no mutating its arguments, no random numbers, no reading from a database.

Referential transparency is the property that follows: a call to a pure function can be replaced by its return value without changing the meaning of the program. If f(3) = 9, then wherever f(3) appears, you can substitute 9 and the program behaves identically.

Why does this matter so much?

• Testability: A pure function is trivially testable — you only need to check input/output pairs. No setup, no teardown, no mocks.
• Equational reasoning: You can reason about pure functions like algebraic equations. This is how Haskell's type system and GHC's optimizer work.
• Parallelism: Two calls to a pure function have no shared mutable state, so they can always run in parallel safely. This is why functional code can be parallelized more aggressively.
• Caching (memoization): If a function is referentially transparent, it's safe to cache its results — calling it again with the same arguments is guaranteed to give the same answer.

Impure functions (those with side effects) are not evil — you need I/O to do anything useful. The functional discipline is to separate pure computation from effects: do the pure computation in pure functions, and isolate the effects at the boundaries. Haskell enforces this separation with the type system (IO monad). Languages like Python leave it to the programmer's discipline.

# PURE function: deterministic, no side effects
def add(a, b):
    return a + b           # same inputs -> always same output

# This is referentially transparent:
# result = add(3, 4) + add(3, 4)
# is IDENTICAL to:
# result = 7 + 7

# IMPURE function examples:
import random

def impure_1(x):           # reads external state
    return x + random.random()  # different result each call!

global_count = 0
def impure_2(x):           # mutates external state (side effect)
    global global_count
    global_count += 1
    return x * 2

def impure_3(lst):
    lst.append(99)         # mutates its argument!
    return lst

# SAFE: return a new list instead of mutating
def pure_append(lst, val):
    return lst + [val]     # creates a new list, does not touch lst

# Memoization is only correct for pure functions:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # pure recursion; safe to cache

print(fib(100))  # instant due to caching

Immutability means that once a data structure is created, it cannot be changed. Instead of modifying an existing value, you create a new value that incorporates the desired change.

Why immutability? Mutable state is the #1 source of bugs in concurrent programs and a major source of bugs in sequential programs. When an object can change at any time, reasoning about its value at a particular point in execution requires tracking every possible mutation. Immutable data is much simpler: a value is what it was when you created it, forever.

Connection to pure functions: Immutability and pure functions reinforce each other. A pure function cannot mutate its inputs (that would be a side effect). If all data is immutable, there is nothing to mutate accidentally.

"Persistent data structures" are immutable data structures designed to be efficient: instead of copying the entire structure on each change, they share unchanged parts between the old and new version. A persistent linked list can share its tail; a persistent binary tree can share unchanged subtrees. Clojure's core data structures (lists, vectors, maps, sets) are all persistent. This is how you can have immutability without O(n) cost on every update.

In Python: tuples are immutable sequences; strings are immutable; frozenset is an immutable set. Idiomatic functional Python avoids mutating lists in-place (.append, .sort) and prefers creating new lists via comprehensions or map/filter.

In Haskell: everything is immutable by default. There are no assignment statements in the usual sense — you only bind names to values. Mutation requires explicit IO or ST monads.

Real-world impact: React's virtual DOM diffing, Redux's state management, and Git's object model are all built on immutable data structures. Git's commits are immutable snapshots; each commit points to the previous one. You never modify a commit — you create a new one.

# Python: prefer creating new data over mutating

# Mutable (imperative) style -- risky in concurrent code
def add_tax_mutable(prices, tax_rate):
    for i in range(len(prices)):
        prices[i] *= (1 + tax_rate)   # mutates the input list!
    return prices

# Immutable (functional) style -- safe, pure
def add_tax_pure(prices, tax_rate):
    return [p * (1 + tax_rate) for p in prices]  # new list

original = [10.0, 20.0, 30.0]
taxed = add_tax_pure(original, 0.1)
print(original)  # [10.0, 20.0, 30.0]  -- unchanged!
print(taxed)     # [11.0, 22.0, 33.0]

# Named tuples as immutable records
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
# p.x = 5  # AttributeError: can't set attribute

# "Update" by creating a new point
p2 = p._replace(x=5)  # new Point(5, 4), p is unchanged

# Haskell: updating a record creates a new value
# data Point = Point { x :: Int, y :: Int }
# p = Point 3 4
# p2 = p { x = 5 }   -- new record; p still Point 3 4

Function composition is the mathematical operation of chaining functions: (g ∘ f)(x) = g(f(x)). The output of f becomes the input of g. In pure functional programming, composition is the primary mechanism for building complex behavior out of simple pieces.

Why composition? In object-oriented programming, you build complexity by inheriting and combining objects. In functional programming, you build complexity by composing functions. The principle is the same — modularity and reuse — but the mechanism is different and often more flexible.

The Unix pipeline analogy: cat file.txt | grep 'error' | sort | uniq -c | sort -rn is function composition: the output of each command is piped as input to the next. Each command is a pure transformation on a stream of text. This composability is why Unix tools are so powerful.

In Haskell, (.) is the composition operator: (f . g) x = f (g x). Programs can be written as a pipeline of composed functions, with no explicit mention of the data being transformed (this is called point-free style).

Compose vs. Pipe: Mathematically, composition applies right-to-left: (f ∘ g)(x) = f(g(x)) applies g first. Many functional utilities (Ramda.js, Haskell's <<<) follow this convention. Pipe applies left-to-right: pipe(g, f)(x) = f(g(x)). Both are equally valid; pipe is often more readable for humans.

# Function composition in Python

def compose(*fns):
    """Right-to-left composition: compose(f, g)(x) = f(g(x))"""
    from functools import reduce
    return reduce(lambda f, g: lambda x: f(g(x)), fns)

def pipe(*fns):
    """Left-to-right: pipe(g, f)(x) = f(g(x))"""
    from functools import reduce
    return reduce(lambda f, g: lambda x: g(f(x)), fns)

double  = lambda x: x * 2
add_one = lambda x: x + 1
square  = lambda x: x ** 2

# pipe: apply left to right
transform = pipe(double, add_one, square)
print(transform(3))  # square(add_one(double(3))) = square(7) = 49

# Haskell point-free style:
# double   = (*2)
# addOne   = (+1)
# square   = (^2)
# transform = square . addOne . double   -- right to left
# transform 3  -- 49

# Real-world: data processing pipeline
words = ["  Hello  ", "WORLD", "foo", "BAR  "]

normalize = pipe(
    str.strip,
    str.lower,
    lambda s: s.capitalize()
)

result = list(map(normalize, words))
print(result)  # ['Hello', 'World', 'Foo', 'Bar']

Everything in this module rests on a foundation built by Alonzo Church in 1936: the lambda calculus. Understanding it — even informally — demystifies why functional programming works the way it does.

The lambda calculus has only three constructs:

1. Variable: x — a name
2. Abstraction (lambda): λx. body — a function that takes x and returns body
3. Application: (f arg) — apply function f to argument arg

That is the entire language. No numbers, no booleans, no lists — yet Church showed this is computationally equivalent to a Turing machine. Everything can be encoded:

• Boolean true: λt. λf. t (a function that takes two things and returns the first)
• Boolean false: λt. λf. f
• The number zero: λf. λx. x (apply f zero times to x)
• The number n: λf. λx. f(f(f(...f(x)...))) (apply f n times)

What this means for programming: The lambda keyword in Python and JavaScript is literally this — an anonymous function literal, a lambda abstraction. The → in Haskell's type signatures reflects the curried, lambda-calculus nature of all functions. The reason higher-order functions are so natural in functional languages is that the underlying model is the lambda calculus, in which functions are the only primitive concept.

Beta reduction is the computational rule: (λx. body) arg reduces to body[x := arg] (substitute arg for x in body). This is what a function call is, mathematically. The entire execution of a pure functional program is just repeated beta reduction.

# Lambda calculus encodings demonstrated in Python

# Church booleans
TRUE  = lambda t: lambda f: t   # choose first
FALSE = lambda t: lambda f: f   # choose second

# IF: if condition then a else b
IF = lambda cond: lambda a: lambda b: cond(a)(b)

print(IF(TRUE)("yes")("no"))   # yes
print(IF(FALSE)("yes")("no"))  # no

# Church AND
AND = lambda p: lambda q: p(q)(p)  # if p then q else p
print(IF(AND(TRUE)(TRUE))("both true")("not both"))   # both true
print(IF(AND(TRUE)(FALSE))("both true")("not both"))  # not both

# Church numerals (first three)
ZERO = lambda f: lambda x: x          # apply f 0 times
ONE  = lambda f: lambda x: f(x)       # apply f 1 time
TWO  = lambda f: lambda x: f(f(x))    # apply f 2 times

# Convert Church numeral to Python int
to_int = lambda n: n(lambda x: x + 1)(0)
print(to_int(ZERO), to_int(ONE), to_int(TWO))  # 0 1 2

# SUCC (successor): add 1 to a Church numeral
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))
THREE = SUCC(TWO)
print(to_int(THREE))  # 3