Exercises — Property-based testing

• (a) Example-based. It fixes ONE input [3,1,2] and asserts ONE hardcoded output. It says nothing about any other list.
• (b) Property-based. The @given(lists(integers())) decorator asks the framework to generate many random lists, and the assertion sort(sort(xs)) == sort(xs) is a rule that must hold for all of them. This is the idempotence pattern: sorting an already-sorted list changes nothing.

• A → 3. Round-trip: $g$ undoes $f$, so encoding then decoding returns the original.
• B → 1. Idempotence: applying twice equals applying once.
• C → 2. Invariant: sorting reorders but preserves the count of elements. Where are Oracle and Metamorphic? The mnemonic RIIOM = Round-trip, Idempotence, Invariant, Oracle, Metamorphic has five patterns, but only three fit into a single self-contained formula. The last two need extra machinery and so appear later on this page:
• Oracle compares against a second, trusted function — $f_{\text{fast}}(x)=f_{\text{slow}}(x)$ — so it needs a reference implementation (see Exercise 2.3).
• Metamorphic relates two different inputs whose outputs must be related — so it needs a pair of inputs, not one (see Exercise 4.2). They are omitted from this three-row table on purpose, not by mistake.

Pattern: Round-trip (inverse functions), because from_json is defined to undo to_json. $\forall x\in \{\text{JSON-serialisable values}\},\text{from\_json}(\text{to\_json}(x))=x$ Here the domain of $x$ is stated explicitly: it is the set of values to_json is contracted to accept — numbers, strings, booleans, None, and lists/dicts built from those. The $\forall$ symbol means "for all", and it ranges only over that set, not over every Python object.

@given(json_values())   # generate whatever `to_json` accepts
def test_json_roundtrip(x):
    assert from_json(to_json(x)) == x

Generator note: it must produce valid inputs for to_json — exactly the JSON-serialisable values above. See Hypothesis (Python) strategies. If you feed it a Python set (not JSON-representable), you'd get a false failure that is your generator's fault, not the code's.

Throughout, $xs$ ranges over all finite lists of integers — the full input contract of dedupe. Property 1 — Idempotence: de-duplicating an already-deduped list changes nothing. $\forall xs,\text{dedupe}(\text{dedupe}(xs))=\text{dedupe}(xs)$ Property 2 — Invariant (membership preserved): every element of the input still appears in the output, and no new element is invented. $\forall xs,\text{set}(\text{dedupe}(xs))=\text{set}(xs)$

@given(lists(integers()))
def test_dedupe_idempotent(xs):
    assert dedupe(dedupe(xs)) == dedupe(xs)
 
@given(lists(integers()))
def test_dedupe_preserves_membership(xs):
    assert set(dedupe(xs)) == set(xs)

First, a notation note we will reuse: $\lfloor y\rfloor$ means floor — round down to the nearest whole number (so $\lfloor 2.5\rfloor =2$). In Python the operator // is integer / floor division: 5 // 2 == 2. So len(xs)//2 and $\lfloor \text{len}(xs)/2\rfloor$ are the same thing written in two notations. We use the words interchangeably from here on because they are literally equal for non-negative lengths.

Pattern: Oracle — compare the fast version against a trusted slow reference.

Odd length ($\text{len}(xs)$ is odd): there is a single middle element after sorting. $\forall xs\text{ with odd length},\text{fast\_median}(xs)=\text{sorted}(xs)[\lfloor \text{len}(xs)/2\rfloor ]$ Example: for $xs=[3,1,4,1,5]$, sorted is $[1,1,3,4,5]$, and $\lfloor 5/2\rfloor =2$, so the reference picks index $2$, which is $3$.

