CSSE1001 — Week 5 Notes

Comprehensions

See csse1001 for course logistics — this note covers Lecture 5B’s technical content. See python-comprehensions for the full reference on comprehension syntax.

Today’s outline

  • List comprehensions
  • Dictionary comprehensions
  • Nested comprehensions
  • Filtering
  • all and any

List comprehension

Mathematics builds sets and sums this way:

\[ \{k^2 : k \in \{0, 1, 2, 3\}\} = \{0, 1, 4, 9\} \qquad \sum_{k \in \{0,1,2,3\}} k^2 = 0^2+1^2+2^2+3^2 \]

Python mirrors this directly:

>>> [k**2 for k in range(4)]
[0, 1, 4, 9]
>>> sum(k**2 for k in range(4))
14

Dictionary comprehension

>>> {x: f"value is {x}" for x in range(3)}
{0: 'value is 0', 1: 'value is 1', 2: 'value is 2'}

>>> {x: 0 for x in "ABC"}   # useful for assigning default values
{'A': 0, 'B': 0, 'C': 0}

>>> cs = "hello world"
>>> {x: cs.count(x) for x in cs}
{'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Nested comprehensions

Multiple for clauses can appear in one comprehension — order matters:

>>> [(a, x) for a in "ABC" for x in range(2)]
[('A', 0), ('A', 1), ('B', 0), ('B', 1), ('C', 0), ('C', 1)]

>>> [(a, x) for x in range(2) for a in "ABC"]
[('A', 0), ('B', 0), ('C', 0), ('A', 1), ('B', 1), ('C', 1)]

Implementing [(a, x) for a in "ABC" for x in range(2)] with a for-loop:

>>> xs = []
>>> for a in "ABC":
...     for x in range(2):
...         xs.append((a, x))

Exercise: disassemble a string

def disassemble(cs: str) -> list[str]:
    """ Returns a list of characters comprising <cs>, maintaining order.
    >>> disassemble("")
    []
    >>> disassemble("abcdef")
    ['a', 'b', 'c', 'd', 'e', 'f']
    """

With a for-loop:

>>> def disassemble(xs: str) -> list[str]:
...     ans = []
...     for x in xs:
...         ans.append(x)
...     return ans

With a list comprehension:

The companion source file defines disassemble with the comprehension return first, followed by an equivalent for-loop version left in the function body below it. That second block is unreachable dead code (the return above it always exits first) and is omitted here.

return [c for c in cs]

Exercise: more capitals than lower-case

Check if a string has (strictly) more capitals than lower-case letters, ignoring all other characters:

def more_capitals(cs: str) -> bool:
    """
    >>> more_capitals("aAbBcCdD")
    False
    >>> more_capitals("CSSE 1001")
    True
    >>> more_capitals("")
    False
    """

A useful “hack”: the integer value of True and False is 1 and 0 respectively, so sum(...) over a sequence of booleans counts how many are True:

>>> True + True + False
2

The lecture slide’s solution has a typo — it compares against 'a' <= c <= 'a' (matching only the literal character 'a') instead of 'a' <= c <= 'z' (matching any lower-case letter). The companion source file has it correct; the exercise below uses the corrected bound.

return (sum('A' <= c <= 'Z' for c in cs)
        > sum('a' <= c <= 'z' for c in cs))

Exercise: all

Check if every element of a list is truthy:

def all(xs: list) -> bool:
    """
    >>> all([1, 2, 3])
    True
    >>> all(["a", "", "c"])
    False
    >>> all([])
    True
    """
return len(xs) == sum(bool(x) for x in xs)

Exercise: any

Check if any element of a list is truthy:

def any(xs: list) -> bool:
    """
    >>> any([0, 0, 0])
    False
    >>> any(["a", "", "c"])
    True
    >>> any([])
    False
    """
return sum(bool(x) for x in xs) > 0

all and any are both included in base Python already (no import needed):

>>> xs = "HELLO WORLD"
>>> all('A' <= x <= 'Z' for x in xs)   # is every letter a capital?
False    # (space is not a capital)
>>> any('A' <= x <= 'Z' for x in xs)   # is any letter a capital?
True

Filtering

Comprehension elements may be filtered with a trailing if. E.g. the numbers less than 100 divisible by both 3 and 7:

>>> [x for x in range(101) if not (x % 3) and not (x % 7)]
[0, 21, 42, 63, 84]

The general pattern

[x for x in xs if P(x)]
[x for x in xs for y in ys if P(x, y)]
[x for x in xs for y in ys for z in zs if P(x, y, z)]
...

where P is some predicate.

Summary

Comprehensions are a rapid way of forming lists and dictionaries that would otherwise require an accumulator for-loop.

Next: week-five-exercises — practice exercises from Lecture 5C.

For-Loops

See csse1001 for course logistics — this note covers Lecture 5A’s technical content. See python-for-loops for the full reference on for-loop syntax, ranges, and enumerate.

Today’s outline

  • For-loops: definition and syntax
  • Iterating over strings, lists, and dictionaries
  • The accumulator pattern
  • range and enumerate

Definitions

Loop — a control structure that repeats code that belongs to it.

For-loop — a control structure that, given a group, repeats code for every member of that group, in order.

for <name> in <iterator>:
    <code>

String iteration (character by character)

A for-loop iterates through a string’s characters, in order:

>>> for x in "abcd":
...     print(x)
a
b
c
d
>>> x
'd'

Note the looping name (x) retains its final value after the loop exits.

Nesting for-loops

>>> (digits, alphas) = ("012", "xy")
>>> for d in digits:
...     for a in alphas:
...         print(d + a)
0x
0y
1x
1y
2x
2y

Python disallows empty for-loop bodies — use pass (the empty instruction, which has no effect) as a placeholder:

>>> for d in digits:
...     for a in alphas:
...         pass
...     print(d + a)
0y
1y
2y

Again, the names used to iterate through an iterator retain their values after the for-loop exits — by the time the outer loop’s print runs, the inner loop has already finished, leaving a at its last value ('y') each time.

The accumulator pattern

Recall an accumulator is a variable a loop uses to build up an aggregate value:

>>> acc = ""
>>> for x in "abcd":
...     acc = acc + x
...     print(acc)
a
ab
abc
abcd

Building it in reverse order just by swapping the order of concatenation:

>>> acc = ""
>>> for x in "abcd":
...     acc = x + acc
...     print(acc)
a
ba
cba
dcba

For-loops vs. while-loops

Can every for-loop be rewritten with only while-loops? Yes:

>>> for x in xs:
...     ...   # do something with x

is code-equivalent to:

>>> k = 0
>>> while k < len(xs):
...     ...   # do something with xs[k]
...     k += 1

Can every while-loop be rewritten with only for-loops? No — consider how many times you’d need to repeat asking a user for correct input (not known in advance).

Technical caveat: a for-loop can be tricked into looping forever in Python, by giving it an iterator that never exhausts. And if you dig deep enough, Python itself used a while-loop to build that iterator in the first place.

Exercise: removing characters

def remove(c: str, cs: str) -> str:
    """ Return the string with all instances of c removed from cs.
    Precondition: len(c) == 1
    >>> remove('b', "bluey")
    'luey'
    >>> remove('b', "Bluey")
    'Bluey'
    >>> remove('b', "chilli")
    'chilli'
    >>> remove('b', "")
    ''
    """

The lecture slide’s worked solution has a variable-naming slip — it reuses c as the loop variable (shadowing the parameter) and references an undefined x:

acc = ""
for c in cs:
    if not c == x:
        acc += c
return acc

The corrected version below (matching the companion source file) uses a different name for the loop variable.

Fill in the blank to complete remove:

acc = ""
for x in cs:
    if x != c:
        acc += x
return acc

List looping (index by index)

A for-loop also iterates directly through a list’s elements:

>>> xs = ['a', 2, 'c', 4, 'e']
>>> for x in xs:
...     print(x)
a
2
c
4
e

Exercise: unique elements

def make_unique(xs: list[int]) -> list[int]:
    """ Returns the UNIQUE elements of xs.
    >>> make_unique([1, 2, 3, 4])
    [1, 2, 3, 4]
    >>> make_unique([1, 2, 2, 2, 3, 1, 4, -3])
    [1, 2, 3, 4, -3]
    """
acc = []
for x in xs:
    if x not in acc:
        acc.append(x)
return acc

This is an out-of-place computation — the original list xs is not modified. An in-place change would instead modify xs directly; those are covered later, in the object-oriented part of the course.

Ranges (iterating through numbers)

range builds an iterator of numbers, with the general form range([start], stop[, step]) (square brackets denote optional arguments) — similar to list slicing:

>>> range(10)
range(0, 10)
>>> type(range(10))
<class 'range'>
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 7))
[2, 3, 4, 5, 6]
>>> list(range(2, 7, 3))
[2, 5]
>>> list(range(2, 7, -1))
[]
>>> list(range(7, 2, -1))
[7, 6, 5, 4, 3]

