Discussion 6: Data Classes

Data Classes

A class statement decorated with @dataclass contains a list of attribute names and type hints. Instances of that class are constructed by calling the class on values for those attributes. The attribute values are accessed using dot notation.

>>> @dataclass
    class Position:
        "A geographic position."
        lat: float
        lon: float
>>> sydney = Position(-33.87, 151.21)
>>> sydney.lat
-33.87
>>> sydney.lon
151.2

Intervals

Acknowledgements. This interval arithmetic example is based on a classic problem from Structure and Interpretation of Computer Programs, Section 2.1.4.

Introduction. Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measurements from physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision. For example, if a measured quantity x lies between two numbers a and b, Alyssa would like her system to use this range in computations involving x.

Alyssa's idea is to implement interval arithmetic as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subtracting, multiplying, or dividing two intervals is also an interval, one that represents the range of the result.

Alyssa represents an interval as an Interval dataclass that has two endpoints: a lower bound and an upper bound. Interval(1, 3) creates the interval from 1 to 3, and if x is an interval, then x.lower and x.upper are its endpoints.

from dataclasses import dataclass

@dataclass
class Interval:
    """The range of possible values of an inexact quantity, from lower to upper."""
    lower: float
    upper: float

Q1: Interval Addition

Implement add_interval, which returns an interval that contains the sum of any value in interval x and any value in interval y.

def add_interval(x: Interval, y: Interval) -> Interval:
    """Return an interval that contains the sum of any value in interval x and
    any value in interval y.

    >>> add_interval(Interval(-1, 2), Interval(4, 8))
    Interval(lower=3, upper=10)
    >>> add_interval(Interval(-3, -2), Interval(-1, 5))
    Interval(lower=-4, upper=3)
    """

Q2: Interval Multiplication

Implement mul_interval, which returns the interval that contains the product of any value in x and any value in y.

Hint: The smallest product is not always the product of two lower bounds because multiplying two negative numbers makes a positive number.

def mul_interval(x: Interval, y: Interval) -> Interval:
    """Return the interval that contains the product of any value in x and any
    value in y.

    >>> mul_interval(Interval(1, 2), Interval(3, 4))
    Interval(lower=3, upper=8)
    >>> mul_interval(Interval(1, 2), Interval(-4, -3))
    Interval(lower=-8, upper=-3)
    >>> mul_interval(Interval(2, 3), Interval(-1, 4))
    Interval(lower=-3, upper=12)
    >>> mul_interval(Interval(-2, -1), Interval(3, 4))
    Interval(lower=-8, upper=-3)
    >>> mul_interval(Interval(-2, -1), Interval(-4, -3))
    Interval(lower=3, upper=8)
    >>> mul_interval(Interval(-3, -2), Interval(-1, 5))
    Interval(lower=-15, upper=3)
    >>> mul_interval(Interval(-1, 2), Interval(4, 8))
    Interval(lower=-8, upper=16)
    >>> mul_interval(Interval(-1, 2), Interval(-4, -3))
    Interval(lower=-8, upper=4)
    >>> mul_interval(Interval(-1, 2), Interval(-3, 1))
    Interval(lower=-6, upper=3)
    >>> mul_interval(Interval(-3, 1), Interval(-1, 2))
    Interval(lower=-6, upper=3)
    >>> mul_interval(Interval(-1, 3), Interval(-2, 1))
    Interval(lower=-6, upper=3)
    """

Q3: Interval Squaring

Eva Lu Ator, another user, has noticed that mul_interval(x, x) does not always compute the square of an interval x correctly. She says that the problem is multiple references to the same interval.

The true value within a particular interval is fixed (though unknown). Combinations that refer to the same interval twice may assume two different true values for the same interval, which is an error that results in intervals that are larger than they should be.

Consider the case of x * x, where x is an interval from -1 to 2. No value within this interval, when squared, will give a negative result. However, mul_interval will allow us to choose 2 from the first reference to x and -1 from the second, giving an erroneous lower bound of -2.

Implement square_interval, which returns the smallest interval that contains the square of every value in x.

Hint: mul_interval(x, x) is correct when x does not contain 0.

def square_interval(x: Interval) -> Interval:
    """Return the smallest interval that contains the square of every value in x.

    >>> square_interval(Interval(2, 3))
    Interval(lower=4, upper=9)
    >>> square_interval(Interval(-3, -2))
    Interval(lower=4, upper=9)
    >>> square_interval(Interval(-1, 2))  # No square is negative
    Interval(lower=0, upper=4)
    >>> mul_interval(Interval(-1, 2), Interval(-1, 2))
    Interval(lower=-2, upper=4)
    >>> square_interval(Interval(-3, 1))
    Interval(lower=0, upper=9)
    """

Recommended, but more challenging (if there's time)

Q4: Sum Fun

Implement sums(n, m), which takes a total n and maximum m. It returns a list of all lists:

1. that sum to n,
2. that contain only positive numbers up to m, and
3. in which no two adjacent numbers are the same.

Important: Two lists with the same numbers in a different order should both be returned.

Here's a recursive approach that matches the template below: build up the result list by building all lists that sum to n and start with k, for each k from 1 to m. For example, the result of sums(5, 3) is made up of three lists:

• [[1, 3, 1]] starts with 1,
• [[2, 1, 2], [2, 3]] start with 2, and
• [[3, 2]] starts with 3.

Hint: Use [k] + s for a number k and list s to build a list that starts with k and then has all the elements of s.

Important: The hint references that your recursion should build each list by deciding its first element and prepending it to the result of the recursive call on the rest ([k] + rest, not rest + [k]). Both are valid ways to solve the underlying problem, but only the [k] + rest order matches the order that our doctests below expect.

>>> k = 2
>>> s = [4, 3, 1]
>>> [k] + s
[2, 4, 3, 1]

Hint (first blank): k is the first number in a list that sums to n, and rest is the rest of that list, so build a list that sums to n.

def sums(n: int, m: int) -> list[list[int]]:
    """Return lists that sum to n containing positive numbers up to m that
    have no adjacent repeats.

    >>> sums(5, 1)
    []
    >>> sums(5, 2)
    [[2, 1, 2]]
    >>> sums(5, 3)
    [[1, 3, 1], [2, 1, 2], [2, 3], [3, 2]]
    >>> sums(5, 5)
    [[1, 3, 1], [1, 4], [2, 1, 2], [2, 3], [3, 2], [4, 1], [5]]
    >>> sums(6, 3)
    [[1, 2, 1, 2], [1, 2, 3], [1, 3, 2], [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []     # The only way to sum to zero using positives
        return [sums_to_zero] # Return a list of all the ways to sum to zero
    result = []
    for k in range(1, m + 1):
        result = result + [ ___ for rest in ___ if rest == [] or ___ ]
    return result

Hint 1: Second Blank (at the end)

Hint 2: Third Blank (at the end)