06 Structured Types, Mutability, and Higher-Order Functions (Chapter 5)

Smallest and largest common divisor, handed back together

Write a function that takes two positive whole numbers and hands back both the smallest and the largest of their common divisors above 1, and (None, None) when they have none.

First, in full, the version that glues the two numbers into a string, so that the two can be compared line for line:

def divisor_report(n1, n2):
    """Assumes n1 and n2 are ints greater than 0.
    Returns a string holding the smallest and the largest common divisor.
    """
    smallest = 0
    largest = 0
    for d in range(2, min(n1, n2) + 1):
        if n1 % d == 0 and n2 % d == 0:
            if smallest == 0:
                smallest = d
            largest = d
    return str(smallest) + ' ' + str(largest)

report = divisor_report(84, 60)
print('the report says:', report)
space = report.find(' ')
low = int(report[:space])
high = int(report[space + 1:])
print('the gap between them is', high - low)

Sample Run:

the report says: 2 12
the gap between them is 10

And now the same job with a tuple. The loop is untouched; only the last line of the body and the three lines of the caller change.

def common_divisors(n1, n2):
    """Assumes n1 and n2 are ints greater than 0.
    Returns a tuple (smallest, largest) of the common divisors greater than 1.
    Returns (None, None) when there is no such divisor.
    """
    smallest = None
    largest = None
    for d in range(2, min(n1, n2) + 1):
        if n1 % d == 0 and n2 % d == 0:
            if smallest == None:
                smallest = d
            largest = d
    return (smallest, largest)

pair = common_divisors(84, 60)
print('for 84 and 60:', pair)
print('smallest is', pair[0], 'and largest is', pair[1])
print('the gap between them is', pair[1] - pair[0])
print('for 13 and 8:', common_divisors(13, 8))

Sample Run:

for 84 and 60: (2, 12)
smallest is 2 and largest is 12
the gap between them is 10
for 13 and 8: (None, None)

Reading length, ends and membership off range(3, 30, 4)

Without listing the values by hand, say how many there are, what the first and last ones are, what a slice of the range is, and whether two given numbers are in it. Then add them up.

r = range(3, 30, 4)
print(r)
print(len(r), r[0], r[-1])
print(r[1:3])
print(19 in r, 20 in r)
total = 0
for value in r:
    total = total + value
print('total', total)

Sample Run:

range(3, 30, 4)
7 3 27
range(7, 15, 4)
True False
total 105

Why print(range(10)) does not show any numbers

A range is asked to show itself, and then asked to show itself again after being turned into a tuple.

r = range(1, 6)
print(r)
print(tuple(r))
print(r[0] + r[4])

Sample Run:

range(1, 6)
(1, 2, 3, 4, 5)
6

Six list methods in a row, with the list printed after each

Run the six operations of the first family one after another on the same list and print it each time, so that the shape of each change is visible rather than remembered.

marks = [55, 90, 70]
print(marks, len(marks))
marks.append(48)
print('after append  ', marks)
marks.insert(1, 100)
print('after insert  ', marks)
gone = marks.pop(2)
print('pop gave back ', gone, 'and left', marks)
marks.remove(48)
print('after remove  ', marks)
marks.reverse()
print('after reverse ', marks)

Sample Run:

[55, 90, 70] 3
after append   [55, 90, 70, 48]
after insert   [55, 100, 90, 70, 48]
pop gave back  90 and left [55, 100, 70, 48]
after remove   [55, 100, 70]
after reverse  [70, 100, 55]

extend against append against plus, on the same two lists

Three operations that all put two lists together, and they leave three different things behind. This is the trace the lecture spends the most time on.

L1 = [1, 2, 3]
L2 = [4, 5]
L3 = L1 + L2
print('L3 =', L3)
print('L1 =', L1)
L1.extend(L2)
print('after extend, L1 =', L1)
L1.append(L2)
print('after append, L1 =', L1)
print('length of L1 =', len(L1))
print('last item    =', L1[-1])

