Class 22 - Templates for lists

Date: November 2, 2026

⚠️Homework

Homework 8 due November 8, 2026

‼️Ending Skills

Last week for skills: 4

🆕New Skills

First week for skills: 6, 7

Skills: 7

Notes (review before class)

Lists as Recursive Data

match tells apart variants of conditional data (Class 20), and empty and non-empty lists (Class 21): lists are conditional data, built into Python. Our own version: a NumList (list of numbers) is either an NlEmpty or an NlLink. (Try, before reading on: what fields should NlLink have, and of what types?)

from dataclasses import dataclass

@dataclass
class NlEmpty:
    pass

@dataclass
class NlLink:
    first: float
    rest: "NumList"

NumList = NlEmpty | NlLink

NlLink has the two parts of a non-empty list: first, a float, and rest, a list of numbers, so a NumList.
NumList isn't defined until after the two classes, so inside them its name is written in quotes.
rest has the very type being defined: a data definition with a field of its own type is recursive data.
This works because building a NumList starts from NlEmpty(), which doesn't refer to NumList; NlLink adds numbers to the front. Building 2, 7, 3 (each rest a valid NumList):

NlEmpty()
NlLink(3, NlEmpty())
NlLink(7, NlLink(3, NlEmpty()))
NlLink(2, NlLink(7, NlLink(3, NlEmpty())))

Recursive data is arbitrarily sized: NlLink makes any NumList larger, so functions must handle any length, like NlLink(1, NlLink(2, ... NlLink(8, NlEmpty()) ...)).

A Function over Recursive Data

contains_3 returns whether a NumList contains 3:

def contains_3(nl: NumList) -> bool:
    """returns True if nl contains 3, False otherwise"""
    ...

def test_contains_3():
    assert not contains_3(NlEmpty())
    assert contains_3(NlLink(3, NlEmpty()))
    assert contains_3(NlLink(1, NlLink(3, NlEmpty())))
    assert contains_3(NlLink(1, NlLink(2, NlLink(3, NlLink(4, NlEmpty())))))
    assert not contains_3(NlLink(1, NlLink(2, NlLink(5, NlLink(4, NlEmpty())))))

Start with a match on the variants, listing each one's fields where its answer goes (in comments: it can't run yet):

# def contains_3(nl: NumList) -> bool:
#     match nl:
#         case NlEmpty():
#             ...
#         case NlLink(first, rest):
#             ... first ...
#             ... rest ...

NlEmpty(): the answer is False.
NlLink(first, rest): if first is 3, the answer is True; otherwise, it is whether rest contains 3.
rest is a NumList, so we could match on it, then on its rest, ...; but any number of copies fails on a list one element longer.
Instead, call the function whose job is exactly that: contains_3(rest). All the tests pass:

def contains_3(nl: NumList) -> bool:
    """returns True if nl contains 3, False otherwise"""
    match nl:
        case NlEmpty():
            return False
        case NlLink(first, rest):
            if first == 3:
                return True
            else:
                return contains_3(rest)

Stepping through contains_3(NlLink(1, NlLink(3, NlEmpty()))):

Substitute the argument for nl. The NlLink case matches: first is 1, rest is NlLink(3, NlEmpty()).
1 == 3 is False, so it runs contains_3(NlLink(3, NlEmpty())): an ordinary call, on the rest, which could be a test on its own.
There, first is 3, so it returns True, and so does the original call.

The function does something with the non-recursive part (checks first), and combines it with the result of the same function on the recursive part (rest).

A Template for Recursive Data

On Class 21, substitution across examples gave a function that calls itself on the rest. The same structure comes from the shape of the data: break it into variants (match), pull out each variant's fields, and call the function on any recursive fields (fields of the same type). For NumList:

# def num_list_fun(nl: NumList) -> ...:
#     match nl:
#         case NlEmpty():
#             ...
#         case NlLink(first, rest):
#             ... first ...
#             ... num_list_fun(rest) ...

A template: the outline of any function on a NumList (hence the generic name). Every data definition has one.
To write a specific function, copy the template, rename it, and fill in the ...s: what does the recursive call return, and how do you combine it with the non-recursive parts?
Examples (Class 21) and the template lead to the same function, but the template scales to complicated data definitions (there will be many), where writing examples out by hand is tedious.

Strategy: Writing a Template for Recursive Data. Given a recursive data definition:

Write a function header (with a placeholder name, if you aren't writing a specific function yet).
Use match to break the recursive-data input into its variants.
In each case, list each of its fields in the answer part.
Call the function itself on any recursive fields.

The Design Recipe

Together, these techniques make a design recipe (adapted from How to Design Programs) for functions over recursive data:

Header: name (needed for recursive calls), contract (input and output types, as annotations), and docstring. The contract guides the body.
Examples: input-output examples as tests, with concrete data, guided by the contract. Include inputs that extend other inputs.
Template: from the definition of the input's type.
Body: fill in the template using your examples (at least one per case). Where one input extends another, the difference in outputs becomes the body, as on Class 21.
Run the examples, to check the function behaves as you expect.
More tests: the examples were about input-output behavior; now add tests that focus on the implementation's details.

Recap (15 mins)

The design recipe, applied to counting the 7s in a NumList: the data definition and examples, the template, and the function written from it, with its tests:

from dataclasses import dataclass

@dataclass
class NlEmpty:
    pass

@dataclass
class NlLink:
    first: float
    rest: "NumList"

NumList = NlEmpty | NlLink

one_7 = NlLink(0, NlLink(7, NlEmpty()))
two_7s = NlLink(7, one_7)

# def num_list_fun(nl: NumList) -> ...:
#     match nl:
#         case NlEmpty():
#             ...
#         case NlLink(first, rest):
#             ... first ...
#             ... num_list_fun(rest) ...

def num_7s(nl: NumList) -> int:
    """counts how many times 7 appears in nl"""
    match nl:
        case NlEmpty():
            return 0
        case NlLink(first, rest):
            if first == 7:
                return num_7s(rest) + 1
            else:
                return num_7s(rest)

def test_num_7s():
    assert num_7s(NlEmpty()) == 0
    assert num_7s(NlLink(0, NlEmpty())) == 0
    assert num_7s(NlLink(7, NlEmpty())) == 1
    assert num_7s(one_7) == 1
    assert num_7s(two_7s) == 2

Line num_7s up against the template: what did each ... become?
What is the first recursive call that num_7s(two_7s) makes, and what does it return?
Which test would fail if return num_7s(rest) + 1 were return 1?

Class Exercises (40 mins)

Use the design recipe to write a function contains_n that takes a NumList and a number, and returns whether that number is in the NumList. Use the template to start when you get to the code step.
Use the design recipe to write a function total_sum that takes a NumList, and returns the sum of all the numbers in it. The sum of the empty list is 0. Use the template to start when you get to the code step.
Use the design recipe to write a function remove_3 that takes a NumList, and returns a new NumList with any 3’s removed. The remaining elements should all be in the list in the same order they were in the input. Use the template to start when you get to the code step.
Write a data definition called NumListList that represents a list of NumLists, and use the design recipe to write a function total_sum_of_lists that takes a NumListList and produces a NumList containing the sums of the sub-lists.
Write a data definition and corresponding template for StrList, which captures lists of strings.

Wrap-up (5 mins)

Data has structure, which can be used to guide how we implement functions.
We can write function templates based on that structure, which is a helpful starting point.

Skills: 7​

Notes (review before class)​

Lists as Recursive Data​

A Function over Recursive Data​

A Template for Recursive Data​

The Design Recipe​

Recap (15 mins)​

Class Exercises (40 mins)​

Wrap-up (5 mins)​