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 git add all three of these files before committing and pushing your final submission.

Collaboration

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:

1. Do not change or remove any lines that start with (*>*.

2. Do not change the names or types of any functions defined in the starter code. This includes adding rec to functions that don't have it.

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.

1. join takes a string sep and a string list l and returns a string consisting of all of the strings of l concatenated, and separated with sep. It's OK if there's one extra sep at the end (not the beginning). e.g.,

    # join ", " ["Python"; "Java"; "OCaml"];;
    - : string = "Python, Java, OCaml, "
   
    # join ", " [];;
    - : string = ""
   

2. concat takes a list of lists and returns one list with all of the elements of all of the original list, e.g.,

    # concat [[1; 2; 3]; [4]; [5; 6]; []];;
    - : int list = [1; 2; 3; 4; 5; 6]
   
    # concat [];;
    - : 'a list = []
   
    # concat [[]; []];;
    - : 'a list = []
   

3. run_length_encode is the same as on HW1, but this time you'll implement it with higher-order functions instead of recursion.

   Returns a run-length encoding of the argument list. Run-length encoding stores each value together with the number of times it appears (contiguously) — in this way, a value that is repeated multiple times can be more efficiently represented. E.g.,

    # run_length_encode ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'];;
    - : (char * int) list = [('a', 5); ('b', 3)]
   
    # run_length_encode [1; 1; 6; 6; 6; 6; 2];;
    - : (int * int) list = [(1, 2); (6, 4); (2, 1)]
   
    # run_length_encode [];;
    - : ('a * int) list = []
   

   You may assume that adjacent elements can be compared for equality using =.

4. run_length_decode is the same as on HW1, but this time you'll implement it with higher-order functions instead of recursion.

   Given a run-length encoded list argument, returns the original list. E.g.,

    # run_length_decode [('a', 5); ('b', 3)];;
    - : char list = ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b']
   

5. (BONUS - 2 points) Write a tail-recursive version of List.fold_right without using List.fold_left or List.rev (or re-implementing either of these; your function should make just one pass over the list). Other than tail recursion, your function should behave identically to List.fold_right. You may use recursion for this question only.

   Hint: Try changing the function you pass to the recursive application.

   Note: This, like other bonus tasks we'll occasionally include in assignments, is quite difficult and is worth a small number of bonus points. Try it for an extra challenge if you want (probably after completing the rest of the assignment).

Part 2: Trees (15 points)

For this section, put your answers in trees.ml. IMPORTANT: In this part, you may not use recursion unless otherwise specified.

Higher-order functions aren't just for lists! Recall the algebraic data type of binary trees from lecture:

    type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

In this section, you'll implement and use higher-order functions over trees.

As an example, we implemented the function tree_fold : 'a tree -> 'b -> ('a -> 'b -> 'b -> 'b) that folds over trees like List.fold_right folds over lists. For example,

    tree_fold (Node (v1, Node (v2, Leaf, Leaf), Leaf)) u f

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.

1. Implement the function tree_map : 'a tree -> ('a -> 'b) -> 'b tree that returns a tree with the same structure as the original tree, but with the given function applied to every node. Use tree_fold. Do not use recursion.

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.

1. Implement the function inorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an in-order traversal. (So, inorder applied to the above tree would give [4;2;5;1;3]. Use tree_fold. Do not use recursion.

2. Implement the function preorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an pre-order traversal. (So, preorder applied to the above tree would give [1;2;4;5;3].) Use tree_fold. Do not use recursion.

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:

    (* Binary operators. *)
    type binop = Add | Sub | Mul | Div | Pow ;;
    type expression =
      | Num of float
      | Var
      | Binop of expression * binop * expression
      | Neg of expression
    ;;

Num a represents the floating-point number a. Var represents the only variable, which we'll call x. Binop (e1, o, e2) represents a binary operation on subexpressions e1 and e2. The binary operation is given by o of type binop which can be Add, Sub, Mul, Div, or Pow. Neg e is the negation of e (e.g., Neg (Num 1.0) represents -1).

For example, we could represent 3.0x² + x + 2.0 as

    Binop (Binop (Neg (Num 3.0), Mul, Binop (Var, Pow, Num 2.0)),
           Add,
           Binop (Var,
                  Add,
                  Num 2.0)
          )

(There are other ways we could represent it too.)

Parsing expressions

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

    parse "~3.0*x^2 + x + 2.0";;

Note that we use ~ instead of - to represent negation. This lets the parser distinguish between negation and subtraction. We also need to explicitly include the * between ~3.0 and x^2 rather than just concatenating the two like we do when writing math normally.

Exercise

Write a function evaluate : expression -> float -> float. The application evaluate e v should substitute v for x in the given expression and evaluate it to a float. For example,

    # evaluate (parse "~3.0*x^2 + x + 2.0") 0.0
    - : float = 2.0

    # evaluate (parse "~3.0*x^2 + x + 2.0") 1.0
    - : float = 0.0

    # evaluate (parse "~3.0*x^2 + x + 2.0") 2.0
    - : float = -8.0

Your implementation may be recursive (it need not be tail-recursive).

Testing

As before, you can test your code by adding assert statements after each function, then compiling the program using

make

This time, this will produce three separate binaries, one for each file. You can run them using the appropriate command, ./hof, ./trees and ./expression.

A note on testing trees.ml: We defined trees t1, t2, and t3, which you can use in tests. t3 is the tree shown in the picture above.

A note on testing expression.ml: It's not a good idea to use = on floats (as we discussed in class, 1.0 as a floating point number can easily become 1.00000000001 for reasons outside your control, and those won't be seen as equal). Instead, we've provided the float_eq function for you to use in assert tests. float_eq a b returns true if a and b are close to each other, even if they're not exactly equal.

Extra questions

These questions are worth 0 points, but are nevertheless important. Answer these questions in expression.ml.

1. Fill in students_collaborated_with with a list of strings giving the names of other students with whom you discussed this homework, and urls_consulted with a (string) list of web URLs or other resources you consulted while doing the homework. Be as specific and thorough as possible, within reason. Remember that this helps clear up confusion if we have any questions about your work. If either answer is "None", you should still fill in the empty list ([]).

2. Also fill in minutes_worked with the (approximate) number of minutes you spent working on this assignment. Your honest feedback will help us with future assignments.

Submission

When you are done with your work, make sure you have compiled your code using make (and ideally tested it using the instructions above). Submissions that do not compile will receive no credit. When finished, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version).

Make sure to git add all three .ml files before you commit so we see your changes, and make sure to git push. Double check Github and make sure you can see your latest code. There are no automatic tests this time.