Sample Run:

L3 = [1, 2, 3, 4, 5]
L1 = [1, 2, 3]
after extend, L1 = [1, 2, 3, 4, 5]
after append, L1 = [1, 2, 3, 4, 5, [4, 5]]
length of L1 = 6
last item    = [4, 5]

The backup that sorted itself, and the one line that fixes it

This is the program from the top of the page. It saves the marks under a second name before sorting, prints both, and the backup comes out sorted too.

marks = [72, 45, 91, 60]
backup = marks
marks.sort()
print('sorted :', marks)
print('backup :', backup)

Sample Run:

sorted : [45, 60, 72, 91]
backup : [45, 60, 72, 91]

Now the same program with the second line changed, and a second way of writing the same fix.

marks = [72, 45, 91, 60]
backup = marks[:]
other = list(marks)
marks.sort()
print('sorted    :', marks)
print('backup    :', backup)
print('other copy:', other)

Sample Run:

sorted    : [45, 60, 72, 91]
backup    : [72, 45, 91, 60]
other copy: [72, 45, 91, 60]

A tuple that cannot be changed, holding a list that can

The trap that a past midterm paper used, with different data. A tuple holds a string, a list and a number. Three lines succeed, the fourth stops the program.

record = ('cs115', [55, 90], 2024)
print(record)
record[1].append(70)
print(record)
part = record[1][0:1]
part = part + part
print(part, type(part))
record[1] = [0]
print('this line never runs')

Sample Run:

('cs115', [55, 90], 2024)
('cs115', [55, 90, 70], 2024)
[55, 55] <class 'list'>
Traceback (most recent call last):
  File "record.py", line 8, in <module>
    record[1] = [0]
    ~~~~~~^^^
TypeError: 'tuple' object does not support item assignment

A default value that remembers the last call

A function collects values into a list, and the list is the default value of its second parameter. Called three times with one argument, it does not start empty.

def collect(value, seen=[]):
    """Assumes value is a number. Adds value to seen and returns seen."""
    seen.append(value)
    return seen

print(collect(1))
print(collect(2))
print(collect(3))

def collect_safe(value, seen=None):
    """Assumes value is a number.
    Returns a list holding value, added to seen when seen was given.
    """
    if seen == None:
        seen = []
    seen.append(value)
    return seen

print(collect_safe(1))
print(collect_safe(2))

Sample Run:

[1]
[1, 2]
[1, 2, 3]
[1]
[2]

How many times each character occurs in a phrase

Write a function that takes a string and hands back a dictionary from each character to how many times it occurs, then print the pairs in alphabetical order of the character.

def letter_counts(text):
    """Assumes text is a string.
    Returns a dictionary whose keys are the characters of text and whose
    values are how many times each character occurs.
    """
    counts = {}
    for ch in text:
        if ch in counts:
            counts[ch] = counts[ch] + 1
        else:
            counts[ch] = 1
    return counts

phrase = 'lab data'
table = letter_counts(phrase)
print(table)
for ch in sorted(table.keys()):
    print(repr(ch), table[ch])

Sample Run:

{'l': 1, 'a': 3, 'b': 1, ' ': 1, 'd': 1, 't': 1}
' ' 1
'a' 3
'b' 1
'd' 1
'l' 1
't' 1

Student records: a dictionary of lists of tuples

All four structures at once, which is what a lab question about grades actually needs. The key is a student number, the value is a list, and each item of the list is a course and a mark held together.

records = {}
records['1234'] = [('econ101', 98.0)]
records['1234'].append(('cs115', 95.0))
records['9876'] = [('cs115', 80.0)]
print(records)
print(records['1234'][1])
print(records['1234'][1][0])
total = 0
for course in records['1234']:
    total = total + course[1]
print('average', total / len(records['1234']))

Sample Run:

{'1234': [('econ101', 98.0), ('cs115', 95.0)], '9876': [('cs115', 80.0)]}
('cs115', 95.0)
cs115
average 96.5

