Problem Set 7

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

Tsilly Lists

Consider an alternate way of defining a list from the one we used in Class 15 and 16, 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 following operations (similarly to the beginning of Class 16) for the tsil: $\text{last}: Tsil \rightarrow Object$, $\text{frest}: Tsil \rightarrow Tsil$, and $\text{empty}: Tsil \rightarrow Boolean$.

2. Provide a constructive definition of length for the tsil data 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 16, we defined a recursive data type, lists, that only relied on one (smaller) list in its recursive definition. Here we give a recursive definition for the data type of \emph{binary} trees. In a binary tree, each node can have 0,1,or 2 children, and each node has a label of its own that (in this case) is always a natural number.

The main two operators corresponding to the base and the construct cases are are:

\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} \end{split} \end{equation}

We also define the following operations on binary trees.

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} \text{label}: \text{\em Tree} \rightarrow \mathbb{N} \colon \qquad & \text{label}(\text{node}(t_1, n, t_2)) \rightarrow n
\text{left}: \text{\em Tree} \rightarrow \text{\em Tree} \colon \qquad & \text{left}(\text{node}(t_1, n, t_2)) \rightarrow t_1
\text{right}: \text{\em Tree} \rightarrow \text{\em Tree} \colon \qquad & \text{right}(\text{node}(t_1, n, t_2)) \rightarrow t_2
\text{empty}: \text{\em Tree} \rightarrow { \T, \F } \colon \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. For example the hight of the tree at the bottom of this page is 2. 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 follows (note the $+$ operation here is list concatenation, as defined in Class 16) : \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

Here we would like to define an $\text{\em OrderedBinaryTree}$ as a data type where for each node with label $n$, all of the children in the left sub-tree have labels smaller than $n$, and all the children in the right sub-tree have labels larger than $n$.

• 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, snazzy, 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.