range is commonly used to walk through a list by index:

>>> xs = [11, 22, 33, 44]
>>> for k in range(len(xs)):
...     ...   # code involving xs[k]

Enumerate (iterating with index)

enumerate simplifies the index-and-value pattern above. Roughly:

enumerate([x0, ..., xn]) == [(0, x0), ..., (n, xn)]

(this isn’t the full story — enumerate actually returns an iterable, not a list — but the pairs it produces work the same way):

>>> xs = [1, 2, 3, 4]
>>> for k, xk in enumerate(xs):
...     ...   # code involving k and xk == xs[k]

Each (k, xk) pair is an immutable tuple:

>>> for k, x in enumerate(["Scientia", "ac", "Labore"]):
...     print(k, x)
0 Scientia
1 ac
2 Labore

(“Scientia ac Labore” is UQ’s motto — “by means of knowledge and hard work”.)

Dictionary looping (key by key)

A for-loop iterates through a dictionary’s keys:

>>> h = {"red": 1, "blue": 2, "green": 3}
>>> for key in h:
...     print(key)
red
blue
green
>>> for key in h:
...     print(h[key])
1
2
3

Exercise: character index

Write a function that returns the character frequency of a string:

def char_index(xs: str) -> dict[str, list[int]]:
    """ Return a dictionary mapping the characters (length one
    substrings) of <xs> to the list of indices at which they occur.
    >>> char_index("")
    {}
    >>> char_index("aaAbbB")
    {'a': [0, 1], 'A': [2], 'b': [3, 4], 'B': [5]}
    """

