Chapter 41

Toolkits

Pure functions are parts, and the same few operations on parts recur in every program: fold, cache, specialize, chain. functools and itertools supply them, written and tested.

Foundations builds behavior from small, pure, composable pieces. functools operates on functions themselves. itertools assembles lazy iterators from composable parts. This chapter tours both toolkits, then turns to two techniques that pair naturally with them: lazy evaluation and recursion. A case study then puts several of the pieces to work on one problem.

The `functools` Toolkit

The standard library provides the building blocks of functional Python under functools, from a single reduce() call to an alternate dispatch mechanism. Each one replaces code you would otherwise write and debug yourself. Caching logic, an eviction policy, a dispatch table: each has an edge case that’s easy to miss on the first attempt. The library’s versions handle those edge cases correctly. CPython implements in C the ones where speed matters most: reduce(), partial(), and the two caches. What follows starts with the simplest tools and works up to singledispatch and singledispatchmethod, which take one registered function per type.

`reduce`

Folds a sequence into a single value by repeatedly applying a two-argument function.

# functools_reduce.py
from functools import reduce
from operator import add

print(reduce(add, [1, 2, 3, 4]))
#: 10

operator.add() is + as a function. The operator module supplies a named function for each operator, ready to pass to a fold in place of lambda a, b: a + b.

For addition specifically, sum() is the dedicated built-in, and math.prod() covers multiplication. reduce() is the tool for every other fold.

On an empty sequence reduce() raises TypeError: reduce() of empty iterable with no initial value, because it has nothing to return. A third argument supplies that starting value, so reduce(add, [], 0) returns 0.

`cache`

Remembers every result forever, so a repeated call with the same arguments returns the stored result without running the body. @cache works correctly only for pure functions. A cached function with side effects runs those effects on the first call with each set of arguments, and skips them on every repeat.

The cache is a dictionary keyed on the arguments, so every argument must be hashable. Passing a list raises TypeError: unhashable type: 'list'.

# functools_cache.py
from functools import cache

@cache
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(30))
#: 832040
print(fib.cache_info())
#: CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)

Because fib() is recursive, the cache now holds every value up to and including 30. The counts show what caching saved. The 31 misses are the 31 distinct arguments, 0 through 30. The 28 hits are the calls that found a stored answer. That is fifty-nine calls in all, against 2,692,537 for the undecorated version, where every branch recomputes the whole subtree beneath it. Caching runs both versions side by side, and Recursion comes back to why the recursive form is worth keeping.

An iterative Fibonacci, a, b = b, a + b in a loop, needs neither recursion nor a cache. The recursive one stays the running example here because it keeps the point about caching small. The branching and the repeated subproblem matter, not the arithmetic.

One trap: decorating a method with @cache keys every entry on self, so the cache holds a strong reference to each instance forever. That is Observer’s lapsed listener leak in cache form. For the usual case, one expensive value per instance, use @cached_property. It stores the result in the instance’s __dict__, so the result goes away with the instance.

`lru_cache`

Like cache(), but bounds memory by discarding the least recently used entry once the cache reaches maxsize.

# functools_lru_cache.py
from functools import lru_cache

@lru_cache(maxsize=2)
def square(n: int) -> int:
    return n * n

square(1)
square(2)
square(3)  # Evicts 1, the least recently used
square(2)  # [1]
square(1)  # [2]
print(square.cache_info())
#: CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

The single hit is the second square(2) ([1]), which is still in the cache. The second square(1) ([2]) is a fourth miss, although 1 was the first value computed, and that miss proves the cache evicted 1. The cache discards the least recently used entry before it stores a new one, so currsize stays at or below maxsize.

`partial`

Presets some of a function’s arguments and returns a new function that expects the rest. Partial Application covers it in depth.

# functools_partial.py
from functools import partial

shout = partial(print, end="!\n")
shout("hello")
#: hello!

functools.Placeholder reserves a position so you can preset a later positional argument and leave an earlier one for the caller.

`partialmethod`

The same idea as partial(), but for a method. partialmethod returns a descriptor, which binds self automatically when you access the method on an instance.

# functools_partialmethod.py
from functools import partialmethod
from record import record

