language: en kae3g ← back to index

kae3g 9520: Functional Programming - Computing with Pure Functions

Phase 1: Foundations & Philosophy | Week 2 | Reading Time: 16 minutes

What You'll Learn

Prerequisites

What Is Functional Programming?

The simple definition:

Functional programming treats computation as the evaluation of mathematical functions and avoids changing state and mutable data.

Unpacking:

The shift:

Imperative: "Do this, then do that, then do this other thing"
            (recipe—list of steps)

Functional: "The answer is f(g(h(input)))"
            (equation—composition of functions)

Pure Functions: The Foundation

A pure function:

  1. Same input → same output (deterministic, no randomness)
  2. No side effects (doesn't change anything outside itself)

Examples

Pure:

(defn add [x y]
  (+ x y))

(add 3 5)  ; => 8
(add 3 5)  ; => 8 (always!)

Impure (side effect: printing):

(defn add-and-log [x y]
  (println "Adding" x "and" y)  ; SIDE EFFECT!
  (+ x y))

(add-and-log 3 5)  
; Prints: "Adding 3 and 5"
; => 8

Impure (side effect: mutation):

let total = 0;

function addToTotal(x) {
  total = total + x;  // SIDE EFFECT: mutates global
  return total;
}

addToTotal(5)  ; => 5
addToTotal(5)  ; => 10 (different output for same input!)

Why Purity Matters

Benefits of pure functions:

  1. Easy to test
    ;; Pure function: just call it
(add 3 5)  ; => 8 (test passed!)

;; Impure function: must set up state, mock I/O, etc.
  2. Easy to reason about
    ;; What does this do?
(defn mystery [x] (* x x))

;; Just look at the code: squares its input
;; No need to check global variables, database state, etc.
  3. Parallel-safe
    ;; Call these in parallel—no race conditions!
(future (add 1 2))
(future (add 3 4))
(future (add 5 6))
  4. Memoizable (cache results)
    ;; Since (expensive-calc 42) always returns same value,
;; compute once, cache forever
(def expensive-calc (memoize expensive-calc))
  5. Time-travel debugging
    ;; Replay with same inputs → same outputs (reproducible bugs!)

Immutability: Values That Never Change

Most languages: Variables vary.

x = [1, 2, 3]
x.append(4)  # Mutated!
# x is now [1, 2, 3, 4]

FP languages: Values are immutable.

(def x [1 2 3])
(def y (conj x 4))  ; New value

x  ; => [1 2 3] (unchanged!)
y  ; => [1 2 3 4] (new value)

Why Immutability Prevents Bugs

The problem with mutation:

function processUsers(users) {
  users.sort((a, b) => a.age - b.age);  // MUTATES input!
  return users.filter(u => u.age > 18);
}

const allUsers = [{name: "Alice", age: 30}, {name: "Bob", age: 17}];
const adults = processUsers(allUsers);

// allUsers is now SORTED (side effect!)
// Other code expecting original order: BROKEN

With immutability:

(defn process-users [users]
  (->> users
       (sort-by :age)
       (filter #(> (:age %) 18))))

(def all-users [{:name "Alice" :age 30} {:name "Bob" :age 17}])
(def adults (process-users all-users))

;; all-users is UNCHANGED (no side effect)
;; Other code: SAFE

Immutability = no spooky action at a distance.

Higher-Order Functions

Functions that take functions as arguments or return functions as results.

Map: Transform Each Element

(map inc [1 2 3 4 5])
; => (2 3 4 5 6)

(map square [1 2 3 4 5])
; => (1 4 9 16 25)

(map :name [{:name "Alice"} {:name "Bob"}])
; => ("Alice" "Bob")

map is a higher-order function (takes function inc, square, :name as argument).

Filter: Keep Some Elements

(filter even? [1 2 3 4 5 6])
; => (2 4 6)

(filter #(> % 10) [5 15 3 20 7 30])
; => (15 20 30)

filter is higher-order (takes predicate function as argument).

Reduce: Combine Elements

(reduce + [1 2 3 4 5])
; => 15  (1+2+3+4+5)

(reduce * [1 2 3 4 5])
; => 120 (1*2*3*4*5 = 5 factorial)

(reduce (fn [acc x] (conj acc (* x x))) [] [1 2 3 4 5])
; => [1 4 9 16 25]  (build vector of squares)

reduce is the most powerful (can implement map, filter, and more using reduce!).

Returning Functions (Closures)

(defn make-multiplier [factor]
  (fn [x] (* x factor)))  ; Returns a function!

(def times-10 (make-multiplier 10))
(def times-100 (make-multiplier 100))

(times-10 5)   ; => 50
(times-100 5)  ; => 500

The returned function "closes over" factor (remembers it). This is a closure.

Composition: The Heart of FP

Mathematical composition:

f(x) = x + 1
g(x) = x * 2

(g ∘ f)(x) = g(f(x)) = (x + 1) * 2

Functional programming:

(defn f [x] (+ x 1))
(defn g [x] (* x 2))

(defn g-of-f [x]
  (g (f x)))

(g-of-f 5)  ; => 12  (5+1=6, 6*2=12)

Using comp (composition function):

(def g-of-f (comp g f))

(g-of-f 5)  ; => 12

Or threading macros:

(-> 5
    f    ; 6
    g)   ; 12

Same idea as Unix pipes: Data flows through transformations.

Declarative vs Imperative

Imperative (HOW to do it)

// Sum of squares of even numbers
let sum = 0;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] % 2 === 0) {
    sum += arr[i] * arr[i];
  }
}

Steps: Initialize sum, loop, check condition, update sum.

Declarative (WHAT you want)

(->> arr
     (filter even?)
     (map #(* % %))
     (reduce +))

Transformation pipeline: Filter evens → square each → sum.

Benefits of declarative:

Why FP Is Winning

1. Concurrency

Mutable state + threads = race conditions:

# Two threads incrementing counter
counter = 0

def increment():
    global counter
    counter = counter + 1  # NOT ATOMIC!

# Thread 1: read 0, add 1, write 1
# Thread 2: read 0, add 1, write 1  (race!)
# Result: 1 (should be 2)

Fix: Locks (complex, slow, deadlock-prone).

FP approach: Immutable data

;; No mutation → no race conditions
(defn increment [counter]
  (+ counter 1))

;; Call from any thread—safe!

For actual shared state: Clojure's atoms (compare-and-swap, lock-free).

2. Testability

Pure functions are trivial to test:

(defn add [x y] (+ x y))

;; Test:
(assert (= (add 2 3) 5))
(assert (= (add 0 0) 0))
(assert (= (add -1 1) 0))

;; No setup, no mocking, no teardown

Impure functions:

function saveUser(user) {
  database.insert(user);  // Side effect!
  sendEmail(user.email);  // Side effect!
  logAudit(user.id);      // Side effect!
}

// Test: Mock database, email service, logger...
// Complex, fragile, slow

3. Reasoning

Pure functions are equations:

(defn total [prices]
  (reduce + prices))

;; You can reason algebraically:
(total []) = 0  (identity)
(total [a]) = a
(total [a b]) = a + b (associative, commutative)

Impure functions: Must trace through execution, track state, consider order.

FP Concepts in Other Languages

FP isn't Clojure-only. It's spreading:

JavaScript (Functional Style)

// Imperative
let doubled = [];
for (let i = 0; i < arr.length; i++) {
  doubled.push(arr[i] * 2);
}

// Functional
const doubled = arr.map(x => x * 2);

ES6+ embraced FP: map, filter, reduce, arrow functions, const/let.

Python (Functional Tools)

# map, filter, reduce
from functools import reduce

nums = [1, 2, 3, 4, 5]
doubled = list(map(lambda x: x * 2, nums))
evens = list(filter(lambda x: x % 2 == 0, nums))
total = reduce(lambda acc, x: acc + x, nums)

Or comprehensions (functional in spirit):

doubled = [x * 2 for x in nums]
evens = [x for x in nums if x % 2 == 0]

Rust (FP + Safety)

let nums = vec![1, 2, 3, 4, 5];

let doubled: Vec<_> = nums.iter()
    .map(|x| x * 2)
    .collect();

let total: i32 = nums.iter().sum();

Rust combines FP (immutability, composition) with systems programming (no GC, memory safety).

Hands-On: FP Practice

Exercise 1: Refactor to Pure

Given (impure):

let total = 0;

function addToTotal(x) {
  total += x;
  return total;
}

Refactor (pure):

function add(total, x) {
  return total + x;
}

// Call site manages state
let total = 0;
total = add(total, 5);
total = add(total, 3);

Or with reduce:

const total = [5, 3, 7].reduce(add, 0);

Exercise 2: Composition

Build a pipeline:

;; Given: list of numbers
;; Want: sum of squares of even numbers

;; Step 1: Filter evens
(filter even? [1 2 3 4 5 6])  ; => (2 4 6)

;; Step 2: Square each
(map #(* % %) [2 4 6])  ; => (4 16 36)

;; Step 3: Sum
(reduce + [4 16 36])  ; => 56

;; Compose:
(->> [1 2 3 4 5 6]
     (filter even?)
     (map #(* % %))
     (reduce +))  ; => 56

Try: Sum of cubes of odd numbers in [1..10].

Exercise 3: Higher-Order Function

Write your own map:

(defn my-map [f coll]
  (if (empty? coll)
    '()
    (cons (f (first coll))
          (my-map f (rest coll)))))

(my-map inc [1 2 3])  ; => (2 3 4)
(my-map square [1 2 3])  ; => (1 4 9)

Recursive definition:

This is how map is actually defined (conceptually—optimized in practice).

Common FP Patterns

1. Map-Reduce

Pattern: Transform each item (map), then combine (reduce).

;; Total price of items
(def items [{:name "Widget" :price 10}
            {:name "Gadget" :price 20}
            {:name "Gizmo" :price 15}])

(->> items
     (map :price)   ; Extract prices: (10 20 15)
     (reduce +))    ; Sum: 45

Scales to distributed computing (MapReduce, Hadoop, Spark—same pattern!).

2. Pipeline (Threading)

Pattern: Data flows through transformations.

(-> data
    parse       ; data → parsed
    validate    ; parsed → validated
    transform   ; validated → transformed
    save)       ; transformed → saved

Each step returns new data. No mutation.

Like Unix pipes, but for data structures.

3. Currying (Partial Application)

Currying: Convert f(x, y) to f(x)(y).

;; Normal function
(defn add [x y] (+ x y))
(add 10 5)  ; => 15

;; Partial application (fix first argument)
(def add10 (partial add 10))
(add10 5)  ; => 15
(add10 20) ; => 30

Useful for creating specialized functions from general ones:

(def log-error (partial log :error))
(def log-info (partial log :info))

(log-error "Something broke")  ; Same as: (log :error "Something broke")

FP and Mathematics

Lambda Calculus (Alonzo Church, 1930s)

The mathematical foundation of FP:

λx. x + 1        ; Function taking x, returning x+1
(λx. x + 1) 5    ; Apply to 5 → 6

All computable functions can be expressed in lambda calculus (Church-Turing thesis).

Modern FP languages are lambda calculus + practical features (types, I/O, performance).

Category Theory

Composition in category theory:

Objects: Types (Integer, String, User)
Morphisms: Functions (Integer → String)
Composition: f: A → B, g: B → C ⇒ g ∘ f: A → C

Laws:

FP respects these laws:

;; Associativity
(comp h (comp g f)) ≡ (comp (comp h g) f) ≡ (comp h g f)

;; Identity
(comp identity f) ≡ (comp f identity) ≡ f

We'll explore this deeply in Essay 9730: Category Theory for Programmers.

FP vs OOP

The eternal debate: Functional vs Object-Oriented Programming.

OOP Approach

class User {
  private String name;
  private int age;
  
  public User(String name, int age) {
    this.name = name;
    this.age = age;
  }
  
  public void haveBirthday() {
    this.age += 1;  // Mutation!
  }
  
  public boolean isAdult() {
    return this.age >= 18;
  }
}

User alice = new User("Alice", 17);
alice.haveBirthday();  // Mutated!

OOP bundles:

FP Approach

;; Just data
(def alice {:name "Alice" :age 17})

;; Functions on data
(defn have-birthday [user]
  (update user :age inc))

(defn adult? [user]
  (>= (:age user) 18))

;; Use:
(def older-alice (have-birthday alice))
(adult? older-alice)  ; => true

;; Original unchanged:
alice  ; => {:name "Alice", :age 17}

FP separates:

Which Is Better?

It depends.

OOP strengths:

FP strengths:

Modern synthesis: Use both!

Clojure's approach: FP by default, OOP when needed (protocols, records).

Try This

Exercise 1: Refactor to Immutable

Imperative (mutation):

function updateUsers(users) {
  for (let user of users) {
    user.lastSeen = Date.now();
  }
  return users;
}

Functional (immutable):

(defn update-users [users]
  (map #(assoc % :last-seen (now)) users))

Benefits:

Exercise 2: Build with Higher-Order Functions

Problem: Given list of numbers, return list of those that are perfect squares.

Imperative:

result = []
for n in nums:
    if int(n ** 0.5) ** 2 == n:
        result.append(n)

Functional:

(defn perfect-square? [n]
  (let [root (Math/sqrt n)]
    (= n (* root root))))

(filter perfect-square? nums)

One line! (Plus the helper function.)

Exercise 3: Compose Complex Behavior

Problem: Process a list of users:

  1. Filter active users
  2. Extract names
  3. Sort alphabetically
  4. Take first 10
  5. Join with commas

Functional composition:

(->> users
     (filter :active?)
     (map :name)
     (sort)
     (take 10)
     (clojure.string/join ", "))

Five transformations, one pipeline. Clear, testable, composable.

Going Deeper

Related Essays

External Resources

For the Mathematically Curious

Reflection Questions

  1. Can all programs be pure? (No—I/O is inherently impure. But you can isolate impurity.)
  2. Is immutability too expensive? (Persistent data structures make it O(log n), not O(n))
  3. Why isn't FP more popular? (Unfamiliar, steeper learning curve—but gaining adoption)
  4. When should you use mutation? (Performance hotspots, interfacing with mutable APIs—but minimize)
  5. Is OOP dead? (No—but FP ideas are infiltrating OOP languages)

Summary

Functional Programming:

Key Insights:

Benefits:

Trade-offs:

In the Valley:

Next: We'll explore Rich Hickey's "Simple Made Easy" in depth—the philosophy underlying both Clojure and the valley itself.

Navigation:
← Previous: 9516 (complete stack in action) | Phase 1 Index | Next: 9530 (rich hickey simple made easy)

Bridge to Narrative: For FP storytelling, see 9949 (The Wise Elders) - Clojure as the Functional Sage!

Metadata:

Copyright © 2025 kae3g | Dual-licensed under Apache-2.0 / MIT
Competitive technology in service of clarity and beauty

← back to index