4 min read
On this page

Functional Programming

Functional programming treats computation as the evaluation of mathematical functions. It emphasizes immutability, pure functions, and function composition — avoiding mutable state and side effects.

Core Concepts

Pure Functions

A function is pure if:

  1. Its output depends only on its inputs (deterministic).
  2. It has no side effects (doesn't modify external state, I/O, etc.).
// Pure
FUNCTION ADD(a, b)  RETURN a + b

// Impure (reads global state)
GLOBAL COUNTER ← 0
FUNCTION GET_COUNT()  RETURN COUNTER

// Impure (side effect: I/O)
PROCEDURE GREET(name)  PRINT "Hello, ", name

Benefits of purity:

  • Referential transparency: Can replace a function call with its result. Enables equational reasoning.
  • Testability: No setup/teardown needed. Same input → same output.
  • Parallelism: No shared mutable state → safe to run in parallel.
  • Caching/memoization: Safe to cache results (same input always gives same output).

Immutability

Data, once created, is never modified. Instead, create new data with changes.

x ← [1, 2, 3]
y ← MAP(x, v -> v + 1)   // new list [2, 3, 4]
// x is unchanged

Persistent data structures: Immutable data structures that efficiently share structure between versions (covered below).

First-Class Functions

Functions are values — they can be stored in variables, passed as arguments, and returned from other functions.

double ← FUNCTION(x) RETURN x * 2
result ← double(5)   // 10

FUNCTION APPLY(f, x)  RETURN f(x)
result ← APPLY(double, 5)   // 10

Higher-Order Functions

Functions that take functions as arguments or return functions.

// Takes a function
FUNCTION MAP(arr, f)
    RETURN [f(x) FOR EACH x IN arr]

// Returns a function
FUNCTION ADDER(n)
    RETURN FUNCTION(x) RETURN x + n

add5 ← ADDER(5)
add5(3)   // 8

Closures

Functions that capture variables from their enclosing scope.

multiplier ← 3
triple ← FUNCTION(x) RETURN x * multiplier   // captures `multiplier`
triple(5)   // 15

Closure types in Rust:

  • Fn: Borrows captured variables immutably. Can be called multiple times.
  • FnMut: Borrows mutably. Can be called multiple times.
  • FnOnce: Takes ownership. Can be called once.

Currying and Partial Application

Currying: Transform a function of n arguments into n functions of 1 argument each.

f(a, b, c) → f(a)(b)(c)

Partial application: Fix some arguments, producing a function of the remaining arguments.

FUNCTION ADD(a, b)  RETURN a + b
add5 ← FUNCTION(b) RETURN ADD(5, b)   // partial application
add5(3)   // 8

Map, Filter, Reduce

The three fundamental higher-order functions for data transformation.

Map

Apply a function to each element, producing a new collection.

nums ← [1, 2, 3, 4, 5]
doubled ← MAP(nums, x -> x * 2)
// [2, 4, 6, 8, 10]

Filter

Keep elements satisfying a predicate.

evens ← FILTER(nums, x -> x MOD 2 = 0)
// [2, 4]

Reduce (Fold)

Combine all elements into a single value using an accumulator.

sum ← FOLD(nums, 0, (acc, x) -> acc + x)
// 15
product ← FOLD(nums, 1, (acc, x) -> acc * x)
// 120

Pipeline Style

Chain operations for readable data transformations:

result ← [1..100]
    |> FILTER(x -> x MOD 3 = 0)   // multiples of 3
    |> MAP(x -> x * x)            // square them
    |> TAKE(5)                     // first 5
    |> SUM()                       // sum them
// 9 + 36 + 81 + 144 + 225 = 495

Algebraic Data Types (ADTs)

Product Types (AND)

Combine multiple values: structs, tuples.

RECORD Point { x: number, y: number }     // named fields
TYPE Pair = (integer, string)              // tuple

Sum Types (OR)

A value is one of several variants: enums.

TYPE Shape =
    Circle(radius)
  | Rectangle(width, height)
  | Triangle(side_a, side_b, side_c)

FUNCTION AREA(shape)
    MATCH shape
        Circle(r):          RETURN PI * r * r
        Rectangle(w, h):    RETURN w * h
        Triangle(a, b, c):
            s ← (a + b + c) / 2
            RETURN SQRT(s * (s - a) * (s - b) * (s - c))

Pattern Matching

Destructure ADTs and branch on their structure.

FUNCTION DESCRIBE(opt)
    MATCH opt
        Some(0):              RETURN "zero"
        Some(n) WHERE n > 0:  RETURN "positive: " + n
        Some(n):              RETURN "negative: " + n
        None:                 RETURN "nothing"

Pattern matching is exhaustive — the compiler ensures all variants are handled.

Recursion Schemes

Catamorphism (Fold)

Recursively collapse a data structure into a value. The most common recursion scheme.

TYPE List = Nil | Cons(head, tail: List)

FUNCTION FOLD(list, init, f)
    MATCH list
        Nil:              RETURN init
        Cons(head, tail):
            acc ← f(init, head)
            RETURN FOLD(tail, acc, f)

Anamorphism (Unfold)

Build a data structure from a seed value.

FUNCTION UNFOLD(seed, f)
    result ← empty list
    state ← seed
    WHILE f(state) ≠ None
        (value, next_state) ← f(state)
        APPEND value TO result
        state ← next_state
    RETURN result

// Generate Fibonacci numbers
fibs ← UNFOLD((0, 1), (a, b) ->
    IF a > 1000 THEN None ELSE Some(a, (b, a + b)))

Hylomorphism

An anamorphism followed by a catamorphism — build up then tear down. Often the intermediate structure can be fused away (deforestation).

Monads

Monads abstract sequential computation with context (effects, failure, state, I/O).

Option / Maybe Monad

Computation that might fail.

FUNCTION PARSE_AND_ADD(a, b)
    x ← PARSE_INT(a)   // returns None on failure (monadic bind)
    IF x = None THEN RETURN None
    y ← PARSE_INT(b)
    IF y = None THEN RETURN None
    RETURN Some(x + y)

Result Monad

Computation that might fail with an error value.

FUNCTION READ_CONFIG(path)
    content ← READ_FILE(path)         // propagate error if fails
    IF content is Error THEN RETURN content
    config ← PARSE_JSON(content)      // propagate error if fails
    IF config is Error THEN RETURN config
    RETURN Ok(config)

Monad Laws

For a monad M with unit (wrapping) and bind (chaining):

  1. Left identity: unit(a).bind(f) == f(a)
  2. Right identity: m.bind(unit) == m
  3. Associativity: m.bind(f).bind(g) == m.bind(|x| f(x).bind(g))

Other Monads

  • IO Monad: Sequence I/O operations purely (Haskell).
  • State Monad: Thread state through computation.
  • Reader Monad: Read from a shared environment.
  • Writer Monad: Accumulate output (logging).
  • List Monad: Non-deterministic computation.

Functors and Applicatives

Functor: Has map. Transforms the value inside a context.

// Option is a functor
x ← Some(5)
y ← MAP(x, v -> v * 2)   // Some(10)

Applicative: Has map + ability to apply wrapped functions to wrapped values.

Monad: Has map + flat_map (bind). Can use the result of one computation to decide the next.

Hierarchy: Functor ⊂ Applicative ⊂ Monad.

Lazy Evaluation

Eager (strict): Arguments evaluated before function call (Rust, most languages).

Lazy: Arguments evaluated only when needed (Haskell).

// Iterators are lazy
iter ← [0, 1, 2, ...] |> MAP(x -> x * x) |> FILTER(x -> x MOD 2 = 0)
// Nothing computed yet! Only when consumed:
first_5 ← TAKE(iter, 5) |> COLLECT()

Benefits: Work with infinite data structures. Avoid unnecessary computation. Enable certain optimizations (short-circuit evaluation).

Drawbacks: Unpredictable memory usage (thunks accumulate). Hard to reason about performance. Space leaks.

Referential Transparency

An expression is referentially transparent if it can be replaced by its value without changing program behavior.

// Referentially transparent:
x ← 2 + 3          // can replace with 5 everywhere
y ← ADD(2, 3)      // if ADD is pure, can replace with 5

// NOT referentially transparent:
x ← READ_LINE()    // depends on external input

Referential transparency enables equational reasoning, compiler optimizations, and safe parallelism.

Functional Languages

| Language | Year | Key Features | |---|---|---| | Lisp (1958) | First functional language. Homoiconic (code = data). Macros. | | ML (1973) | Type inference (Hindley-Milner). Pattern matching. | | Haskell (1990) | Pure. Lazy. Type classes. Monads. | | OCaml (1996) | Strict ML. Fast native compilation. | | Erlang (1986) | Concurrent functional. Actor model. | | Elixir (2011) | Modern syntax on Erlang VM (BEAM). | | Scala (2004) | FP + OOP on JVM. | | F# (2005) | FP on .NET. | | Clojure (2007) | Lisp on JVM. Persistent data structures. | | Rust (2015) | Multi-paradigm with strong FP support (closures, iterators, pattern matching, ADTs). |

Applications in CS

  • Data processing: Map-reduce pipelines, stream processing (filter/map/fold chains).
  • Concurrency: Immutability eliminates data races. Actor model (Erlang/Elixir). STM (Software Transactional Memory).
  • Compiler construction: AST transformations, type checking, optimization passes are naturally functional.
  • Distributed systems: Stateless functions are easier to distribute, retry, and cache.
  • React/Redux: UI as a pure function of state. Reducers are fold operations.
  • Machine learning: Pure mathematical functions. Automatic differentiation works on pure computations.
  • Testing: Pure functions are trivially testable. Property-based testing (QuickCheck) leverages FP.