@record
class Text:
    value: str

    def pad(self, width: int, fill: str = " ") -> str:
        return self.value.rjust(width, fill)

    zero_pad = partialmethod(pad, fill="0")

print(Text("7").zero_pad(3))
#: 007

A partial object is a descriptor too, so writing zero_pad = partial(pad, fill="0") here works. partial and partialmethod differ as soon as an argument is positional. partialmethod passes the instance first and the bound arguments after it, the order a method expects. partial passes the bound arguments first and the instance after them, so partial(pad, 5) calls pad(5, instance) and fails with AttributeError: 'int' object has no attribute 'value'. Use partialmethod inside a class body and partial everywhere else.

`cached_property`

Runs a property’s code once, on first access, then reuses the stored result.

# functools_cached_property.py
from dataclasses import dataclass
from functools import cached_property

@dataclass
class Lazy:
    n: int

    @cached_property
    def squared(self) -> int:
        print("computing")
        return self.n * self.n

x = Lazy(5)
print(x.squared)
#: computing
#: 25
print(x.squared)  # No second "computing"
#: 25
x.n = 10  # Doesn't change the cached result
print(x.squared)
#: 25

The stored result stays when an input changes. x.n = 10 leaves squared at 25. del x.squared resets it. Deleting the cached attribute discards the stored value, and the next access recomputes it from the current state.

A first access from two threads at once is a race. cached_property takes no lock, so both threads can find no stored value and both run the property’s code.

The stored value goes in the instance’s __dict__, so the class must have one. A record is slotted and has none. The first access to a cached_property on a @record raises a TypeError, as slots_limits.py in When Slots Does Not Fit shows. Lazy is a @dataclass for that reason, and because the demo assigns to x.n.

`wraps`

Copies a wrapped function’s name and docstring onto its wrapper, so a tool that reads those attributes reports the original. Its sibling, update_wrapper(), copies the same metadata onto a wrapper that is a class instance.

# functools_wraps.py
from collections.abc import Callable
from functools import wraps

def trace(
    func: Callable[[str], str]
) -> Callable[[str], str]:
    @wraps(func)
    def wrapper(name: str) -> str:
        return func(name)
    return wrapper

@trace
def greet(name: str) -> str:
    "Say hello."
    return f"Hello, {name}!"

print(greet.__name__, "-", greet.__doc__)
#: greet - Say hello.

If you delete the @wraps(func) line, that same print() reports wrapper - None, and every tool that reports a function by its name or docstring, help() among them, reports the wrapper too. The name greet refers to wrapper either way. wraps() copies the original’s name and docstring onto wrapper. wraps() also sets greet.__wrapped__ to the original function, so a tool that needs the original, such as inspect.signature(), can reach it.

`cmp_to_key`

Wraps an old-style comparator into a key function that sorted() accepts as its key argument. A comparator takes two values and returns negative, zero, or positive.

# functools_cmp_to_key.py
from functools import cmp_to_key

def by_length_desc(a: str, b: str) -> int:
    return len(b) - len(a)

words = ["a", "ccc", "bb"]
print(sorted(words, key=cmp_to_key(by_length_desc)))
#: ['ccc', 'bb', 'a']

This ordering has a key. sorted(words, key=len, reverse=True) gives the same list, and a key function is the better choice whenever one exists. cmp_to_key() is for a comparator that arrives from older code, and for an ordering with no per-element key, where the rule is a comparison between two elements.

`total_ordering`

Fills in the rest of the comparison methods from __eq__ and one of __lt__, __le__, __gt__, or __ge__, so a class needs two methods instead of five to sort and compare correctly.

# functools_total_ordering.py
from functools import total_ordering

@total_ordering
class Weight:
    def __init__(self, kg: float) -> None:
        self.kg = kg

    def __eq__(self, other: object) -> bool:
        return (isinstance(other, Weight)
                and self.kg == other.kg)

    def __lt__(self, other: Weight) -> bool:
        return self.kg < other.kg

light = Weight(2)
heavy = Weight(5)
print(light < heavy, light <= heavy, light > heavy)
#: True True False

