You must be authenticated to submit your files

CSE 102 – Tutorial 12 – Exceptions, functional programming

Sections tagged with a green marginal line are mandatory.

Sections tagged with an orange marginal line are either more advanced or supplementary, and are therefore considered optional. They will help you deepen your understanding of the material in the course. You may skip these sections on a first pass through the tutorial, and come back to them after finishing the mandatory exercises.

After you are finished with the tutorial, please upload your submission to Moodle by the indicated deadline.

Discussion of the tutorials with friends and classmates is allowed, with acknowledgment, but please read the Moodle page on “Collaboration, plagiarism, and AI”.

We expect you to write your solutions to all of the problems for this tutorial in a file named exfun.py and to upload it using the form below. You can resubmit your solution as many times as you like.

Upload form is only available when connected

Programming with exceptions

Python comes with a built-in function input() that reads a single line from standard input. We can learn a bit more about its behavior by typing help(input) into the Python interpreter (you’ll get slightly different output in Spyder):

>>> help(input)
Help on built-in function input in module builtins:

input(prompt='', /)
    Read a string from standard input.  The trailing newline is stripped.

    The prompt string, if given, is printed to standard output without a
    trailing newline before reading input.

    If the user hits EOF (*nix: Ctrl-D, Windows: Ctrl-Z+Return), raise EOFError.
    On *nix systems, readline is used if available.

The EOF (end-of-file) character is traditionally used by terminal programs in Unix systems to indicate that there is no more input. To observe the behavior of input() described above, execute the program

while True: print('read: ' + input())

and try entering a few lines of text, followed by an EOF character. (Press “Control-D” to generate an EOF if you are running Linux/MacOS, or “Control-Z+Return” if you are running Windows.)

  1. Write a function sum_of_input() which lets the user enter a list of integers and calculates their sum while performing validation of the input. The user should enter one number per line and indicate that they have finished typing numbers by sending an EOF. If the user enters an invalid integer, then your function must raise an exception named InvalidInput; on success, it should return the computed sum. You can write your function by completing the code below:

    class InvalidInput(Exception):
    pass

def sum_of_input() -> int:
    # do something here

    Hint: you can test that the input string is a valid integer by applying the int builtin. For example, int('-3') is accepted and returns -3, while int('green') raises a ValueError exception.

Previously in class, we saw how to define a function timed(f, x) which takes a function f and an argument x and returns a pair (v, t) consisting of the value computed by the function on the argument together with the time needed for the function call. Let’s recall the definition of this (higher-order) function, now with added type hints. You should first include the lines

import time
from typing import Callable

at the top of your file, then you can consider the following definition:

def timed[S,T](f: Callable[[S],T], x: S) -> tuple[T, float]:
    start = time.time()
    out = f(x)
    end = time.time()
    return (out, end-start)

As indicated by the type annotations, the function timed(f, x) is generic in the sense that the function f can take an input argument of an arbitrary type S (and return an arbitrary type T), so long as x has a matching type.

The bracket syntax for typing generic functions by specifying a list of type parameters was only introduced in Python 3.12. If you are using Python 3.11 or earlier you should remove the suffix [S,T] following def timed and add the following two lines beforehand

S = TypeVar('S')
T = TypeVar('T')

after making sure to import TypeVar from the typing module.

For example, f can be a function from integers to integers, or a function that takes a string and returns nothing:

In [1]: timed(lambda x:x+1, 10)
Out[1]: (11, 2.6226043701171875e-06)

In [2]: timed(print, 'hello')
hello
Out[2]: (None, 5.650520324707031e-05)

However, if the function f raises an exception on input x, then timed(f, x) will pass that exception through to the caller and abort the timing operation:

In [3]: timed(lambda x:100000**100000/x, 0)
*** ZeroDivisionError: division by zero

  1. Modify the behavior above so that if the function f raises an exception e on input x, then the timing function returns a pair (e, t) of the exception itself together with the elapsed time until the exception was raised. You should implement this behavior as a new function timed_ex(f, x), which we declare below with type annotations.

    def timed_ex[S,T](f: Callable[[S],T], x: S) -> tuple[T | Exception, float]:
    # do something here

    Examples:

    In [4]: timed_ex(lambda x:x+1, 10)
