Homework #2 Solution

Description

How to Submit
• Submit one solution per team (each team can have 1–3 members), through TEACH. Put the name and ONID ID of every team member in a comment at the top of the file.
• Your submission should consist of one file named HW2.<your-username>.hs, where <your-username> is the ONID ID of the team member who submitted the file.
• Your file must compile without errors or warnings in GHCi. Put all non-working parts of your solution in comments! If your file does not compile, the TAs will not evaluate it.
• Please preserve the existing doctest comments in the template (the lines starting with >>> and the results underneath). This will help the TA during grading.
• If you can’t solve a problem, you can get partial credit by describing in comments what you tried and where you got stuck.
Description
The goal of this assignment is to further develop your functional programming skills. In particular, to get more practice working with data types and defining functions using pattern matching and recursion.
In this assignment, you’ll again be working with binary trees. However, the data type you’re using in this assignment is different from the tree data type from Homework 1 in two ways: First, the type of value stored in each node is now parameterized rather than fixed to Int. This means that you can have trees of integers, boolean values, functions, or any other Haskell type. Second, the unary Leaf constructor has been replaced by a binary End constructor. This is more flexible since it doesn’t require every node in a tree to have either zero or two children.
Download this template (HW2.template.hs), rename it as described above, and enter your solutions directly in the file. For each undefined function in the template, you should:
1. Write the appropriate type of the function.
2. Implement the function.
As before, the comment preceding each function gives a brief English description of what the function should do. Additionally, each comment contains doctest examples that illustrate the intended behavior of the function. You can use these examples both to help understand the intended behavior of the function, and as unit tests.
I’ve given the type of the last function you must implement since it involves a type class constraint, which we haven’t covered yet in class. The constraint Eq a => means that the function will work for all trees that contain values that can be checked for equality (like integers and booleans).
Besides Haskell lists and the types defined in the template, you’ll also need Haskell’s Maybe data type. We covered this briefly in class, but if you need a refresher, see Chapter 3 of Brent Yorgey’s Intro to Haskell.