Weight is a hand-written class to show the tool. In real code Weight would be @dataclass(frozen=True, order=True), which generates all five comparison methods from the field order. total_ordering is the right tool when the class cannot be a dataclass, or when the ordering differs from the fields in declaration order.

Each synthesized comparison is slower than a hand-written one, because it wraps a call to your __lt__ or __eq__. A method that dataclass generates compares the fields with no extra call.

`singledispatch`

Turns a plain function into one that dispatches on the type of its first argument, with per-type implementations you register separately. Visitor uses singledispatch() as an alternative to the Visitor pattern, and explains why the registered function below takes the name _.

# functools_singledispatch.py
from functools import singledispatch

@singledispatch
def describe(value: object) -> str:
    return f"a {type(value).__name__}"

@describe.register
def _(value: int) -> str:
    return f"the number {value}"

print(describe("hi"), "|", describe(5))
#: a str | the number 5

Because singledispatch() dispatches on the first argument alone, a rule that depends on two types needs Multiple Dispatching. The caller must pass that argument by position. describe(value=5) raises TypeError: describe requires at least 1 positional argument.

`singledispatchmethod`

The same dispatch, written as a method so it reads as self.op(x) instead of a bare function call. The registered method below again takes the placeholder name _.

# functools_singledispatchmethod.py
from functools import singledispatchmethod

class Describer:
    @singledispatchmethod
    def describe(self, value: object) -> str:
        return f"a {type(value).__name__}"

    @describe.register
    def _(self, value: int) -> str:
        return f"the number {value}"

d = Describer()
print(d.describe("hi"), "|", d.describe(5))
#: a str | the number 5

singledispatchmethod dispatches on the first argument after self, not on self, so the type of value selects the implementation, just as it does for the plain describe() in functools_singledispatch.py.

itertools does for iteration what functools does for functions. It supplies ready-made pieces you compose, in place of loops you write and test again.

The `itertools` Toolkit

Each itertools function produces values on demand instead of building a list up front, the property Lazy Evaluation revisits below. Each is also a loop you would otherwise write by hand. The itertools version is written in C and correct on the edge cases a hand-written version can miss: the empty iterable, the single element, and the point where two sequences run out at different lengths. Combine them the way you combine any small function, by passing one’s output to the next. Reusable Algorithms introduces several of these as stages in lazy pipelines. This section is the catalog.

`repeat`

Yields the same object over and over, forever or a set number of times.

# itertools_repeat.py
from itertools import repeat

print(list(repeat("x", 3)))
#: ['x', 'x', 'x']
print(list(map(pow, range(5), repeat(2))))
#: [0, 1, 4, 9, 16]

The counted form replaces the list you would write as ["x"] * 3. The infinite form is the reason to import repeat(). It supplies a constant argument for as many calls as map() makes, and it holds one object in memory however many calls there are. Here the output stops when range(5) runs out, because map() stops at its shortest input.

`islice`

Slices any iterable, including an infinite one, the way [start:stop:step] slices a list.

# itertools_islice.py
from itertools import islice

print(list(islice(range(10), 2, 8, 2)))
#: [2, 4, 6]

Two differences from a list slice. islice() rejects negative indices with a ValueError, since a negative index counts back from the end, and an iterable may have none. And it consumes every element it passes. An iterator you pass to islice() resumes where the slice stopped. A list slice leaves the list as it was.

`count`

Counts up (or down) forever from a start value, with a constant step.

# itertools_count.py
from itertools import count, islice

print(list(islice(count(10, 2), 5)))
#: [10, 12, 14, 16, 18]

`cycle`

Repeats an iterable forever.

# itertools_cycle.py
from itertools import cycle, islice

print(list(islice(cycle("AB"), 5)))
#: ['A', 'B', 'A', 'B', 'A']

cycle() saves each element the first time through, so the whole input stays in memory for as long as the cycle object exists.

`chain`

Iterates over several iterables one after another, as if they were one. chain.from_iterable(iterables) does the same when the iterables themselves arrive as one lazy sequence, rather than as separate arguments. Where the iterables come from a loop, unpacking in a comprehension says the same thing without the import.

# itertools_chain.py
from itertools import chain

print(list(chain([1, 2], [3, 4])))
#: [1, 2, 3, 4]
print(list(chain.from_iterable([[1, 2], [3, 4]])))
#: [1, 2, 3, 4]