Out[4]: (11, 4.0531158447265625e-06)

In [5]: timed_ex(lambda x:100000**100000/x, 0)
Out[5]: (ZeroDivisionError('division by zero'), 0.08045339584350586)

In [6]: timed_ex(int, 'green')
Out[6]: (ValueError("invalid literal for int() with base 10: 'green'"), 1.5497207641601562e-05)

    Hint: use a try ... except ... finally block.

Programming with binary trees, revisited

Throughout this section we will work with leaf-labelled binary trees, as discussed in class. We recall the encoding below — for simplicity, we assume that all leaves are labelled by integers.

class Leaf:
    def __init__(self, value: int):
        self.value = value
    def __repr__(self):
        return f'Leaf({self.value})'

class Node:
    def __init__(self, left: 'Tree', right: 'Tree'):
        self.left = left
        self.right = right
    def __repr__(self):
        return f'Node({self.left}, {self.right})'

type Tree = Leaf | Node
# remove "type" from the previous line for Python 3.11, i.e., replace by
# Tree = Leaf | Node

You should copy these definitions into a file named trees.py. (Or alternatively, download the file here.) Then you should add the line

from trees import Leaf, Node, Tree

to your main source file.

For example, the values

example1 : Tree = Node(Leaf(0), Node(Leaf(1), Leaf(2)))
example2 : Tree = Node(Node(Leaf(0), Leaf(1)), Leaf(2))
example3 : Tree = Node(Node(Node(Leaf(0), Leaf(1)), Leaf(2)), Node(Leaf(3), Leaf(4)))
correspond to the three trees below, diagrammatically:

Also useful for testing purposes, the function cbt(n, x=0) defined below constructs a complete binary tree with \(2^n\) leaves labelled from \(x\) to \(x+2^n-1\).

def cbt(n: int, x:int = 0) -> Tree:
    if n == 0: return Leaf(x)
    else:      return Node(cbt(n-1, x), cbt(n-1, x + 2**(n-1)))
Pattern-matching and folds

  1. Making use of recursion and structural pattern-matching (i.e., Python’s match ... case ... syntax), write four functions count_nodes(t), sum_leaves(t), leaves(t), and mirror(t) with the following specifications:

    • count_nodes(t: Tree) -> int returns the number of binary nodes in the tree t;
    • sum_leaves(t: Tree) -> int returns the sum of the labels of the leaves in the tree t;
    • leaves(t: Tree) -> list[int] returns the list of leaf labels in the tree t, listed from left to right;
    • mirror(t: Tree) -> Tree returns the mirror image of the tree t.

    Examples:

    In [7]: [(count_nodes(t), sum_leaves(t), leaves(t), mirror(t)) for t in [example1,example2,example3]]
Out[7]: [(2, 3, [0, 1, 2], Node(Node(Leaf(2), Leaf(1)), Leaf(0))),
           (2, 3, [0, 1, 2], Node(Leaf(2), Node(Leaf(1), Leaf(0)))),
           (4,
            10,
            [0, 1, 2, 3, 4],
            Node(Node(Leaf(4), Leaf(3)), Node(Node(Leaf(2), Leaf(1)), Leaf(0))))]

In [8]: [count_nodes(cbt(n)) for n in range(10)]
Out[8]: [0, 1, 3, 7, 15, 31, 63, 127, 255, 511]

    Warning: Make sure that you have imported the definitions of the tree classes from the trees module as per the above instructions, rather than copying them into your exfun.py file. If you do the latter then your code will not pass the testing server!

You probably implemented all four functions from the previous exercise in a very similar way. In fact, they can all be written as folds over a binary tree in the following sense.

  1. Write a higher-order function fold_tree(t, f_leaf, f_node) which takes as input a binary tree t, a unary function f_leaf, and a binary function f_node, and computes a value as follows: the function f_leaf is applied to obtain a value for each leaf label, and these values are combined by using f_node at every binary node. For example, fold_tree(example1, g, h) should evaluate to h(g(0), h(g(1), g(2))) for any functions g and h.

    Examples:

    In [9]: fold_tree(cbt(4), lambda x:x, min)
Out[10]: 0

