For Loops (Iteration)

Introduction to Software Engineering (CSSE 1001)

Introduction

A loop is a control structure that repeats code that belongs to it.

A for-loop is a control structure that, given a object called an iterator, repeats code for every member of that in order.

The general framework for writing a for loop is the following.

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

String Iteration

We can for-loop through strings character-by-character.

for x in "abcd":
    print(x)

a
b
c
d

Notice here that the order the characters were visited was left-to-right and that the looping variable maintains its value even after the loop terminates:

x

'd'

Nesting For-Loops

(digits, alphas) = ("012", "xy")
for d in digits:
    for a in alphas:
        print(d + a)

0x
0y
1x
1y
2x
2y

(digits, alphas) = ("012", "xy")
for d in digits:
    for a in alphas:
        pass
    print(d + a)

0y
1y
2y

Note

The keyword pass is the empty instruction. It has no effect and simply passes to the next line. It is required here because Python does not permit empty for loops.

(digits, alphas) = ("012", "xy")
for d in digits:
    for a in alphas:
        pass
print(d + a)

2y

Important

The names used to iterate retain their values after the for-loop exits.

Accumulators

Recall an accumulator is a variable which a loop uses to ‘accumulate’ an aggregate value.

acc = ""
for x in "abcd":
    acc = acc + x
    print(acc)

a
ab
abc
abcd

By swapping the order of arithmetic in the accumulator we can accumulate from the other side.

acc = ""
for x in "abcd":
    acc = x + acc  # Note the order change
    print(acc)

a
ba
cba
dcba

Exercise 1 Can every for loop be rewritten with only while loops?

Solution

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

Exercise 2 Can every while loop be rewritten with only for loops?

Solution

No! Consider how many times you need to repeat asking a user for correct input.

Ackchyually Professor

We can “trick” a for loop in Python to loop forever by giving it an iterator that never exhausts.

However, if we dig deep enough, we find Python has used a while loop to create that iterator.

Exercise 3 Implement the following function according to its specification.

def remove(c: str, cs: str) -> str:
    """ Return the string obtained by removing all instances 
    of <c> from <cs>.
    
    Precondition:
        len(c) == 1

    >>> remove('b', "bluey")
    'luey'
    >>> remove('b', "Bluey")
    'Bluey'
    >>> remove('b', "chilli")
    'chilli'
    >>> remove('b', "")
    ''
    """

Solution

def remove(c: str, cs: str) -> str:
    """ Removes all instances of c from the list cs.
    """
    acc = ""
    for x in cs:
        if not c == x:
            acc += x
    return acc

List Iteration

For loops iterate through the elements of the list in order.

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

a
2
c
4
e

Exercise 4 Implement the following function according to its specification.

def make_unique(xs: list[int]) -> list[int]:
    """ Return the unique elements of <.
    >>> 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]
    """

Solution

def make_unique(xs: list[int]) -> list[int]:
    """ Return the unique members of <xs>.
    """
    acc = []
    for x in xs:
        if x not in acc:
            acc.append(x)
    return acc

Ranges

Python’s range keyword allows us to quickly build an iterator for use by for-loops.

The general form is

range([start], stop[, step])

which is similar to list slicing. Note here that square braces indicate optional arguments.

Range Examples

range(10)

range(0, 10)

It has type range.

type(range(10))

range

To see what is in a range we can convert it to a list (though converting ranges to lists is usually a bad idea because ranges are a lot more memory efficient).

Omitting the optional start and optional step creates a range from zero to the mandatory stop.

list(range(10))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Including the optional start, mandatory stop, and omitting step.

list(range(2, 7))

[2, 3, 4, 5, 6]

Including the optional start, mandatory stop, and including step.

list(range(2, 7, 3))

[2, 5]

list(range(2, 7, -1))

[]

list(range(7, 2, -1))

[7, 6, 5, 4, 3]

We can use ranges to iterate through dictionaries using list indexes (though it is better not to).

xs = [11, 22, 33, 44]
for k in range(len(xs)):
    print(k, xs[k])

0 11
1 22
2 33
3 44

Enumerate

If the index of a list element is required for some computation it is best to use enumerate. Python’s enumerate simplifies index-based iteration.

It is essentially defined by

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

so we can do