`pairwise`

Yields consecutive overlapping pairs from an iterable, without indexing by hand and risking an off-by-one at the ends.

# itertools_pairwise.py
from itertools import pairwise

print(list(pairwise([1, 2, 3, 4])))
#: [(1, 2), (2, 3), (3, 4)]

`batched`

Groups an iterable into fixed-size tuples, with a shorter final batch when the length leaves a remainder. A hand-written loop gets that remainder wrong easily.

# itertools_batched.py
from itertools import batched

print(list(batched(range(7), 3)))
#: [(0, 1, 2), (3, 4, 5), (6,)]

A short final batch is normal for pagination and wrong for fixed-width records. For fixed-width records, batched(data, 3, strict=True) raises ValueError: batched(): incomplete batch instead. zip(strict=True) under zip_longest offers the same choice.

`accumulate`

Yields the running total of an iterable, or the running result of any two-argument function.

# itertools_accumulate.py
from itertools import accumulate
from operator import mul

print(list(accumulate([1, 2, 3, 4])))
#: [1, 3, 6, 10]
print(list(accumulate([1, 2, 3, 4], mul)))
#: [1, 2, 6, 24]

accumulate() is reduce() with the intermediate results kept. The last value it yields is the value reduce() returns.

`compress`

Keeps the elements of one iterable wherever the matching selector is true.

# itertools_compress.py
from itertools import compress

print(list(compress("ABCD", [1, 0, 1, 0])))
#: ['A', 'C']

`takewhile`

Yields elements while a predicate holds, then stops at the first failure.

# itertools_takewhile.py
from itertools import takewhile

print(list(takewhile(lambda n: n < 3, [1, 2, 3, 4, 1])))
#: [1, 2]

The input carries a trailing 1 to separate takewhile() from filter(). filter(lambda n: n < 3, ...) returns [1, 2, 1], because filter() skips a failing element and tests the next. takewhile() stops at the first failure, before it reaches the last element. On finite data the distinction is a detail. On an infinite source it decides whether the program terminates. Reusable Algorithms works through that case.

`dropwhile`

Skips elements while a predicate holds, then yields everything after.

# itertools_dropwhile.py
from itertools import dropwhile

print(list(dropwhile(lambda n: n < 3, [1, 2, 3, 4, 1])))
#: [3, 4, 1]

The same trailing 1 marks the same distinction from the other direction. dropwhile() stops testing once the predicate fails, so it yields the final 1, where filterfalse() tests every element and returns [3, 4].

`filterfalse`

Keeps the elements a predicate rejects, the complement of filter().

# itertools_filterfalse.py
from itertools import filterfalse

print(list(filterfalse(lambda n: n % 2 == 0, range(6))))
#: [1, 3, 5]

`starmap`

Like map(), but unpacks each element as the arguments to the function.

# itertools_starmap.py
from itertools import starmap

print(list(starmap(pow, [(2, 5), (3, 2)])))
#: [32, 9]

map(pow, [2, 3], [5, 2]) gives the same answer from two parallel iterables, one per parameter. starmap() is for arguments that arrive paired, as the tuples zip() produces or the rows of a file.

`zip_longest`

Zips iterables of different lengths, filling the missing positions instead of stopping at the shortest. The default filler is None. When None is a valid element, pass a distinct sentinel as the fillvalue keyword argument:

# itertools_zip_longest.py
from itertools import zip_longest

print(list(zip_longest([1, 2, 3], [4, 5])))
#: [(1, 4), (2, 5), (3, None)]

MISSING = sentinel("MISSING")
print(list(zip_longest([1, 2, 3], [4, 5],
                       fillvalue=MISSING)))
#: [(1, 4), (2, 5), (3, MISSING)]

Python offers three ways to zip inputs of different lengths, and the choice says what a mismatch means. Plain zip() stops at the shortest and raises no error, the right choice when the extra elements are genuinely surplus. zip(a, b, strict=True) raises a ValueError, which for the two lists above reads zip() argument 2 is shorter than argument 1. strict=True is the right choice when equal lengths are an invariant you want checked. zip_longest() pads, the right choice when the missing elements are data in their own right.

