Problem Set 8

\dbox{{\bf Deliverable:} Submit your responses as a single, readable PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 4 November}. }

Tsilly Lists

Consider an alternate way of defining a list from the one we used in Class 16 and 17, where instead of prepend, lists are constructed using postpend (to avoid confusion, we call our postpended list a tsil, and reserve list for the original prepended list):

A tsil is either the empty tsil ($\lambda$), or the result of $\text{postpend}(t, e)$ for some tsil $t$ and object $e$.

1. Define the meaning of the observer operations (similarly to the beginning of Class 17) for the tsil: $\text{last}: Tsil \rightarrow Object$, $\text{frest}: Tsil \rightarrow Tsil$, and $\text{empty}: Tsil \rightarrow Boolean$.

2. Provide a definition of length for the tsil type.

3. Prove that there is an equivalent tsil for every list. (Your answer should include a clear definition of what equivalent means.)

Structural Induction on Trees

In Class 17, we defined a binary tree as either $\text{\bf null}$ or a node constructed from a binary tree, object, and binary tree. Here, we define a binary tree where the labels are natural numbers.

A tree has these operations:

\begin{equation} \begin{split} \qquad & \text{\bf null}: \text{\em Tree}
& \text{node}: \text{\em Tree} \times \mathbb{N} \times \text{\em Tree} \rightarrow \text{\em Tree}
& \text{label}: \text{\em Tree} \rightarrow \mathbb{N}
& \text{left}: \text{\em Tree} \rightarrow \text{\em Tree}
& \text{right}: \text{\em Tree} \rightarrow \text{\em Tree}
& \text{empty}: \text{\em Tree} \rightarrow { \T, \F }
\end{split} \end{equation}

The meaning of the operations is defined for all trees $t_1, t_2$, and all $n \in \mathbb{N}$, by: \begin{equation} \begin{split} \qquad & \text{label}(\text{node}(t_1, n, t_2)) \rightarrow n
\qquad & \text{left}(\text{node}(t_1, n, t_2)) \rightarrow t_1
\qquad & \text{right}(\text{node}(t_1, n, t_2)) \rightarrow t_2
\qquad & \text{empty}(\text{\bf null}) \rightarrow \T
\qquad & \text{empty}(\text{node}(t_1, n, t_2) \rightarrow \F
\end{split} \end{equation}

1. The height of a tree is the maximum distance (number of edges) from its root (the one node that has no parent node) to a leaf. Provide a constructive definition of height for our binary tree type. (Hint: the height of $\text{node}(\text{\bf null}, n, \text{\bf null})$ is $0$. The height of $\text{\bf null}$ should also be $0$.)

2. Prove that the maximum number of nodes in a binary tree of height $h$ is $2^{h + 1} - 1$.

The in-order traversal of a binary tree is a list of the node labels in the order they appear from left-to-right across the tree. For example, the in-order traversal of the tree shown below would be the list $(4, 8, 9, 13, 22, 27)$.

\begin{center} \includegraphics[scale=0.7]{./content/docs/binarytree.pdf} \end{center}

We can define $\text{traverse}$ to produce a (prepend) list as: (note the $+$ operation here is list concatenation, as defined in Class 17) \begin{equation} \begin{split} & \text{traverse}(\text{\bf null}) = \text{\bf null}
& \text{traverse}(\text{node}(t_1, n, t_2)) = \text{traverse}(t_1) + \text{prepend}(n, \text{traverse}(t_2))
\end{split} \end{equation}

1. Prove that for all trees $t$ with $n$ nodes, the result of $\text{traverse(t)}$ is a list of length $n$.

Ordered Binary Trees

We define an $\text{\em OrderedBinaryTree}$ as:

• Base case: $\text{\bf null} \in \text{\em OrderedBinaryTree}$.

• Constructor case: if $t_1, t_2 \in \text{\em OrderedBinaryTree}$ and $n \in \mathbb{N}$, and $(\text{empty}(t_1) \vee \text{maximum}(t_1) < n)$ and $(\text{empty}(t_1) \vee \text{minimum}(t_2) > n)$, then $\text{node}(t_1, n, t_2) \in \text{\em OrderedBinaryTree}$.

You may assume all the other tree operations (including $\text{traverse}$ from question 5) are defined for \text{\em OrderedBinaryTree}s also.

1. Define the $\text{minimum}: \text{\em OrderedBinaryTree} \rightarrow \mathbb{N}$ and $\text{maximum}: \text{\em OrderedBinaryTree} \rightarrow \mathbb{N}$ operations used in the definition of $\text{\em OrderedBinaryTree}$ above.

2. ($\star$) Prove that $\forall t \in \text{\em OrderedBinaryTree} \ldotp \text{traverse}(t)$ is an ordered list. (A list, $p = (p_1, p_2, \cdots, p_n)$ is an ordered list if $\forall i \in { 1, \cdots, n-1 } \ldotp pi < p{i + 1}$.)

Programming with Procedures

\dbox{These problems are {\em optional}, and provided to give students who are interested some experience with functional programming which will make you a more powerful, fashionable, and prolific programmer. You do not need to do them to earn “gold star” level credit on this assignment, and nothing on the exams will depend on them. You will receive “bonus” credit on this assignment for turning in good answers to these questions.}

These questions assume you have some experience programming in Python, but are sadly lacking in previous experience using procedures as parameters and results and realize that you cannot be a true kunoichi programmer without becoming adept with programming with procedures.

Download: pairs.py (if the link in the PDF file doesn’t work, use https://uvacs2102.github.io/docs/pairs.py).

In pairs.py, we defined make_pair and various procedures for building and using lists. You should download this code, run it in your favorite Python3 environment, and make sure you understand it.

1. Define a function list_tostring(lst) that takes a list (constructed using the list_append function from pairs.py) as its input and returns a string representation of that list. For example, list_tostring(list_prepend(1, list_prepend(2, list_prepend(3, None)))) should print out [1, 2, 3]. (You can use str(x) to turn any Python object x into a string.)

2. Define a function list_map(fn, lst) that takes as inputs a function and a list, and returns a list that is the result of applying the input function to each element of lst. For example, list_map(lambda x: x + 1, list123) should return the list [2, 3, 4].

3. Define a function list_accumulate(fn, lst, base) that takes as inputs a function, a list, and a base value, and returns the result of applying the function through the list. For example, list_accumulate(lambda a, b: a + b, lst, 0) should return the sum of all the elements in the list, and list_accumulate(lambda a, b: a * b, lst, 1) should return their product, and list_accumulate(lambda a, b: b + 1, lst, 0) should return the length of the list.

4. Define list_map (as in problem 10) using list_accumulate.