The companion source file’s signature annotates the return type as dict[str, int], but both the doctest and the actual behaviour return dict[str, list[int]] — a list of indices per character, not a single count. The annotation above has been corrected to match.

acc = {}
for k, x in enumerate(xs):
    if x in acc:
        acc[x].append(k)
    else:
        acc[x] = [k]
return acc

Summary

For-loops let us iterate through anything iterable. Strictly speaking they’re not necessary (a while-loop, or copy-pasting code k times, can always do the same job) but they’re used often enough to merit their own dedicated syntax.

Next: 2025-08-25-comprehensions (Lecture 5B) — a rapid way of building lists and dictionaries that would otherwise need an accumulator for-loop.

Week 5 Exercises — For-Loop Practice

Practice exercises for week 5 (Lecture 5C, “For Loop Practice”), following on from 2025-08-25-for-loops and 2025-08-25-comprehensions. See python-for-loops and python-comprehensions for the reference material needed to solve these.

On the HTML site, fill in each blank with your answer, then click Run Code to check it. In the PDF, the Working callout is shown as a static answer key instead (interactive checking needs a browser).

Q1 — Capitalize a string

def capitalize(cs: str) -> str:
    """ Capitalize every alphabet letter of a string.
    >>> capitalize("boom goes the dynamite!")
    'BOOM GOES THE DYNAMITE!'
    >>> capitalize("123")
    '123'
    """