`groupby`

Groups consecutive elements that share a key. The input must arrive sorted by that key, since groupby() groups only adjacent elements.

# itertools_groupby.py
from itertools import groupby

data = ["a", "a", "b", "b", "b", "c"]
print([(k, list(g)) for k, g in groupby(data)])
#: [('a', ['a', 'a']), ('b', ['b', 'b', 'b']), ('c', ['c'])]
# [1]
print([(k, list(g)) for k, g in groupby(["b", "a", "b"])])
#: [('b', ['b']), ('a', ['a']), ('b', ['b'])]

The print() at [1] shows what unsorted input does. "b" comes back as two separate groups, and no error reports it. groupby(sorted(data, key=keyfunc), key=keyfunc) is the fix, with the same key function both times. sorted() returns a new list and leaves data as it was, so groupby() must receive what sorted() returns.

The comprehension’s list(g) is necessary. Each group is a view onto the one underlying iterator, so advancing to the next group empties the previous group’s view. list(groupby(data)) therefore returns three keys paired with three empty iterators, because the outer list() walks all the way to the end before anything reads a group. Consume each group before asking for the next one, as the comprehension above does.

`tee`

Splits one iterable into several independent iterators over the same data, so two consumers can each walk it once without collecting it into a list first.

# itertools_tee.py
from itertools import tee

a, b = tee([1, 2, 3])
print(list(a), list(b))
#: [1, 2, 3] [1, 2, 3]

Two cautions. After tee(), use only the returned iterators. Advancing the original source consumes values that the copies then miss. And tee() buffers every value one copy has consumed and the other still awaits. This demo drains a completely before touching b, so tee() stores the whole sequence. When one consumer runs far ahead of the other, list() is simpler and uses the same memory. tee() saves memory when the consumers stay roughly in step. Iterators measures that buffering and adds a third caution. tee() shares one unlocked buffer between its branches, so two threads advancing them at the same time can raise a RuntimeError.

`product`

The Cartesian product of the input iterables, the same pairs a nested for loop builds.

# itertools_product.py
from itertools import product

print(list(product("AB", [1, 2])))
#: [('A', 1), ('A', 2), ('B', 1), ('B', 2)]

Unlike the tools above, product() reads its inputs completely before yielding its first tuple, so every input must be finite. product(count(1), "AB") runs forever, because the call tries to read all of count(1), an input with no end.

`permutations` and `combinations`

Three tools draw r elements from an iterable, and two questions separate them: does order matter, and may an element repeat? The same input and the same r make the answers comparable:

# itertools_selections.py
from itertools import (combinations,
                       combinations_with_replacement,
                       permutations, product)

print(list(permutations("AB", 2)))
#: [('A', 'B'), ('B', 'A')]
print(list(combinations("AB", 2)))
#: [('A', 'B')]
print(list(combinations_with_replacement("AB", 2)))
#: [('A', 'A'), ('A', 'B'), ('B', 'B')]
print(list(product("AB", repeat=2)))
#: [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

permutations() counts orderings, so AB and BA are two results. combinations() treats those as the same draw and keeps one, and keeping one is right when you want each pair of distinct elements once. combinations_with_replacement() also ignores order, but draws from the full input each time, and that repeated draw produces AA. product() with repeat= is the fourth combination of answers. Order matters and elements repeat, so it yields all four pairs.

Composing the Pieces

Each entry above is one stage. Stacked, they are a pipeline:

# itertools_pipeline.py
from itertools import batched, count, islice, takewhile

squares = (n * n for n in count(1))
batches = batched(squares, 3)
totals = (sum(b) for b in batches)
print(list(takewhile(lambda t: t < 500, totals)))
#: [14, 77, 194, 365]
print(list(islice(squares, 3)))  # [1]
#: [256, 289, 324]

The pipeline stacks four stages on an infinite source, and none of them runs until list() pulls. The print() at [1] shows the source resuming at n = 16 rather than 13, because takewhile() pulls one more total, the 590 from the batch (169, 196, 225), finds it over the limit, and discards it. A pull-based pipeline reads one value further than it keeps, and here that one value is a batch of three squares.