One function that applies any other function to every item

The pattern the lecture builds this idea on. Write a function that takes a list and a function, and replaces every item by what the function makes of it. Then call it three times with three different functions, one of them your own.

def apply_to_each(values, f):
    """Assumes values is a list and f is a function of one argument.
    Replaces every item of values with f of that item and returns nothing.
    """
    for i in range(len(values)):
        values[i] = f(values[i])

def factorial(n):
    """Assumes n is an int greater than or equal to 0. Returns n factorial."""
    product = 1
    for i in range(1, n + 1):
        product = product * i
    return product

L = [1, -2, 3.33]
print('L =', L)
apply_to_each(L, abs)
print('after abs :', L)
apply_to_each(L, int)
print('after int :', L)
apply_to_each(L, factorial)
print('after fact:', L)

Sample Run:

L = [1, -2, 3.33]
after abs : [1, 2, 3.33]
after int : [1, 2, 3]
after fact: [1, 2, 6]

A conversion function chosen per item, with int as the default

A past paper used a header of this shape, with a function as the default value of the second parameter, and asked what the program printed. Here is the same idea on different data. Three branches choose three different tools for three kinds of reading.

def convert(value, using=int):
    """Assumes value is a number and using is a function of one argument.
    Returns using applied to value.
    """
    return using(value)

readings = [-40.5, 0, 12.25, -3.75, 91.6]
for i in range(len(readings)):
    if readings[i] > 50:
        readings[i] = convert(readings[i])
    elif readings[i] > -10:
        readings[i] = convert(readings[i], bool)
    else:
        readings[i] = convert(readings[i], abs)
print(readings)

Sample Run:

[40.5, False, True, True, 91]

The same six lines, on a list where two low marks are neighbours

The unlucky input. Two marks below fifty are next to each other, and one of them survives.

marks = [30, 40, 75, 20, 90]
for mark in marks:
    if mark < 50:
        marks.remove(mark)
print(marks)

Sample Run:

[40, 75, 90]

The three patterns that work, on the same unlucky list

First the while loop with a counter advanced by hand, which also hands back what it took out. This is the shape a past exam solution used for exactly this job.

def take_out_failing(marks):
    """Assumes marks is a list of numbers.
    Removes every mark below 50 from the list it was given and returns a new
    list holding the removed marks, in the order they were found.
    """
    failed = []
    i = 0
    while i < len(marks):
        if marks[i] < 50:
            failed.append(marks.pop(i))
        else:
            i = i + 1
    return failed

group = [30, 40, 75, 20, 90]
print('before:', group)
out = take_out_failing(group)
print('after :', group)
print('failed:', out)

Sample Run:

before: [30, 40, 75, 20, 90]
after : [75, 90]
failed: [30, 40, 20]

Then the version that builds a new list and changes nothing.

def passing_only(marks):
    """Assumes marks is a list of numbers.
    Returns a new list of the marks that are 50 or more and leaves the
    list it was given untouched.
    """
    kept = []
    for mark in marks:
        if mark >= 50:
            kept.append(mark)
    return kept

group = [30, 40, 75, 20, 90]
print('kept  :', passing_only(group))
print('before:', group)

Sample Run:

kept  : [75, 90]
before: [30, 40, 75, 20, 90]

And the shortest fix to the broken loop, which is to walk a clone.

group = [30, 40, 75, 20, 90]
for mark in group[:]:
    if mark < 50:
        group.remove(mark)
print(group)

Sample Run:

[75, 90]

The same mistake on a dictionary, where it stops the program

Dropping the parts that are out of stock, written the way the list version was written.

stock = {'nut': 0, 'bolt': 12, 'washer': 0}
for part in stock:
    if stock[part] == 0:
        stock.pop(part)
print(stock)

Sample Run:

Traceback (most recent call last):
  File "stock_clean.py", line 2, in <module>
    for part in stock:
RuntimeError: dictionary changed size during iteration