CS 440 HW2
In this homework you will be writing and making use of higher order functions -- an important class of functions discussed in class. You'll also be writing functions that perform symbolic manipulation --- a step in the direction of implementing compilers/interpreters.
Your code for this homework will go in three different files, one for each part. You'll find stubs for each of the programming exercises. Remember to
This assignment is to be completed individually, subject to the academic integrity policy on the course website. Make sure you read and understand these.
At the end of this assignment, we will ask you to list any students you discussed the homework with, as well as any websites or other resources (please list specific URLs when applicable) you referred to.
Important notes about grading
Your submissions will be graded automatically for correctness, as well as checked by hand. Please keep our autograder (and Xincheng, who has to run it) happy:
Part 1: HOFs (20 points)
Your code for this part will go in the fine "hof.ml" IMPORTANT: In this part, you may not use recursion unless otherwise specified.
Part 2: Trees (15 points)
For this section, put your answers in
Higher-order functions aren't just for lists! Recall the algebraic data type of binary trees from lecture:
In this section, you'll implement and use higher-order functions over trees.
As an example, we implemented the function
is f v1 (f v2 u u) u.
Note that our implementation isn't tail-recursive. The Cornell book (linked from the course website) gives a tail-recursive version.
There are various ways of traversing a tree to flatten it. Consider the tree below.
An in-order traversal goes down the left subtree of a node first, then visits the node itself, then the right subtree. A in-order traversal of the above tree would visit nodes in the order 4, 2, 5, 1, 3. You can think of this as basically visiting the nodes left-to-right as they're drawn on the page.
A pre-order traversal visits the node itself, then the left subtree, then the right subtree. A pre-order traversal of the above tree visits the nodes in the order 1, 2, 4, 5, 3.
Part 3: Expression evaluation (10 points)
For this section, put your answers in "expression.ml".
In this section, we'll work with a datatype that represents arithmetic expressions of a single variable. This is actually defined as two data types:
For example, we could represent 3.0x2 + x + 2.0 as
(There are other ways we could represent it too.)
We've provided functions (below the definition of the data types, in a large block of code you can ignore) for parsing strings into expression datatypes. You may find this helpful when testing your code, unless you particularly like manually typing things like the expression above. The parser is reasonably robust, but not great, so you may need to fiddle around a bit to get your strings in the right format. We can get the above expression by running
Note that we use
Write a function
Your implementation may be recursive (it need not be tail-recursive).
As before, you can test your code by adding
This time, this will produce three separate binaries, one for each file. You can run them using the appropriate command,
A note on testing
A note on testing
These questions are worth 0 points, but are nevertheless important. Answer these questions in
When you are done with your work, make sure you have compiled your code using
Make sure to