Lazy Evaluation

Lazy evaluation computes a value only when something needs it. A generator is the canonical example. It yields one value at a time, each on request. With itertools, you can describe an infinite sequence and take only the part you use:

# lazy.py
from collections.abc import Iterator
from itertools import count, islice

def squares() -> Iterator[int]:
    for n in count(1):
        # Proves this runs on demand
        print(f"computing square {n}")
        yield n * n

# count() is infinite; islice() pulls only what's needed:
first_five = list(islice(squares(), 5))
#: computing square 1
#: computing square 2
#: computing square 3
#: computing square 4
#: computing square 5
print(first_five)
#: [1, 4, 9, 16, 25]

squares() yields squares without end, yet the program terminates because islice() requests five values. Each computing square N line appears the moment islice() pulls that value, one at a time, the same way any for loop consumes a generator. The fifth computing square line is the last, because islice() asks for exactly five.

list(squares())[:5] looks equivalent and is a different program. It builds the whole list before slicing, so it asks squares() for every value. squares() has no last value, so list() keeps asking for more and the program stalls before the slice. Slicing lazily lets the source be infinite. Slicing a list requires a source that ends. Lazy Evaluation with Generators looks at the same idea from the perspective of memory and speed.

Laziness matters most at scale. A generator pipeline can process a multi-gigabyte file or a live network stream one item at a time, so memory use stays constant whatever the size of the source. Stages chain together, passing one item at a time between them. A consumer that stops early, such as any() or next(), ends the upstream work at the same point.

Recursion

Recursion expresses a repeated computation as a function that calls itself. Each recursive function needs a base case that stops the recursion and a recursive case that moves toward it:

# recursion.py
import sys

def factorial(n: int) -> int:
    # Base case stops the recursion:
    if n <= 1:
        return 1
    # Recursive case moves toward the base case:
    return n * factorial(n - 1)

print(factorial(5))
#: 120
# Python caps how deep recursion can go:
print(sys.getrecursionlimit())
#: 1000

A for loop computes this same factorial in about the same number of lines and stays in one frame at any n. Python pushes a frame for every recursive call, including one in tail position, where a language with tail-call optimization reuses the caller’s frame. The stack has a cap, so deep recursion raises a RecursionError. sys.setrecursionlimit() raises that limit when the depth is genuine.

A long flat sequence calls for a loop or one of the itertools tools. For a countdown like this one, the loop is as short as the recursion and faster, since it makes no calls. Recursion is the better choice once the problem branches rather than repeats, as nested_sum.py shows.

Branching adds a problem of its own. More than one branch can reach the same subproblem, and a plain recursive function recomputes it every time. That recomputation is why the recursive fib() under cache gets a decorator rather than a rewrite as a loop. The recursion states the definition, and the cache removes the repetition.

Self-similar problems, such as walking a tree, are a different reason to recurse. In a tree walk each subproblem occurs once, and a cache would save nothing. Code that walks a tree, nested data, or a directory reads best when its shape matches the data’s shape. The function handles one node and calls itself for the rest:

# nested_sum.py
type Nested = int | list[Nested]

def deep_sum(items: list[Nested]) -> int:
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)
        else:
            total += item
    return total

print(deep_sum([1, [2, [3, 4], 5], 6]))
#: 21

deep_sum() states what to do with one element and delegates the nesting to itself. To write deep_sum() as a loop, you build your own stack to track which sublists are still open, and you must get the push and pop right at every depth. The recursive version hands that bookkeeping to the call stack.

Case Study: Pairing Rotations

Pair up participants for an activity across several rounds, and avoid repeating a pairing until every possible pairing has occurred once. A small program solves this scheduling problem by combining several of the chapter’s tools: an infinite generator for the rounds, islice() to take as many of them as you want, combinations() for the pairs inside a group, and a seeded random source that makes the whole schedule reproducible.

The circle method solves the pairs-only version exactly, by direct construction. The method holds one player in place and arranges the rest in a circle. Each round, it pairs players sitting across from each other, then rotates everyone but the stationary player by one seat. For an even number of players n, the circle method produces n - 1 rounds with no repeated pair. No schedule can do better, because those rounds use every one of the n * (n - 1) / 2 possible pairs exactly once.