xs = [11, 22, 33, 44]
for k, xk in enumerate(xs):
    print(k, xk)

0 11
1 22
2 33
3 44

for k, xk in enumerate(["Scientia", "ac", "Labore"]):
    print(k, xk)

0 Scientia
1 ac
2 Labore

UQ’s motto is “Scientia ac Labore” which translates to by means of knowledge and hard work.

Dictionary Iteration

We iterate through dictionaries key-by-key.

for key in table:
    value = table[key]

For example the following will print keys.

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

red
blue
green

Whereas this will print values.

for key in h:
    print(h[key])

1
2
3

Practice Questions

Exercise 5 (Frequency dictionary.) Implement the following function according to its specification.

def char_freq(xs: str) -> dict[str, int]:
    """ Return a dictionary mapping the characters (length one substrings) of 
    <xs> to their number of occurrences in <xs>.
    >>> char_index("")
    {}
    >>> char_index("aaAbbB")
    {'a': 2, 'b': 2, 'A': 1, 'B': 1}
    """

Exercise 6 (Capitalize Every Character) Write a function that capitalizes every character of a string.

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

Solution

def capitalize(cs: str) -> str:
    """ Capitalize every letter of a string.
    """
    ans = ""
    gap = ord('a') - ord('A')
    for x in cs:
        if 'a' <= x <= 'z':
            ans += chr(ord(x) - gap)  # capitalize
        else:
            ans += x
    return ans

Exercise 7 (Matrix Transpose) Write a function

def transpose(ass: list[list[int]]) -> list[list[int]]:

that returns the matrix transpose of \(\mathbb{A}\). Recall the transpose of a matrix is obtained by swapping its rows and columns.

\[ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}^\intercal = \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} \]

Exercise 8 (Caesar Cipher) A Caesar Cipher is a type of encryption where each letter in the plaintext is ‘shifted’ a certain number of places down the alphabet to obtain the ciphertext.

For instance, with a shift of -2 we do:

\[ \begin{align*} A &\to Y \\ B &\to Z \\ C &\to A \\ &\;\vdots \\ Z &\to X \end{align*} \]

Write code for encrypting and decrypting messages using the Caesar cipher.

In particular, write functions with the headers.

def encrypt_caesar(plaintext: str, shift: int) -> str:

def decrypt_caesar(ciphertext: str, shift: int) -> str:

Exercise 9 (Character Index Dictionary) Write a function that, when given a string, returns a dictionary whose keys are characters and values are the positions of these characters in the string.

def char_index(xs: str) -> dict[str, list[int]]:
    """
    >>> char_index("")
    {}
    >>> char_index("aaAAbbBB")
    {'a': [0, 1], 'b': [4, 5], 'A': [2, 3], 'B': [6, 7]}
    """

Solution

def char_index(xs: str) -> dict[str, int]:
    ans = dict()
    for k, x in enumerate(xs):
        if x in ans:
            ans[x].append(k)
        else:
            ans[x] = [k]
    return ans

Exercise 10 (Merge Dictionaries) Write a function that merges 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 associated with each key in the new dictionary 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}
    """

Solution

def combine(
    d1: dict[int, list[int]], 
    d2: dict[int, list[int]]
    ) -> dict[int, int]:
    ans = dict()
    for key in d1:
        if key in d2:
            ans[key] = sum(d1[key]) + sum(d2[key])
    return ans

Exercise 11 (Reverse Lookup) Write a function that does a reverse lookup.

def reverse_lookup(d: dict, item) -> list:
    """Returns all keys such that d[keys] == item

    Precondition: 
        item is immutable.

    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'bluey')
    [1, -31]
    >>> reverse_lookup({1: 'bluey', 19: 'chilli', -31: 'bluey'}, 'muffin')
    []
    """

Exercise 12 (Invert Dictionary) Write a function which inverts the keys and items of a dictionary. Since there may be many identical values, we will have to map those to lists of keys.

def invert(d: dict) -> dict:
    """Return the inverted version of d.
    >>> invert({1: 10, 2: 10})
    {10: [1, 2]}
    """

Summary

For loops enable us to iterate through anything iterable. Strictly speaking, they are not necessary (to repeat something k times we could just copy-paste k-times or use a while loop) but are used so often as to merit their introduction.