Even length ($\text{len}(xs)$ is even): there is no single middle — two elements straddle the centre, and the median is their average. This is the natural edge case, and skipping it would leave half of all inputs untested. $\forall xs\text{ with even length},\text{fast\_median}(xs)=\frac{\text{sorted}(xs)[n-1]+\text{sorted}(xs)[n]}{2},n=\frac{\text{len}(xs)}{2}$ Example: for $xs=[4,1,3,2]$, sorted is $[1,2,3,4]$, $n=2$, so the median is $(\text{index }1+\text{index }2)/2=(2+3)/2=2.5$.

def slow_median(xs):
    s = sorted(xs)
    n = len(s)
    if n % 2 == 1:
        return float(s[n // 2])
    return (s[n // 2 - 1] + s[n // 2]) / 2
 
@given(lists(integers(), min_size=1))
def test_median_oracle(xs):
    assert fast_median(xs) == slow_median(xs)

Why min_size=1: the median is undefined for the empty list, so we exclude it from the domain. We now cover every non-empty list — both parities.

The bug is in the property (the test), not necessarily the code. encode strips whitespace, so it is lossy — it throws information away. For an input like s = " a ", encode(s) == "a", and decode("a") == "a" != " a ". A round-trip property $g(f(x))=x$ is only valid when $f$ is injective / lossless. Stripping is not lossless, so this pattern simply does not apply. Correct property (idempotence of the lossy step instead): $\text{encode}(\text{encode}(s))=\text{encode}(s)$ Stripping twice equals stripping once — that is true here.

Shrinking is a greedy descent toward the simplest still-failing input (see figure). The framework tries the cheapest simplifications first — dropping elements shrinks structure fastest — and only switches to shrinking the values once the list is already as short as it can be. A plausible path:

1. [3,1,4,1,5,9,2,6] — fails. Why drop elements first? Fewer elements is the biggest simplification, so the greedy search tries that before touching values.
2. [3,1,4,1,5] — dropped the tail; the duplicate 1 survives, still fails → keep (a smaller failing input is strictly better).
3. [1,4,1] — dropped more, keeping both copies of the duplicate because we suspect duplicates matter; still fails → keep.
4. [1,1] — dropped the non-duplicate 4; still fails → keep. We now cannot drop further without destroying the duplicate.
5. [1] — dropping one copy leaves no duplicate, so the bug's trigger is gone → passes → discard, restore [1,1]. Why this teaches us something: the pass tells the framework the duplicate is essential, so it stops dropping and switches strategy.
6. Now shrink values toward 0: [0,0] — still a duplicate, still fails → keep. Values can't get simpler than 0. Stopping condition: no simpler candidate (fewer elements, or values closer to 0) still fails. Report [0,0]. That minimal counterexample points straight at "breaks when a duplicate exists." See Fuzzing for the raw-generation cousin without this shrink step.

Direction 1 — parse ∘ render (starting from numbers): this is the clean round-trip. $\forall n\in \mathbb{Z},\text{parse}(\text{render}(n))=n$

@given(integers())
def test_render_then_parse(n):
    assert parse(render(n)) == n

Direction 2 — render ∘ parse (starting from strings): trickier because many strings map to the same number ("007", "+7", "7" all parse to 7). So render(parse(s)) == s is false in general — render produces only the canonical form. The correct property is that render ∘ parse is idempotent. Here is the "why", step by step:

• Let $c(s)=\text{render}(\text{parse}(s))$ be "canonicalise the string $s$".
• Applying $c$ once turns any valid form ("007") into its canonical form ("7").
• Applying $c$ again to an already-canonical string must return it unchanged — canonicalising the canonical form does nothing new.
• That "second application changes nothing" is exactly the idempotence law $c(c(s))=c(s)$. Unwrapping $c$ gives the nested form: $\forall s\text{ valid},\text{render}(\text{parse}(s))=\text{render}(\text{parse}(\text{render}(\text{parse}(s))))$ The outer render(parse(...)) is $c$ applied to the inner render(parse(s)), which is $c(s)$ — so the whole line reads $c(s)=c(c(s))$. It is not a magic string of functions; it is idempotence with $c$ spelled out.

@given(text())
def test_render_parse_idempotent(s):
    assume(is_parseable(s))          # only valid numeric strings
    canon = render(parse(s))
    assert render(parse(canon)) == canon

Why assume: we filter out non-numeric strings so we test only inputs the contract covers. This mirrors Test-driven development: properties describe the intended contract first.

Metamorphic = relate two related inputs whose outputs must be related, even when the exact output is unknown. Property: adding a document that does not contain the query must not change the results already returned. $\forall q,\forall D,\forall d\text{ with }q\notin d:\text{search}(q,D)=\text{search}(q,D\cup \{d\})\setminus \{d\}$

@given(query=text(min_size=1), docs=lists(text()), irrelevant=text())
def test_irrelevant_doc_doesnt_change_results(query, docs, irrelevant):
    assume(query not in irrelevant)
    base = search(query, docs)
    extended = search(query, docs + [irrelevant])
    assert [r for r in extended if r != irrelevant] == base

We never assert the actual ranking — only that an irrelevant addition is invisible to the query. That is the power of metamorphic testing (the M in RIIOM, and the reason it could not fit the single-formula table of Exercise 1.2).

Why not a proof: PBT is sampling from an input space. For integers() that space is countably infinite — infinitely many values, but you still visit only finitely many (10,000) of them. Passing 10,000 cases says nothing about the infinitely many untested integers. It raises confidence, never certainty. (Contrast with a mathematical proof, or an exhaustive check over a genuinely finite domain.) The hidden bug: f(42) divides by zero → ZeroDivisionError. If the framework's random draws from integers() never happened to hit exactly 42, all 10,000 cases pass while the bug lurks. Smallest generator change to expose it: bias the generator toward the boundary value, e.g. integers(min_value=40, max_value=44) or add 42 explicitly via sampled_from([42]) mixed in. Frameworks like Hypothesis (Python) already nudge generators toward such "magic" boundary values, which is why it usually would find 42 — but a naive uniform generator over a huge range might not. This is the everyday argument for combining PBT with hand-written boundary example tests.

Why shrinking breaks: shrinking assumes that if input $x$ fails, re-running $x$ still fails, so it can safely test simpler inputs and trust the pass/fail signal. If f reads a hidden global RNG, then re-running the same input may pass one moment and fail the next. The framework tries a simpler candidate, it passes by luck, and the shrinker wrongly discards it — the reported "minimal" case may not even reproduce. Fix: make behaviour deterministic per input — seed the RNG from the input, inject the RNG as a parameter, or make the property tolerant (assert a range, not an exact value). Frameworks also replay the failing seed so a genuine failure can be reproduced. Classification: a function with hidden global randomness is not a pure function — it has a hidden dependency (the RNG state) and is not referentially transparent. Pure functions are the ideal target for PBT precisely because same-input-same-output makes shrinking reliable.

(a) The accepted chain. Halve while the result still fails ($|x|\ge 10$); reject the first halving that lands below the threshold: $848\to 424\to 212\to 106\to 53\to 26\to 13$ Checking each: $848,424,212,106,53,26,13$ all have $|x|\ge 10$ → fail → accepted. The next candidate is $\lfloor 13/2\rfloor =6$, but $6<10$ → it passes → discarded. (b) Reported minimum. Pure halving cannot step below the last still-failing value it holds, so it reports $\boxed{13}$. (c) What a smarter shrinker does. After halving stalls at 13, a finer strategy would linearly probe the still-failing region downward: $12,11,10$ all fail, but $9<10$ passes — so the true minimal failing value is $\boxed{10}$. Plain halving misses it because its step size (halving) is too coarse near the boundary; it lands on 6 (below threshold) and stops, getting stuck at a local, not global, minimum. This is the everyday lesson: shrinking gives a much simpler, usually near-minimal, counterexample — not a provably minimal one.