The classical fix for an odd roster is a phantom player. Whoever draws the phantom sits out that round.

Groups of Any Size

The circle method is pairs-only. The circle method is a closed-form answer to one narrow question: how do you split every possible pair into rounds in which each player appears exactly once? Pairs are the only group size where that question has a tidy rotation-based answer. Groups of three are far harder to schedule so that every pair meets exactly once. The best-known case is Kirkman’s schoolgirl problem, fifteen students walking in threes on seven days. A perfect trio schedule exists only when the roster size leaves a remainder of 3 when divided by 6, so seven students have none.

A given students and size may have no exact answer, so the general version below trades rotation for a greedy search and settles for a good schedule. The greedy search builds each group one member at a time, adding whoever the current members have met the fewest times. Those meeting counts come from a running history, updated at the end of every round:

# student_pairs.py
import random
from collections import Counter
from collections.abc import Iterator
from itertools import combinations

type Group = tuple[str, ...]
type Round = list[Group]

def group_rounds(
    students: list[str], size: int, seed: int = 0
) -> Iterator[Round]:
    history: Counter[frozenset[str]] = Counter()
    rng = random.Random(seed)

    def met(group: list[str], candidate: str) -> int:
        return sum(history[frozenset((m, candidate))]
                   for m in group)

    while True:
        pool = list(students)
        rng.shuffle(pool)
        groups: list[list[str]] = []
        while len(pool) >= size:
            leader = pool.pop()
            group = [leader]
            while len(group) < size:
                stranger = min(pool,
                               key=lambda c: met(group, c))
                pool.remove(stranger)
                group.append(stranger)
            groups.append(group)
        # Roster smaller than one group
        if pool and not groups:
            groups.append([])
        # Too few left for a full group of `size`
        for extra in pool:
            host = min(groups, key=lambda g: met(g, extra))
            host.append(extra)
        round_result: Round = [tuple(g) for g in groups]
        for g in round_result:
            for pair in combinations(g, 2):
                history[frozenset(pair)] += 1
        yield round_result

The first demo schedules seven students in pairs for seven rounds and counts who met whom:

# pair_rounds.py
from itertools import combinations, islice
from student_pairs import group_rounds

students = ["Ana", "Bo", "Cy", "Di", "Eve", "Fi", "Gia"]
rounds = list(islice(group_rounds(students, 2),
                     len(students)))
for i, grouping in enumerate(rounds[:3]):
    print(i, grouping)
#: 0 [('Gia', 'Eve', 'Ana'), ('Di', 'Cy'), ('Fi', 'Bo')]
#: 1 [('Di', 'Bo', 'Eve'), ('Cy', 'Ana'), ('Gia', 'Fi')]
#: 2 [('Eve', 'Fi', 'Ana'), ('Bo', 'Gia'), ('Cy', 'Di')]

meetings = [*map(frozenset, combinations(group, 2))
            for r in rounds for group in r]
possible = set(map(frozenset, combinations(students, 2)))
distinct = set(meetings)
print(len(distinct), "of", len(possible),
      "pairs met at least once")
#: 21 of 21 pairs met at least once
print(len(meetings) - len(distinct), "repeat meetings")
#: 14 repeat meetings

Called with size=2, group_rounds() covers all 21 possible pairs across the seven rounds, with no rotation and no stationary player: a shuffle, then a greedy choice repeated until the pool is empty. The coverage costs 14 repeat meetings. An odd roster leaves one player over, so each round adds that player to an existing pair. A triple holds three meetings where a pair holds one, and those two additional meetings a round, over seven rounds, are the 14 repeats.

Trios come from the same seven students:

# trio_rounds.py
from itertools import islice
from student_pairs import group_rounds

students = ["Ana", "Bo", "Cy", "Di", "Eve", "Fi", "Gia"]
trios = list(islice(group_rounds(students, 3), 3))
for i, grouping in enumerate(trios):
    print(i, grouping)
#: 0 [('Gia', 'Eve', 'Cy', 'Fi'), ('Di', 'Bo', 'Ana')]
#: 1 [('Di', 'Eve', 'Bo', 'Gia'), ('Cy', 'Ana', 'Fi')]
#: 2 [('Eve', 'Ana', 'Gia'), ('Bo', 'Fi', 'Di', 'Cy')]

