Immutability and Pure Functions

Immutability and pure functions are the twin pillars on which the whole functional paradigm rests. Higher-order functions, composition, lazy evaluation and safe parallelism are all consequences of these two ideas; remove them and functional programming collapses back into ordinary imperative code with extra brackets. A pure function is one whose output depends only on its inputs and which has no observable effect on the outside world. Immutability is the discipline that, once a value is created, it can never be altered — only superseded by a new value. Held together, the two give you referential transparency: the licence to reason about a program by substituting expressions for their values, exactly as you do in school algebra.

This lesson defines both properties rigorously, traces Haskell evaluations that show why purity permits substitution, contrasts mutable and immutable models on a realistic record-update task, and weighs the genuine costs (memory, allocation) against the benefits (testability, concurrency, optimisation). The pay-off is the conceptual machinery you will lean on in every later lesson and in the big-data section of the course.

---

Spec Mapping

This lesson addresses AQA 7517 §4.12.1, the characteristics of the functional paradigm, with specific focus on pure functions, the absence of side effects, referential transparency, and immutable data. You should be able to: define a pure function and state its two defining properties; identify whether a given function is pure or impure and justify the classification; explain referential transparency and demonstrate substitution on a worked example; define immutability and explain how functional languages model "change" without mutation; and argue the benefits of these properties for testing, reasoning and concurrency (the last linking forward to big data in §4.11). The material draws on the paradigm-comparison ideas of §4.12.1 and underpins the list-processing functions of §4.12.3.

AQA's specification is a list of assessable points; the wording and examples here are our own and are not a verbatim reproduction of any board text.

---

Pure Functions — the Two Properties

A function is pure if it satisfies both of the following:

1. Determinism (same input ⇒ same output). Calling it with the same arguments always yields the same result, no matter when or how often it is called. It may not consult any value that can vary between calls — no global mutable state, no system clock, no random-number source, no file or network read.
2. Freedom from side effects. Its only effect is to compute and return a value. It does not modify external state, mutate its arguments, perform input/output, or otherwise leave any trace on the world beyond the value it returns.

A side effect is any observable interaction with the world outside the simple input-to-output mapping. The catalogue you must be able to recite is:

• modifying a global or any state outside the function;
• mutating an argument passed in (e.g. appending to a caller's list);
• reading from or writing to a file, database, network or screen;
• reading a non-deterministic source such as the clock or a random generator.

Pure functions in Haskell

-- Pure: result depends only on x and y; nothing else changes
add :: Int -> Int -> Int
add x y = x + y

-- Pure: deterministic, no side effects
square :: Int -> Int
square x = x * x

-- Pure: a list "transformation" that builds a NEW list
incrementAll :: [Int] -> [Int]
incrementAll = map (+1)

In Haskell purity is not a matter of discipline you must remember to apply — the language enforces it. There is no syntax for reassigning a binding and no way to perform I/O outside the special IO type, so an ordinary function such as add is pure by construction. That is precisely why Haskell is used to teach the paradigm: you cannot accidentally write an impure function and not notice.

Impure functions (Python, for contrast)

# Impure #1: depends on AND mutates external state -> not deterministic
counter = 0
def increment():
    global counter
    counter += 1          # mutates a global
    return counter        # returns 1, then 2, then 3... for the SAME (no) input

# Impure #2: reads a non-deterministic source
import random
def roll():
    return random.randint(1, 6)   # different result each call

# Impure #3: performs I/O (a side effect)
def greet(name):
    print(f"Hello, {name}!")      # writes to the screen
    return name

# Impure #4: mutates its argument
def add_item(lst, item):
    lst.append(item)              # the CALLER's list is changed
    return lst

Each of the four is impure for a different reason, and being able to name the reason — "it mutates a global", "it reads the clock", "it does I/O", "it mutates an argument" — is what earns the marks. greet is a subtle case worth dwelling on: it looks harmless because it also returns name, but the print is an irreversible interaction with the outside world, so the function is impure regardless of its return value.

Pure vs impure — summary

Property	Pure function	Impure function
Same inputs → same output	Always	Not guaranteed
Modifies external state	Never	May do so
Mutates its arguments	Never	May do so
Performs I/O	Never	May do so
Reads clock / RNG / globals	Never	May do so
Easy to test in isolation	Yes — apply input, assert output	Often needs mocks / fixtures
Safe for parallel execution	Yes	Requires synchronisation

---

Referential Transparency — Traced

Referential transparency is the property that an expression can be replaced by its value anywhere it appears without changing the program's meaning. It is the formal pay-off of purity: because a pure call always denotes the same value, that value can stand in for the call. Consider:

square :: Int -> Int
square x = x * x

result = square 4 + square 4

Because square is pure, square 4 is always 16, so we may substitute step by step:

  square 4 + square 4
= 16 + square 4        -- replace the first occurrence by its value
= 16 + 16              -- replace the second occurrence by its value
= 32

This is not just a tidy way to evaluate by hand — it licenses a real compiler optimisation called common sub-expression elimination: the runtime may compute square 4 once and reuse it, certain that the second call cannot differ. Now contrast an impure expression:

import random
x = random.random() + random.random()   # the two calls give DIFFERENT values

You cannot replace random.random() by "its value", because it has no single value. The substitution that worked for square is invalid here, which is exactly why impure expressions resist the equational reasoning that makes functional programs easier to analyse, refactor and prove correct. Every pure function is referentially transparent; no impure one is.

---

Immutability — Once Created, Never Changed

Immutability means a value, once constructed, cannot be altered. There is no operation that reaches into an existing structure and overwrites part of it. To model change, you build a new value that incorporates the difference, leaving the original intact.

Mutable (imperative) — the original is overwritten

numbers = [1, 2, 3]
numbers.append(4)       # the SAME list object now ends in 4
numbers[0] = 10         # the SAME list object is changed again
# numbers is now [10, 2, 3, 4]; the old value [1, 2, 3] is gone

Immutable (functional) — a new value is produced

-- Haskell: every value is immutable. To "prepend" you build a new list.
original = [1, 2, 3]
modified = 0 : original    -- [0, 1, 2, 3]
-- 'original' is STILL [1, 2, 3] — it was never touched

A binding such as x = 5 fixes x to 5 for the whole of its scope. Writing x = 6 afterwards is not reassignment — it is a duplicate-definition error the compiler rejects. This is the single most common stumbling block for students arriving from Python or Java: in Haskell, = means mathematical equality, not "store into".

Structural sharing makes immutability affordable

A natural worry is that copying data on every change must be ruinously slow. In practice, immutable structures use structural sharing: the new value reuses the unchanged parts of the old one rather than deep-copying them. When we wrote 0 : original, Haskell did not copy [1, 2, 3]; the new list is a single new cell holding 0 whose tail points at the existing [1, 2, 3].

graph LR
    M["modified: 0"] --> O0["1"]
    subgraph original
        O0 --> O1["2"]
        O1 --> O2["3"]
        O2 --> N["[]"]
    end

Both original and modified are valid, distinct lists, yet the three shared cells exist only once in memory. Because the shared portion can never change (it is immutable), sharing it is completely safe — no second reader can be surprised by a mutation. This is why prepending with cons is O(1), not O(n): a key efficiency fact examined in the lists lesson.

---

Modelling "Change" Without Mutation — a Worked Record Update

If nothing can be modified, how does a functional program update a student's score? By building a new record that copies the unchanged fields and overrides the changed one. Haskell's record update syntax does exactly this:

data Student = Student { name :: String, score :: Int }
    deriving (Show)

alice :: Student
alice = Student { name = "Alice", score = 85 }

-- "Update" the score by creating a NEW Student
aliceUpdated :: Student
aliceUpdated = alice { score = 90 }

After this code runs, alice still has score = 85 and aliceUpdated has score = 90. The expression alice { score = 90 } reads as "a Student exactly like alice but with score set to 90". The name field was shared, not recomputed. Crucially, any other part of the program still holding a reference to alice sees the original unchanged — there is no spooky action at a distance where a distant update silently alters your value. That guarantee is the heart of why immutable programs are easier to reason about.

---

How to Decide Whether a Function Is Pure — a Checklist

Exam questions frequently give you a fragment and ask "is this pure? justify your answer". Work through two questions, and the function is pure only if the answer to both is "no":

1. Does its result depend on anything other than its arguments? Look for reads of a global variable, the system clock, a random source, a file or the keyboard. Any of these breaks determinism.
2. Does it change anything observable beyond returning a value? Look for assignment to a global, mutation of an argument (e.g. list.append), printing, or writing to a file/network/screen. Any of these is a side effect.

Apply the checklist to four fragments:

# A: pure -> result depends only on x, y; nothing changed
def f(x, y): return x * y + 1

# B: impure -> reads a global that can change (breaks determinism)
rate = 1.2
def g(price): return price * rate

# C: impure -> mutates its argument (a side effect)
def h(xs): xs.append(0); return xs

# D: impure -> performs I/O (a side effect), even though it returns x
def k(x): print(x); return x

Fragment B is the subtle one and a favourite of examiners: g looks pure because it only multiplies, but it reads the mutable global rate. If some other code reassigns rate, then g 100 changes its answer, so g is not deterministic. Contrast that with a function that uses a genuine constant such as pi: a constant never varies, so determinism is preserved and the function stays pure. The discriminator is therefore mutability of the external thing read, not merely "does it touch anything outside itself".

---

Determinism Made Concrete — a Traced Comparison

It helps to see why determinism licenses substitution while non-determinism forbids it. Take a pure function and substitute its calls freely:

triple :: Int -> Int
triple x = x * 3

-- triple 4 is ALWAYS 12, so every occurrence can be replaced by 12
  triple 4 + triple 4
= 12 + triple 4
= 12 + 12
= 24

Now consider an impure, non-deterministic counterpart written in Python (Haskell will not even let you write this as an ordinary function):

import random
def lucky(): return random.randint(1, 6)

# lucky() has NO single value — these two calls may differ
x = lucky() + lucky()   # could be 2, could be 12, could be anything in 2..12

You cannot rewrite lucky() + lucky() as 2 * lucky() — that changes the meaning, because the original makes two independent draws. The pure version could be safely rewritten as 2 * triple 4; the impure one cannot. This is referential transparency working for you in one case and its absence biting you in the other, and it is exactly the property a compiler relies on when it caches or reorders pure computations.

---

Reconciling Purity with the Real World: the IO Type

A fair objection is that every useful program must eventually do something impure — read input, print output, save a file. Haskell does not deny this; it quarantines effects inside a special type called IO. A value of type IO a is a description of an effectful action that, when run, produces a value of type a. The type system then keeps the two worlds visibly separate:

-- A PURE function: ordinary type, no IO anywhere
greeting :: String -> String
greeting name = "Hello, " ++ name ++ "!"