In [11]: fold_tree(cbt(4), lambda x:x, max)
Out[12]: 15
  1. If you have not already done so, add type annotations to your definition of fold_tree, trying to write a type for the function that is as general as possible. (You might look to the examples of timed and timed_ex above.)

  1. Reimplement the four functions that you defined above, but now just in terms of fold_tree. You should do so by defining the functions f_leaf* and f_node* referenced below or by replacing them with appropriate lambda expressions.

    def count_nodes_as_fold(t : Tree) -> int:
    return fold_tree(t, f_leaf1, f_node1)

def sum_leaves_as_fold(t : Tree) -> int:
    return fold_tree(t, f_leaf2, f_node2)

def leaves_as_fold(t : Tree) -> list[int]:
    return fold_tree(t, f_leaf3, f_node3)

def mirror_as_fold(t : Tree) -> Tree:
    return fold_tree(t, f_leaf4, f_node4)

  1. Again just using fold_tree and without making use of any auxiliary recursion, define a function eq_tree(t: Tree, u: Tree) -> bool that determines whether or not two trees t and u are structurally equal.

    Examples:

    In [13]: example1 == Node(Leaf(0), Node(Leaf(1), Leaf(2)))
Out[13]: False

In [14]: eq_tree(example1, Node(Leaf(0), Node(Leaf(1), Leaf(2))))
Out[14]: True

In [15]: eq_tree(example2, Node(Leaf(0), Node(Leaf(1), Leaf(2))))
Out[15]: False

    Hint: it may help to first define eq_tree using recursion and pattern-matching, before trying to define it as a fold. It is important to keep in mind that fold_tree can compute a value of arbitrary type, in particular it can return a function as its answer.

Rémy’s algorithm

Rémy’s algorithm is a simple and elegant iterative algorithm for generating random binary trees of a fixed size. It is a uniform generator in the sense that every binary tree is generated with equal probability.

At a high level, the algorithm can be described as follows:

  1. Start: a tree with one leaf with label 0.

  2. For i from 1 to n:

    1. Choose one existing subtree u at random. (There are 2n+1 subtrees when the tree has n internal nodes.)

    2. Toss a coin.

      1. If Heads, make u the left child of a new internal node; attach a new leaf with label i as the right child of the new internal node.

      2. If Tails, do the symmetric thing: u goes on the right and the new leaf with label i goes on the left of a new internal node.

Here is a little animation of Rémy’s algorithm being used to generate a random binary tree with 16 leaves, followed by running the algorithm in reverse to deconstruct the tree:

Observe that as we grow new leaves, we also label them in the order of creation.

  1. Write a function remy(n : int) -> Tree which uses Rémy’s algorithm to generate a uniformly random binary tree with \(n\) binary nodes and \(n+1\) leaves, with the leaves labelled \(0,\dots,n\) in order of creation.

    Examples:

    In [16]: remy(8)
Out[16]: Node(Node(Node(Node(Node(Leaf(7), Node(Leaf(3), Leaf(1))), Node(Leaf(2), Leaf(6))), Leaf(5)), Leaf(8)), Node(Leaf(0), Leaf(4)))

In [17]: remy(8)
Out[17]: Node(Leaf(1), Node(Leaf(2), Node(Node(Leaf(0), Leaf(5)), Node(Node(Leaf(8), Leaf(4)), Node(Leaf(7), Node(Leaf(6), Leaf(3)))))))

    Hint: to facilitate the step of picking a random subtree u of t and replacing it by a larger tree Node(Leaf(k), u) or Node(u, Leaf(k)), begin by writing a function that enumerates every subtree together with a pointer from its immediate parent. More precisely, write a generator function subtrees(t: Tree, pt: Node, lct: bool) -> Iterator[tuple[Tree, Node, bool]] with the following specification: subtrees(t, pt, lct) generates all triples (u, p, lc) such that u is a subtree of t, p is the immediate parent of u in t, and lc is True just in case u is the left child of p, under the assumption that t = pt.left if lct = True, and t = pt.right if lct = False. Then you can write remy(n) by repeatedly calling subtrees and updating the tree appropriately. To simplify the code, it may help to begin by creating a tree with a dummy binary node at the root and a leaf labelled 0 as (say) its right child.