.ipynb .pdf

repository open issue

Contents

Object Oriented Programming

Start in JupyterHub

OOP: Grouping of Values and Preservation of Invariants

Classes help in different ways: They can group related values, they can keep interdependent state consistent, and can they preserve data invariants (such as non-zero denominators).

# this is something you might have seen already
def add_fractions(f1, f2):
    return (f1[0] * f2[1] + f2[0] * f1[1], f1[1] * f2[1])


# this is very difficult to read
# also, a much cleaner result would be (5, 4)
add_fractions((1, 2), (3, 4))

(10, 8)

Fractions

import functools
import math

# representational constants
# see context managers chapter for details
FRACTIONAL, DECIMAL = range(2)


# this is a module-level global variable
# see context managers chapter for details
_STRING_REPRESENTATION = FRACTIONAL


# see context managers chapter for details
class string_style:
    def __init__(self, style):
        self._new_style = style
        self._old_style = None

    def __enter__(self):
        global _STRING_REPRESENTATION
        self._old_style = _STRING_REPRESENTATION
        _STRING_REPRESENTATION = self._new_style
        return self

    def __exit__(self, tp, value, traceback):
        global _STRING_REPRESENTATION
        _STRING_REPRESENTATION = self._old_style
        # re-raise exceptions
        return False


# see decorators chapter for details on total_ordering
@functools.total_ordering
class MyFraction:
    # default parameters help with conversion from integers
    def __init__(self, num=0, denom=1):
        # prevent illegal instances from being created
        # use assert denom != 0 only if you trust the user
        if denom == 0:
            # do not print error messages
            # print("ERROR")
            # always raise exceptions
            raise ValueError("Denominator cannot be zero.")
        self._num = num
        self._denom = denom
        # if you forget this, equality test will not work consistently
        self._cancel()

    # we will improve this using properties later on
    def get_num(self):
        return self._num

    def get_denom(self):
        return self._denom

    # __eq__ is required for equality checks
    # for simplicity, this requires "other" to be a MyFraction object
    # Python's built-in Fraction supports comparisons with ints and floats, too
    def __eq__(self, other):
        # delegate to tuple equality instead of bothering with
        # return self._num == other._num and ...
        return (self._num, self._denom) == (other._num, other._denom)

    # delegate to __eq__ for consistency
    def __ne__(self, other):
        return not self.__eq__(other)

    # without aggressive cancelling,
    # MyFraction(1, 2) is not equal to MyFraction(2, 4)
    # cancelling can only be guaranteed through encapsulation
    def _cancel(self):
        gcd = math.gcd(self._num, self._denom)
        self._num //= gcd
        self._denom //= gcd

    def __lt__(self, other):
        return self._num * other._denom < other._num * self._denom

    # <= > >= generated by functools

    # do not modify self or other, always create a new object!
    def __add__(self, other):
        new_num = self._num * other._denom + other._num * self._denom
        new_denom = self._denom * other._denom
        return MyFraction(new_num, new_denom)

    # subtract and unary minus -> assignment

    # divide, invert -> assignment

    # also implement __radd__, ... if your addition supports types other than MyFraction

    # without this, MyFraction cannot be used in sets and dicts
    # this only makes sense for immutable values (see example below)
    def __hash__(self):
        return hash((self._num, self._denom))

    # the built-in print function uses "str" internally
    def __str__(self):
        # alternative implementations
        # return str(self._num) + "/" + str(self._denom)
        # return "{}/{}".format(self._num, self._denom)
        # return f"{self._num}/{self._denom}"

        # allow switching between fractional and decimal representation
        return (
            f"{self._num}/{self._denom}"
            if _STRING_REPRESENTATION == FRACTIONAL
            else f"{float(self)}"
        )

    # jupyter notebook uses "repr" for printing values
    def __repr__(self):
        # remember the repr contract https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__repr__
        return f"MyFraction({self._num!r}, {self._denom!r})"

    # this is required for
    # if MyFraction(): ...
    def __bool__(self):
        # you can use implicit conversion
        # return bool(self._num)
        # but prefer explicit when possible
        return self._num != 0

    def __float__(self):
        # remember: floats can overflow
        try:
            return self._num / self._denom
        except OverflowError as oe:
            # provide a nice error message on top of the stack trace
            raise ValueError("This fraction cannot be represented as a float") from oe

    @staticmethod
    def from_float(flt):
        num, denom = flt.as_integer_ratio()
        return MyFraction(num, denom)

    @staticmethod
    def from_str(s):
        split = s.split("/")
        if len(split) == 1:
            return MyFraction(int(split[0]))
        elif len(split) == 2:
            return MyFraction(int(split[0]), int(split[1]))
        else:
            raise ValueError("Illegal fraction format")

    def with_num(self, new_num):
        return MyFraction(new_num, self._denom)

    def with_denom(self, new_denom):
        return MyFraction(self._num, new_denom)

