Homework #1 Solution




The goal of this assignment is to help you learn the basics of programming in Haskell: data types, functions, pattern matching, and recursion.

In this assignment, you will define several functions for querying, generating, and manipulating binary trees of integers. Some of the problems will also require knowing about binary search trees.

Download this template (HW1.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.

The comment preceding each function gives a brief English description of what the function should do. Additionally, each comment contains doctestexamples 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 using the doctest tool demonstrated in class. Feel free to add more examples to improve your test coverage.

Instructions for installing doctest are on the course web page.

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 HW1.<your-username>.hs, where <your-username> is the ONID ID of the team member who submitted the file.
  • This file must compile without errors 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.