Foundations — List - dict comprehensions and generators

This page assumes you have seen nothing. Every bracket, every keyword, every symbol the parent note (the topic note) throws at you is defined here first, anchored to a picture, and justified. If you can read from line one, you are ready. We deliberately introduce the pieces (walking, brackets, for, if, %) before we name the two constructs ("comprehension", "generator") that assemble them.

0. The most basic picture: what is an iterable?

Everything on this page depends on one idea: a thing you can walk through, one item at a time.

Look at the figure: the iterable is a row of boxes, and iteration is the arrow moving left to right, visiting one box per step. This single motion — step, get an item, step again — is the seed of everything else on the page. If you understand the arrow, you understand the whole chapter.

Basic Python containers (list, dict, tuple) are covered in 1.4.01-Basic-Python-syntaxand-data-structures; the walking-through mechanism itself is 2.3.02-Iterator-protocol.

1. The bracket family: [ ], { }, ( )

Three bracket shapes tell Python what kind of thing you want to build. Same words inside, different brackets outside → different result.

Round brackets are the tricky ones, because they are overloaded — the same ( ) means three different things:

The figure shows the same inner recipe x**2 for x in range(4) wearing three different bracket "costumes": square (a stored shelf), curly (a bag with no duplicates), round (nothing computed yet — a magic box we open later). The costume decides where the results live.

2. The symbol for ... in ... (and the block colon :)

Picture the arrow from §0 again. Each time the arrow lands on a box, the name item is re-pointed at whatever is inside that box. for is the engine that advances the arrow; in is the pointer that tells the engine which row of boxes to walk.

3. The if filter clause

The for engine visits every box. Often you want only some boxes. That is the job of if.

So the filtered form has four moving parts, left to right: the result recipe expr, the walker for item in iterable, and the optional gate if condition. Drop the if and every item passes. This exact clause is what the parent's [x**2 for x in range(10) if x % 2 == 0] uses — the % gate is defined next.

4. The symbol % — the remainder gate

The figure shows numbers dropping into a two-lane sorter: x % 2 == 0 sends evens down the left chute, odds down the right. This is exactly the if x % 2 == 0 filter from §3. We need % because a filter needs a yes/no test, and remainder is the cheapest way to ask "is this divisible?".

Note == (double equals) means "is equal to? (a question)", while a single = means "assign this name" (a command). The parent uses both; do not mix them.

5. range(...) — the number-line walker

Crucially, range never stores its numbers; it generates them on demand, so range(10**9) costs almost no memory. This is your first proof that "make-on-demand" is normal and not exotic. The parent's range(10) gives the ten numbers 0 through 9 — visit each with the arrow from §0.

6. zip(...) — walking two rows in step

The figure shows keys = ['a','b','c'] on top, values = [1,2,3] below, and the zipper pulling them into tuples ('a',1), ('b',2), ('c',3). This is precisely why the parent's dict-building example writes for k, v in zip(keys, values) — zip produces the pairs, and the two names k, v catch the two halves of each pair. Without zip you'd need index bookkeeping.

7. The colon : inside { } — set vs dict

A dict is the "phone book" picture: 'a' (name) points to 1 (number). The colon is the little arrow "name → number". This is the entire difference between a set construct {expr for ...} and a dict construct {key: val for ...}.

8. yield — the pause button (the lazy construct at last)

Now we have every piece — the arrow, the brackets, for, if. We can finally name the two assemblies.

Picture a vending machine that dispenses one snack, then waits — remembering which slot it stopped at — until you press again. That memory-between-presses is what makes generators stateful: the parent's Fibonacci example keeps a, b alive across pauses. This is why the topic can produce an endless stream (fibonacci) without ever storing it.

9. The cost symbols: $n$, $T_c$, $k$, $O(1)$

The parent's "when to use each" derivation uses four symbols. Here is each in plain words, then a careful derivation.

Derivation — the list. Building a list comprehension runs the recipe once for each of the $n$ items, so the build cost is $n\cdot T_c$, paid a single time up front. The results now sit in memory. Reading a stored item back is a direct memory lookup — it does not re-run the recipe — so each access costs $O(1)$. Doing $k$ full passes therefore adds only $k\cdot n$ cheap lookups. Total: $\text{list cost}=\underset{\text{build once}}{\underbrace{n\cdot T_c}}+\underset{\text{re-read }k\text{ times}}{\underbrace{k\cdot n\cdot O(1)}}.$

Derivation — the generator. A generator stores no results, so there is nothing to re-read. Every time you walk it, each item must be recomputed from scratch at cost $T_c$. One pass costs $n\cdot T_c$; $k$ passes cost: $\text{generator cost}=k\cdot n\cdot T_c.$

Compare. With $k=1$ (a single pass) the generator does exactly $n\cdot T_c$ and stores nothing — it wins on memory at no extra time. With $k>1$ the generator pays the full $T_c$ again on every pass, while the list paid $T_c$ only once and then re-reads cheaply. So: many passes → list; single pass or data-too-big-to-store → generator.

Prerequisite map

Each foundation on the left feeds the topic on the right. If any left-hand node is fuzzy, re-read its section above before touching the parent note.

Where these lead next

• The remainder/filter machinery reappears when you split data in 1.5.01-Batch-processing-and-mini-batches.
• Lazy streaming over files powers 1.4.04-File-IO-and-data-loading.
• The for ... in engine is formalised in 2.3.02-Iterator-protocol.
• Vectorised alternatives (doing x**2 on a whole array at once) live in 1.4.02-NumPy-arrays-and-vectorization.

Equipment checklist

Cover the right side; say it out loud before revealing.