Called with size=3, the same function schedules trios instead. Seven students make two threes with one left over, so one group grows to four. Growing one group is the join-instead-of-sit-out choice pair_rounds.py shows for pairs.

The last case asks for groups of five from a roster of two:

# small_roster.py
from student_pairs import group_rounds

print(next(group_rounds(["Ana", "Bo"], 5)))
#: [('Ana', 'Bo')]

A roster smaller than one full group is the extreme case of joining instead of sitting out. In group_rounds(), the while len(pool) >= size loop exits at once and leaves groups empty. The if pool and not groups line then creates the one group into which the leftovers fold. If you delete that line, min() receives an empty sequence and raises a ValueError. Two students and a requested size of five produce one group of two, because the alternative is a round in which nobody meets anyone.

`history` Is Mutable State

met() runs once per candidate per slot, so it looks like the place for @cache. If you add @cache, the first call raises a TypeError, because met() takes a list and a list is unhashable. If you pass a tuple instead, the calls succeed and the schedule gets worse. met() reads history, which changes at the end of every round. An answer cached in round 0 therefore comes back unchanged in a later round, after the counts it summed have grown. The cache entry’s rule, pure functions only, is the reason. A function that reads mutable state is impure, however simple its body looks.

The general version needs memory, where the circle method needs a round number. In the circle method, which pair sits where in round r follows from r alone. group_rounds() needs the history Counter, because no formula takes a round number and returns the grouping of arbitrary size that keeps every pair’s meeting count lowest. To reach round 100, group_rounds() therefore generates rounds 0 through 99 first. The circle method computes round 100 from its arithmetic alone. Recursion makes the same choice, memory for generality, when the problem outgrows a loop’s counter and needs a stack.

group_rounds() remains deterministic in the sense that matters for testing. The same students, size, and seed always produce the same infinite sequence of rounds, since random.Random(seed) draws every number from its own seeded state.

Choosing From the Toolkits

The rule for both modules is the same. Before writing a loop, ask whether the loop has a name in one of these modules. A running total is accumulate(), a width-two sliding window is pairwise(), a remainder-safe chunking is batched(), and a memoized pure function is @cache. Each of those replaces a small piece of code that works on the first input you try and fails on the empty input, the single element, or the last partial batch.

The second rule is that the pieces exist to stack. islice(count(10, 2), 5) in this chapter is two stages. A real pipeline is five or six, and it holds only the few items in flight, however long its source. Error Handling asks what such a pipeline does when one stage fails. A chain of pure functions leaves that question open.

Exercises

This chapter’s solutions give a hint, usually the shape of the code, and a full answer for each exercise.

Rewrite deep_sum() from nested_sum.py without recursion, using a list as an explicit stack. Compare the two versions for length, and name the mistakes the loop version allows that the recursive one cannot make.
functools_lru_cache.py prints CacheInfo(hits=1, misses=4, maxsize=2, currsize=2). Change maxsize to 3, predict the four numbers before running it, then run it and account for any difference.
Write batch_totals(source, n), which takes an iterator and yields the sum of each n-element batch, built only from itertools pieces and a generator expression. Show that it stays lazy by passing it count(1) and taking five values.
groupby() on unsorted input silently returns the same key more than once. Write grouped(data, key) returning a dict[K, list[V]] that cannot make that mistake, and say what it costs relative to groupby().
Decorate deep_sum() with @cache and explain the exception. What must change about the Nested alias for caching to be possible?
group_rounds() takes a seed and builds its own random.Random. Replace the seed parameter with an rng: random.Random parameter. Which property of the function does the rng parameter preserve, and which one does it leave to the caller?

Toolkits

The functools Toolkit

reduce

cache

lru_cache

partial

partialmethod

cached_property

wraps

cmp_to_key

total_ordering

singledispatch

singledispatchmethod

The itertools Toolkit

repeat

islice

count

cycle

chain

pairwise

batched

accumulate

compress

takewhile

dropwhile

filterfalse

starmap

zip_longest

groupby

tee

product

permutations and combinations