ICS 33 Fall 2025, Exercise Set 6 Solutions

Problem 1

There are obviously a lot of reasonable experiments that one might propose to explore this, but when I consider this problem, I see a few open questions worth answering. Suppose that we have classes X and Y, along with a class Z that inherits from both X and Y.

What happens when a Z method uses super() to call a method that's defined in X, but not in Y?
What happens when a Z method uses super() to call a method that's defined in both X and Y?
What happens when a Z method uses super() to call a method that's defined in neither X nor Y?


>>> class X:
...     def only_x(self):
...         print('X.only_x')
...     def both(self):
...         print('X.both')
...
>>> class Y:
...     def only_y(self):
...         print('Y.only_y')
...     def both(self):
...         print('Y.both')
...
>>> class Z(X, Y):
...     def only_x(self):
...         super().only_x()
...     def only_y(self):
...         super().only_y()
...     def only_z(self):
...         super().only_z()
...     def both(self):
...         super().both()
...
>>> Z().only_x()
    X.only_x     # When only one base class has a method, that's what's chosen.
>>> Z().only_y()
    Y.only_y     # A method in any base class can be found with super().
>>> Z().only_z()
    Traceback (most recent call last)
      ...
    AttributeError: 'super' object has no attribute 'only_z'
                 # Calling a method that doesn't exist in any base class fails.
>>> Z().both()
    X.both       # Reasonable theory: X is listed first in Z's bases, so it wins.
>>> class Z2(Y, X):
...     def both(self):
...         super().both()    # Let's confirm that theory.
....
>>> Z2().both()
    Y.both       # Confirmed!

So, all in all, we can say that super() in the presence of multiple inheritance will allow us to access attributes of any base class, with preference given to the base classes that are listed first. (We could take this experiment further by exploring how MRO fits into this, but we might reasonably conclude at this point that MRO is how Python is deciding which base class to choose, when given a choice; that's consistent with everything else we've learned about inheritance.)

Taking it a step further

There's one additional thing that's a bit beyond the scope of the problem, but worth thinking about here, while we're on the subject. If it's our supposition that MRO is the determining factor in the meaning of super(), doesn't that mean that the same super() call in the same class might mean different things in different situations? Let's explore that, too.


>>> class W:
...     def foo(self):
...         print('W.foo')
...
>>> class X(W):
...     def foo(self):
...         print('X.foo')
...         super().foo()
...
>>> class Y(W):
...     def foo(self):
...         print('Y.foo')
...         super().foo()
...
>>> class Z(X, Y):
...     def foo(self):
...         print('Z.foo')
...         super().foo()
...
>>> X().foo()
    X.foo
    W.foo     # X.foo called W.foo; X is Y's base class
>>> Y().foo()
    Y.foo
    W.foo     # Y.foo called W.foo; W is Y's base class
>>> Z().foo()
    X.foo
    Y.foo     # X.foo called Y.foo, even though Y is not X's base class
    W.foo
>>> Z.__mro__
    (<class '__main__.Z'>, <class '__main__.X'>, <class '__main__.Y'>, <class '__main__.W'>, <class 'object'>)
              # The meaning of super() is consistent with the MRO of the
              # class of the object on which we originally called foo().

This suggests that multiple inheritance makes the use of super() a lot more brittle than we might have imagined. When X.foo says super().foo(), it's calling the version of foo belonging to the next class in the MRO of the original object that has one. So, that same line of code — super().foo() — means different things, which means that it'll be necessary to be sure that we design every foo method throughout an inheritance hierarchy to be compatible (i.e., to be able to accept the same number and types of arguments), and not to make assumptions about the order in which versions of foo may be called (e.g., X.foo can't assume that the only other foo that will be called is W.foo).

Problem 2

To fully provide hashability, the HashableByAttributes mixin class would need to provide two methods: __hash__ and __eq__.

The __hash__ method would need to determine which of an object's attributes are hashable, then combine their values together into a hash. We've seen that we can pass an iterable of hashable values to the built-in hash function and it'll do the rest, so that's the technique we'll lean on here.
The __eq__ method would need to compare the values of an object's attributes. For two objects that have identical types, we'd consider them to be equivalent if they contain the same attributes and all of those attributes have equivalent values. (A reasonable default would be to compare all of the attributes, whether they're hashable or not, since all attributes can be compared in this way.)

One way to check whether an object is hashable is to simply hash it and see whether it fails (by raising a TypeError), though I've opted for a different approach below — foreshadowing some things we'll learn in the weeks to come — by using the Hashable type from the collections.abc module instead.


from collections.abc import Hashable


class HashableByAttributes:
    def __hash__(self):
        return hash(value for value in self.__dict__.values() if isinstance(value, Hashable))


    def __eq__(self, other):
        if type(self) is type(other):
            return self.__dict__.keys() == other.__dict__.keys() and \
                   all(self.__dict__[key] == other.__dict__[key] for key in self.__dict__.keys())
        else:
            return NotImplemented

We could then inherit from this mixin class to achieve automatic hashability and equivalence.


class Person(HashableByAttributes):
    def __init__(self, name, age):
        self._name = name
        self._age = age

Once we've done that, we could write our unit tests accordingly, though I'll demonstrate a few things in the shell here and leave it at that.


>>> hash(Person('Boo', 13)) == hash(Person('Boo', 13))
    True
>>> hash(Person('Boo', 13)) == hash(Person('Alex', 47))
    False
>>> Person('Boo', 13) == Person('Boo', 13)
    True
>>> Person('Alex', 47) == Person('Boo', 13)
    False

One thing you may have noticed is that the built-in hash function doesn't return a stable result between executions of the same tests. While we're guaranteed that the same object will have the same hash for one execution of Python, there's no guarantee that it will have the same hash across multiple executions of Python. Consequently, testing of hashing would best be centered around checking whether hashes are equivalent when we expect them to be.

Problem 3

Sequential search


def sequential_search(items, key):
    def search_from(iterator, key):
        try:
            element = next(iterator)
        except StopIteration:
            return False

        if element == key:
            return True
        else:
            return search_from(iterator, key)

    return search_from(iter(items), key)

The function will require O(n) time to search a collection containing n elements.
The function will require O(n) memory to search a collection containing n elements, because there may be as many as n calls to search_from active simultaneously.
If tail call elimination was available in Python, this function would still require O(n) time, but would require only O(1) memory, since every call to search_from is a tail call.

Binary search


def binary_search(items, key):
    def search_in(items, start, end, key):
        if start > end:
            return False

        middle = (start + end) // 2

        if key == items[middle]:
            return True
        elif key < items[middle]:
            return search_in(items, start, middle - 1, key)
        else:
            return search_in(items, middle + 1, end, key)

    return search_in(items, 0, len(items) - 1, key)

The function will require O(log n) time to search a collection containing n elements. (Logarithms are the inverse of exponentiation, which make them an accurate way to describe the number of times you can take n and divide it half repeatedly until you're left with 1, which is essentially how many elements we'll need to look at here.)
The function will require O(log n) memory to search a collection containing n elements, because there may be as many as log₂n calls to search_in active simultaneously.
If tail call elimination was available in Python, this function would still require O(log n) time, but would require only O(1) memory, since every call to search_in is a tail call.