acc += chr(ord('A') + ord(c) - ord('a'))

Shifting a lower-case letter up to its capital by the fixed gap between 'A' and 'a' in the character encoding.

Q2 — Matrix transpose

def transpose(xss: list[list[int]]) -> list[list[int]]:
    """ Return the transpose of xss (rows and columns swapped).
    Precondition: xss is square, i.e. len(xss) == len(xss[0]) == ...
    >>> transpose([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
    [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
    >>> transpose([[1]])
    [[1]]
    """
row = [xs[k] for xs in xss]

Row k of the transpose is column k of the original — the k-th element of every row xs in xss.

Q3 — Caesar cipher

A Caesar cipher shifts each letter a fixed number of places down the alphabet (wrapping around) to encrypt; shifting by the negative amount decrypts it again.

def caesar_cipher(cs: str, shift: int) -> str:
    """ Return a string where each character of <cs> has been shifted
    by <shift> according to the Caesar cipher.
    >>> caesar_cipher("HELLO", 3)
    'KHOOR'
    >>> caesar_cipher("KHOOR", -3)
    'HELLO'
    >>> caesar_cipher("abc xyz", 2)
    'cde zab'
    >>> caesar_cipher("cde zab", -2)
    'abc xyz'
    """

This resolves the Caesar cipher exercise posed (and left unsolved) back in 2025-08-18-non-primitive-data — same idea, a single shift parameter instead of separate encrypt/decrypt functions.

acc += chr((ord(c) - ord('a') + shift) % 26 + ord('a'))

% 26 wraps the shift around the alphabet in both directions (including for negative shifts, since Python’s % always returns a non-negative result for a positive divisor).

Q4 — Combine two dictionaries

def combine(d1: dict[int, list[int]], d2: dict[int, list[int]]) -> dict[int, int]:
    """ Return the dictionary where each key is a key that is in both
    d1 and d2. The value for each key is the sum of all the integers
    associated with that key in d1 and d2.
    >>> combine({1: [2], 4: [5, 6]}, {4: [8]})
    {4: 19}
    """
acc[key] = sum(d1[key]) + sum(d2[key])

Q5 — Reverse lookup

def reverse_lookup(d: dict, item) -> list:
    """ Returns all keys of <d> such that d[key] == item.
    Precondition: the items of <d> are immutable.
    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'bluey')
    [1, -31]
    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'muffin')
    []
    """
if d[k] == item:

Q6 — Invert a dictionary

def invert(d: dict) -> dict:
    """ Return the inverted version of d (values become keys, mapping
    to a list of the original keys that shared that value).
    >>> invert({1: 10, 2: 10})
    {10: [1, 2]}
    """
acc[val] = [key]

Reference material

Python Comprehensions

A comprehension is a concise way to build a list or dictionary directly from an iterable, without writing an explicit accumulator for-loop.

List comprehension

>>> [k**2 for k in range(4)]
[0, 1, 4, 9]

Equivalent to:

>>> acc = []
>>> for k in range(4):
...     acc.append(k**2)

sum(... for ...) (a generator expression, without the surrounding []) computes a running total directly, without building the intermediate list:

>>> sum(k**2 for k in range(4))
14

Dictionary comprehension

>>> {x: x**2 for x in range(4)}
{0: 0, 1: 1, 2: 4, 3: 9}

Useful for assigning default values across a set of keys:

>>> {x: 0 for x in "ABC"}
{'A': 0, 'B': 0, 'C': 0}

Nested comprehensions

Multiple for clauses can appear in one comprehension. The order of the for clauses matters — it matches the order they’d be nested as for-loops:

>>> [(a, x) for a in "AB" for x in range(2)]
[('A', 0), ('A', 1), ('B', 0), ('B', 1)]

>>> [(a, x) for x in range(2) for a in "AB"]
[('A', 0), ('B', 0), ('A', 1), ('B', 1)]

Filtering

A trailing if filters which elements are included:

>>> [x for x in range(101) if not (x % 3) and not (x % 7)]
[0, 21, 42, 63, 84]

The general pattern

[x for x in xs if P(x)]
[x for x in xs for y in ys if P(x, y)]
[x for x in xs for y in ys for z in zs if P(x, y, z)]
...

where P is some predicate.

True/False as 1/0

Python’s bool is a subtype of int, so True/False behave as 1/0 in arithmetic — a common idiom for counting how many elements of an iterable satisfy some condition:

>>> True + True + False
2
>>> sum(x > 0 for x in [-1, 2, 3, -4])
2

all and any

Python’s built-in all(xs)/any(xs) check whether every/some element of xs is truthy:

>>> all(['A' <= x <= 'Z' for x in "HELLO WORLD"])
False
>>> any(['A' <= x <= 'Z' for x in "HELLO WORLD"])
True

Careful: redefining a function named all or any in your own code shadows these built-ins for the rest of that scope — see 2025-08-25-comprehensions’s exercises, which do exactly this (as an exercise in reimplementing them) as a worked example.

See python-for-loops for the equivalent for-loop/accumulator forms these shortcut.

Python For-Loops

A for-loop is a loop that repeats code for every member of a group (an iterator), in order:

for <name> in <iterator>:
    <code>

Iterating over strings, lists, and dictionaries

A for-loop iterates a string’s characters, a list’s elements, or a dictionary’s keys (in each case, in order):

>>> for x in "abcd":
...     print(x)
a
b
c
d

>>> for x in ['a', 2, 'c']:
...     print(x)
a
2
c

>>> for key in {"red": 1, "blue": 2}:
...     print(key)
red
blue

The looping name retains its final value after the loop exits.

Nested for-loops

Python disallows empty loop bodies — use pass (the empty instruction, which has no effect) as a placeholder when a loop body needs no code yet:

>>> for d in "01":
...     for a in "xy":
...         pass
...     print(d + a)
0y
1y

Accumulator pattern

An accumulator is a variable a loop uses to build up an aggregate value across iterations:

>>> acc = ""
>>> for x in "abcd":
...     acc = acc + x
>>> acc
'abcd'

range

range([start], stop[, step]) builds an iterator of numbers (square brackets denote optional arguments), similar to list slicing:

>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 7))
[2, 3, 4, 5, 6]
>>> list(range(2, 7, 3))
[2, 5]
>>> list(range(7, 2, -1))
[7, 6, 5, 4, 3]

Commonly used to walk through a list by index: for k in range(len(xs)):.

enumerate

enumerate(xs) pairs each element of xs with its index, roughly enumerate([x0, ..., xn]) == [(0, x0), ..., (n, xn)] (it actually returns an iterable of tuples, not a list):

>>> for k, x in enumerate(["a", "b", "c"]):
...     print(k, x)
0 a
1 b
2 c

For-loops vs. while-loops

Every for-loop can be rewritten with only a while-loop:

>>> for x in xs:
...     ...

>>> k = 0
>>> while k < len(xs):
...     x = xs[k]
...     ...
...     k += 1

The reverse isn’t always true — a while-loop whose number of repetitions isn’t known in advance (e.g. repeatedly prompting a user until they enter valid input) can’t be rewritten as a for-loop.

Out-of-place vs. in-place

Building a new accumulator (e.g. a fresh list) without touching the original input is an out-of-place computation. An in-place change instead mutates the input directly — covered with lists and the object-oriented part of the course.

See python-comprehensions for a more concise way to write many accumulator-style for-loops.