This fraction class is immutable by contract: Variables starting with _ are considered implementation details and not part of the public interface. Python’s built-in Fraction class (see https://docs.python.org/3/library/fractions.html) is immutable in the same way. The built-in Fraction class offers more functionality, such as support for adding fractions to integers and floats, as well as rounding. The only reason we partially re-implemented the Fraction class is to understand the underlying concepts. Always use the Fraction class from the standard library if you need to use fractions.

https://github.com/python/cpython/blob/3.9py/Lib/fractions.py

from fractions import Fraction

f = Fraction(1, 1)
# Python fractions are mutable just like ours
f._numerator = 100
f

Fraction(100, 1)

# this is why mutable data should not be used in sets
mf = MyFraction(0, 1)
s = {mf}
mf._num = 5
# mf is now MyFraction(5, 1)
MyFraction(5, 1) in s

False

Assignment OOP1

1. Rechenoperatoren Implementieren Sie die Methoden __sub__, __div__, __neg__, invert für MyFraction.

2. Vergleichsoperatoren Implementieren Sie die fehlenden Vergleichsoperatoren für MyFraction.

import functools
import math

# representational constants
# see context managers chapter for details
FRACTIONAL, DECIMAL = range(2)


# this is a module-level global variable
# see context managers chapter for details
_STRING_REPRESENTATION = FRACTIONAL


# see context managers chapter for details
class string_style:
    def __init__(self, style):
        self._new_style = style
        self._old_style = None

    def __enter__(self):
        global _STRING_REPRESENTATION
        self._old_style = _STRING_REPRESENTATION
        _STRING_REPRESENTATION = self._new_style
        return self

    def __exit__(self, tp, value, traceback):
        global _STRING_REPRESENTATION
        _STRING_REPRESENTATION = self._old_style
        # re-raise exceptions
        return False


# see decorators chapter for details on total_ordering
@functools.total_ordering
class MyFraction:
    # default parameters help with conversion from integers
    def __init__(self, num=0, denom=1):
        # prevent illegal instances from being created
        # use assert denom != 0 only if you trust the user
        if denom == 0:
            # do not print error messages
            # print("ERROR")
            # always raise exceptions
            raise ValueError("Denominator cannot be zero.")
        self._num = num
        self._denom = denom
        # if you forget this, equality test will not work consistently
        self._cancel()

    # we will improve this using properties later on
    def get_num(self):
        return self._num

    def get_denom(self):
        return self._denom

    # __eq__ is required for equality checks
    # for simplicity, this requires "other" to be a MyFraction object
    # Python's built-in Fraction supports comparisons with ints and floats, too
    def __eq__(self, other):
        # delegate to tuple equality instead of bothering with
        # return self._num == other._num and ...
        return (self._num, self._denom) == (other._num, other._denom)

    # delegate to __eq__ for consistency
    def __ne__(self, other):
        return not self.__eq__(other)

    # without aggressive cancelling,
    # MyFraction(1, 2) is not equal to MyFraction(2, 4)
    # cancelling can only be guaranteed through encapsulation
    def _cancel(self):
        gcd = math.gcd(self._num, self._denom)
        self._num //= gcd
        self._denom //= gcd

    def __lt__(self, other):
        return self._num * other._denom < other._num * self._denom

    # <= > >= generated by functools

    # do not modify self or other, always create a new object!
    def __add__(self, other):
        new_num = self._num * other._denom + other._num * self._denom
        new_denom = self._denom * other._denom
        return MyFraction(new_num, new_denom)

    # subtract and unary minus -> assignment

    def __neg__(self):
        return MyFraction(-self._num, self._denom)

    def __sub__(self, other):
        return self + (-other)

    def __mul__(self, other):
        return MyFraction(self._num * other._num, self._denom * other._denom)

    # divide, invert -> assignment
    def invert(self):
        return MyFraction(self._denom, self._num)

    def __div__(self, other):
        return self * other.invert()

    # also implement __radd__, ... if your addition supports types other than MyFraction

    # without this, MyFraction cannot be used in sets and dicts
    # this only makes sense for immutable values (see example below)
    def __hash__(self):
        return hash((self._num, self._denom))

    # the built-in print function uses "str" internally
    def __str__(self):
        # alternative implementations
        # return str(self._num) + "/" + str(self._denom)
        # return "{}/{}".format(self._num, self._denom)
        # return f"{self._num}/{self._denom}"

        # allow switching between fractional and decimal representation
        return (
            f"{self._num}/{self._denom}"
            if _STRING_REPRESENTATION == FRACTIONAL
            else f"{float(self)}"
        )

    # jupyter notebook uses "repr" for printing values
    def __repr__(self):
        # remember the repr contract
        return f"MyFraction({self._num!r}, {self._denom!r})"

    # this is required for
    # if MyFraction(): ...
    def __bool__(self):
        # you can use implicit conversion
        # return bool(self._num)
        # but prefer explicit when possible
        return self._num != 0

    def __float__(self):
        # remember: floats can overflow
        try:
            return self._num / self._denom
        except OverflowError as oe:
            # provide a nice error message on top of the stack trace
            raise ValueError("This fraction cannot be represented as a float") from oe

    @staticmethod
    def from_float(flt):
        num, denom = flt.as_integer_ratio()
        return MyFraction(num, denom)

    @staticmethod
    def from_str(s):
        split = s.split("/")
        if len(split) == 1:
            return MyFraction(int(split[0]))
        elif len(split) == 2:
            return MyFraction(int(split[0]), int(split[1]))
        else:
            raise ValueError("Illegal fraction format")

    def with_num(self, new_num):
        return MyFraction(new_num, self._denom)

    def with_denom(self, new_denom):
        return MyFraction(self._num, new_denom)

Binary Min-Heap

See https://en.wikipedia.org/wiki/Binary_heap for details

class MinHeap:
    # never use mutable default parameters such as lists
    def __init__(self, iterable=None):
        self._buffer = []
        if iterable is None:
            return
        for elem in iterable:
            self.add(elem)

    # def _sift_up(self, idx):
    #     if idx == 0:
    #         return
    #     parent = (idx - 1) // 2
    #     if self._buffer[parent] < self._buffer[idx]:
    #         return
    #     self._swap(idx, parent)
    #     self._sift_up(parent)

    # _sift_up und _sift_down are implementation details
    # and not part of the public interface
    # this is why we prefix them with "_"
    def _sift_up(self, idx):
        # prefer this over a recursive solution because of stack overflows
        while idx > 0:
            parent = (idx - 1) // 2
            # this requires only __lt__ to be defined!
            if self._buffer[parent] < self._buffer[idx]:
                break
            self._swap(idx, parent)
            idx = parent

    # def _sift_down(self, idx):
    #     left_child = 2 * idx + 1
    #     if left_child >= len(self._buffer):
    #         return
    #     smaller_child = left_child
    #     right_child = left_child + 1
    #     if right_child < len(self._buffer):
    #         if self._buffer[right_child] < self._buffer[left_child]:
    #             smaller_child = right_child
    #     if self._buffer[smaller_child] < self._buffer[idx]:
    #         self._swap(smaller_child, idx)
    #         self._sift_down(smaller_child)

    def _sift_down(self, idx):
        while True:
            left_child = idx * 2 + 1
            if left_child >= len(self._buffer):
                break
            smaller_child = left_child
            right_child = left_child + 1
            if right_child < len(self._buffer):
                if self._buffer[right_child] < self._buffer[left_child]:
                    smaller_child = right_child
            if self._buffer[smaller_child] < self._buffer[idx]:
                self._swap(idx, smaller_child)
            else:
                break

    # this is used multiple times in different places, so use a separate function
    def _swap(self, i, j):
        self._buffer[i], self._buffer[j] = self._buffer[j], self._buffer[i]

    def add(self, value):
        self._buffer.append(value)
        last_index = len(self._buffer) - 1
        self._sift_up(last_index)

    def extract_min(self):
        if not self._buffer:
            raise IndexError("Extract from empty heap")
        minimum = self._buffer[0]
        self._swap(0, -1)
        self._buffer.pop()
        self._sift_down(0)
        return minimum

    def __len__(self):
        return len(self._buffer)

    def __bool__(self):
        return bool(self._buffer)

    # for an implementation of __eq__ und __ne__
    # see the standard library chapter

    # heaps are not indexable, so do not implement this
    # def __getitem__(self, key):
    #    return NotImplemented

Assignment OOP2

1. String-Repräsentation des Heaps Implementieren Sie __str__ und __repr__ für den binären Min-Heap. Denken Sie dabei an den vorher besprochenen Contract für __repr__-Implementierungen.

class MinHeap:
    # never use mutable default parameters such as lists
    def __init__(self, iterable=None):
        self._buffer = []
        if iterable is None:
            return
        for elem in iterable:
            self.add(elem)

    # def _sift_up(self, idx):
    #     if idx == 0:
    #         return
    #     parent = (idx - 1) // 2
    #     if self._buffer[parent] < self._buffer[idx]:
    #         return
    #     self._swap(idx, parent)
    #     self._sift_up(parent)

    # _sift_up und _sift_down are implementation details
    # and not part of the public interface
    # this is why we prefix them with "_"
    def _sift_up(self, idx):
        # prefer this over a recursive solution because of stack overflows
        while idx > 0:
            parent = (idx - 1) // 2
            # this requires only __lt__ to be defined!
            if self._buffer[parent] < self._buffer[idx]:
                break
            self._swap(idx, parent)
            idx = parent

    # def _sift_down(self, idx):
    #     left_child = 2 * idx + 1
    #     if left_child >= len(self._buffer):
    #         return
    #     smaller_child = left_child
    #     right_child = left_child + 1
    #     if right_child < len(self._buffer):
    #         if self._buffer[right_child] < self._buffer[left_child]:
    #             smaller_child = right_child
    #     if self._buffer[smaller_child] < self._buffer[idx]:
    #         self._swap(smaller_child, idx)
    #         self._sift_down(smaller_child)

    def _sift_down(self, idx):
        while True:
            left_child = idx * 2 + 1
            if left_child >= len(self._buffer):
                break
            smaller_child = left_child
            right_child = left_child + 1
            if right_child < len(self._buffer):
                if self._buffer[right_child] < self._buffer[left_child]:
                    smaller_child = right_child
            if self._buffer[smaller_child] < self._buffer[idx]:
                self._swap(idx, smaller_child)
            else:
                break

    # this is used multiple times in different places, so use a separate function
    def _swap(self, i, j):
        self._buffer[i], self._buffer[j] = self._buffer[j], self._buffer[i]

    def add(self, value):
        self._buffer.append(value)
        last_index = len(self._buffer) - 1
        self._sift_up(last_index)

    def extract_min(self):
        if not self._buffer:
            raise IndexError("Extract from empty heap")
        minimum = self._buffer[0]
        self._swap(0, -1)
        self._buffer.pop()
        self._sift_down(0)
        return minimum

    def __len__(self):
        return len(self._buffer)

    def __bool__(self):
        return bool(self._buffer)

    # for an implementation of __eq__ und __ne__
    # see the standard library chapter

    # heaps are not indexable, so do not implement this
    # def __getitem__(self, key):
    #    return NotImplemented

    # solution to assignment
    def __str__(self):
        return repr(self)

    # solution to assignment
    def __repr__(self):
        # return f"<MinHeap with {len(self)} entries>"
        # this is only possible if MinHeap provides an appropriate constructor
        return f"MinHeap({self._buffer!r})"

Assignment OOP3

1. Internals von range🧑‍🏫 Implementieren Sie eine Klasse MyRange, die wie range funktionieren soll. Aus Gründen der Einfachheit beschränken wir uns auf positive Werte für skip. Orientieren Sie sich an folgender Vorgabe:

class MyRange:
    # MyRange(end)
    # MyRange(start, end)
    # MyRange(start, end, skip)
    def __init__(...):
        pass

    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__len__
    def __len__(self):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__str__
    def __str__(self):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__repr__
    def __repr__(self):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__contains__
    def __contains__(self, item):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__hash__
    def __hash__(self):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__eq__
    def __eq__(self, other):
        pass
    
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__ne__
    def __ne__(self, other):
        pass

    # r = MyRange(20)
    # r[4]     -> key has value 4
    # r[:5:-1] -> key has value slice(None, 5, -1)
    # use isinstance(key, slice) to check for slices
    # https://docs.python.org/3/reference/datamodel.html?highlight=__repr__#object.__getitem__
    def __getitem__(self, key):
        print(key)

# Slices still buggy


class MyRange:
    # MyRange(end)
    # MyRange(start, end)
    # MyRange(start, end, skip)
    def __init__(self, start, end=None, skip=1):
        if end == None:
            end = start
            start = 0
        tmp = (end - start) // skip
        end = start + tmp * skip
        self._start = start
        self._end = end
        self._skip = skip

    def __len__(self):
        return (self._end - self._start) // self._skip

    def __str__(self):
        return f"Range({self._start},{self._end},{self._skip})"

    def __repr__(self):
        return f"Range({self._start},{self._end},{self._skip})"

    def __contains__(self, item):
        if item < self._start or item >= self._end:
            return False
        if ((item - self._start) % self._skip) == 0:
            return True
        return False

    def __hash__(self):
        return hash((self._start, self._end, self._skip))

    def __eq__(self, b):
        return self._start == b._start and self._end == b._end and self._skip == b._skip

    def __ne__(self, b):
        return not (self == b)

    # r = MyRange(20)
    # r[4]     -> key has value 4
    # r[:5:-1] -> key has value slice(None, 5, -1)
    # use isinstance(key, slice) to check for slices
    def __getitem__(self, key):
        if not isinstance(key, slice):
            if len(self) <= key:
                raise IndexError("object index out of range")
            return self._start + key * self._skip

        start = key.start if key.start else 0
        stop = key.stop if key.stop else -1
        step = key.step if key.step else 1

        new_start = (
            self._end + start * self._skip
            if start < 0
            else self._start + self._skip * start
        )
        new_end = (
            self._end + stop * self._skip
            if stop < 0
            else self._start + self._skip * stop
        )
        return MyRange(new_start, new_end, self._skip * step)

Functions as Values

def largest_number(numbers):
    if not numbers:
        raise ArgumentError("Empty List")
    # largest = numbers[0] only works with indexable structures
    largest = None
    for n in numbers:
        if largest is None or n > largest:
            largest = n
    return largest

# this is the best way to do it in Python
def largest_number(numbers):
    return max(numbers)

# functions can be assigned to variables
largest_number = max

# see BAS2
def longest_string(strings):
    if not strings:
        raise ArgumentError("Empty List")
    longest = None
    length = -1
    for s in strings:
        if len(s) > length:
            length = len(s)
            longest = s
    return longest

def string_length(s):
    return len(s)


# this is the best way to do it in Python
def longest_string(strings):
    # the use of a "key" argument instead of a comparator stems from SQL
    return max(strings, key=string_length)

def longest_string(strings):
    return max(strings, key=len)

def find_string_where_letter_a_is_most_frequent(strings):
    if not strings:
        raise ArgumentError("Empty List")
    best = None
    max_count = -1
    for s in strings:
        count = s.count("a")
        if count > max_count:
            max_count = count
            best = s
    return best

def count_a(s):
    return s.count("a")


# this is the best way to do it in Python
def find_string_where_letter_a_is_most_frequent(strings):
    return max(strings, key=count_a)

# lambda functions implicitly return the value
# this reduces the function to its bare minimum
count_a = lambda s: s.count("a")


def find_string_where_letter_a_is_most_frequent(strings):
    return max(strings, key=count_a)

# lambdas can be used like any other value
def find_string_where_letter_a_is_most_frequent(strings):
    return max(strings, key=lambda s: s.count("a"))

# this is a generalized version
def find_string_where_letter_is_most_frequent(strings, letter):
    if not strings:
        raise ArgumentError("Empty List")
    best = None
    max_count = -1
    for s in strings:
        count = s.count(letter)
        if count > max_count:
            max_count = count
            best = s
    return best

def find_string_where_letter_is_most_frequent(strings, letter):
    # the lambda function captures "letter" from the enclosing scope
    return max(strings, key=lambda s: s.count(letter))

# can you write this without using lambdas?
# this does not work
def count(s, letter):
    return s.count(letter)


def find_string_where_letter_is_most_frequent(strings, letter):
    return max(strings, key=count)

# stacked functions work
def count(letter):
    def count_letter(s):
        return s.count(letter)

    # functions can be returned by other functions
    return count_letter


# as such, they require multiple invocations
count("l")("hallo")

2

def find_string_where_letter_is_most_frequent(strings, letter):
    return max(strings, key=count(letter))

# local definition also works
def find_string_where_letter_is_most_frequent(strings, letter):
    def count_letter(s):
        return s.count(letter)

    return max(strings, key=count_letter)

# this is what stacked lambdas would look like
count = lambda letter: lambda s: s.count(letter)

Less Commonly Known Basic Features Language Features I