Skip to content

Homework 2

Due: Sunday, September 21st at 11:59pm.

Submission Instructions

Start with the template code here.

  • Replace each failwith "TODO" with your solution. (failwith has type string -> t for any type t, and throws an exception when it evaluates. Your solution to each problem should not include failwith.)
  • Be sure to test your solutions in utop or in tests alongside your submission. To load your file into utop, use #use "hw2.ml";;.
  • Submit your version of hw2.ml to the HW2 assignment on Gradescope. Your version of hw2.ml should include (at least) the functions above, with the same types as above.
  • This assignment is partially autograded, which will give you immediate feedback about the correctness of your code via random testing. You may submit as many times as you would like. We will only manually grade the last submitted assignment. Please ensure your code type checks locally before you submit it (i.e., loading it into utop does not fail).
  • At the top of the template file, there is a comment for you to write in approximately how many hours you spent on the assignment. Filling this in is optional, but helpful feedback for the instructors.

Q1: Defining concat (Autograded)

Using recursion, define the function concat : string list -> string that concatenates a list of strings in order. The empty list should produce the empty string "". Some example unit tests: 

concat [] = ""
concat [""; "a"] = "a"
concat ["abc"; "def"] = "abcdef"
concat ["a"; ""; "b"; "cd"] = "abcd"

Q2: Testing a list: alternating (Autograded)

Implement a function alternating : int list -> bool that tests whether the list alternates between even and odd (beginning at even). Your function should return true on the empty list, and false on any list that begins with an odd number. (For checking if x is even, you can test whether x mod 2 equals 0.)

Some example unit tests which should pass of your implementation: 

alternating [] = true
alternating [1] = false
alternating [4] = true
alternating [1;2;3] = false
alternating [2;3;4] = true
alternating [2;3] = true
alternating [2;2] = false

Note

You may find it useful to use mutual recursion, which defines two recursive functions in terms of each other. You do this by defining the first function using let rec, and the others by and. For example: 

let rec f (x : int) : int = 
  if x <= 0 then 1 else g (x - 1) + 1
and g (x : int) : int = 
  x + f (x - 1)
Note how f calls g and g calls f. (If you have been writing ;; at the end of your definitions, take note that this example won't work if we put ;; between the definition of f and g.)

If f and g have the same input and outupt types, we can alternatively eliminate the mutual recursion by using a parameter that keeps track of which function we are: 

(* 
  - which = true: we are behaving like `f`
  - which = false: we are behaving like `g`
*)
let rec fg (which : bool) (x : int) : int = 
  if which then 
    (* Behave as f *)
    if x <= 0 then 1 else fg false (x - 1) + 1
  else 
    (* Behave as g *)
    x + fg true (x - 1)

let f : int -> int = fg true
let g : int -> int = fg true

Q3: Generator, stringifier for int_tree (Manually graded)

For this question and the rest of the HW, consider this data structure: 

type int_tree =
  | Leaf
  | Node of (int_tree * int * int_tree)
This is the type of a binary tree where leaves hold no data, while internal nodes hold an int in addition to their subtrees.

First, define a generator (random sampler) for int_tree: 

let rec gen_int_tree (depth : int) (bound : int) : int_tree = failwith "TODO"

This generator should create a tree of depth depth (returning Leaf if depth <= 0, which counts as depth zero) and fill each node with an integer using Random.int, with integer bound bound. Your implementation should create trees that are balanced: for each node, the left subtree should have the same "shape" (number of nodes and branching structure) as the right subtree.

Next, define a stringifier for int_tree: 

let rec string_of_int_tree (t : int_tree) : string = failwith "TODO"
Your stringifier may choose any format, as long as it displays all the data in the tree. string_of_int will be useful here.

Q4: Mapping over an int_tree (Autograded)

The map : (int -> int) -> int list -> int list function for lists applies the argument function to each element of the list, creating a new list of the same length: 

map (fun (x : int) -> x + 1) [1; 2; 3] = [2; 3; 4]
map (fun (x : int) -> x * 2) [] = []
map (fun (x : int) -> x * 2) [42] = [84]

In this problem, you will define a similar function for int_tree:

let rec map_int_tree (f : int -> int) (t : int_tree) : int_tree = failwith "TODO"
which returns a tree by applying f to each int in the original tree. Some example tests: 
map_int_tree (fun (x : int) -> x + 3) Leaf = Leaf
map_int_tree (fun (x : int) -> x + 3) 
  (Node (Node (Leaf, 0, Leaf), 3, Node (Leaf, 7, Leaf))) 
  =
  (Node (Node (Leaf, 3, Leaf), 6, Node (Leaf, 10, Leaf)))

Q5: Composing int_tree_map with itself (Manually graded)

Similar to what we did for lists in class, we can create a testing harness to test properties about int_trees: 

let rec tester (prop : int_tree -> bool) (n : int) = 
  if n <= 0 then 
    print_endline "All tests succeeded"
  else 
    let t = gen_int_tree 4 1000 in
    if prop t then 
      tester prop (n - 1)
    else 
      print_endline ("Found counterexample: " ^ string_of_int_tree t)
This testing harness runs prop on a random int_tree a maximum of n times in a row. If all tests succeed, then we have successfully tested prop to always return true on our random inputs; if any test fails, we end and print the counter-example.

In this problem, define a logical specification that states that, given an int_tree t, mapping it using map_int_tree twice in a row with the function (fun (x : int) -> x + 1) is the same as mapping it once with the function (fun (x : int) -> x + 2). 

let map_2_spec (t : int_tree) : bool = failwith "TODO"

This is a theorem that should be true about map_int_tree. You can test the truthiness of your version of map_2_spec by calling tester against it; if the tester finds a counter-example, there is likely an issue with your implementation of map_2_spec or map_int_tree. Take note that if tester says that all tests succeeded, this only means that your version of map_2_spec is true; not that it is the correct one! (We will not grade you on whether you called tester on map_int_tree, but doing so will help you find potential bugs.)

Q6: Maximum of int_tree (Autograded)

Define a function int_tree_max : int_tree -> int option that returns the maximum int in the tree, if it exists. 

int_tree_max Leaf = None
int_tree_max (Node (Leaf, 2, Node (Leaf, 3, Leaf))) = Some 3

Q7: Defining whether an int_tree is sorted (Manually graded)

An int_tree is sorted if, for all nodes Node(x, i, y) in the tree, i is greater than or equal to all integers stored in x and less than or equal to all integers stored in y. For example, Node(Node(Leaf, 0, Leaf), 1, Leaf) is sorted, but Node(Leaf, 1, Node(Leaf, 0, Leaf)) is not.

Implement a boolean test for sorted: 

let rec sorted (t : int_tree) : bool = failwith "TODO"
Using int_tree_max will be helpful here.

Q8: Testing a theorem about sorted (Manually graded)

Implement the property sorted_plus1_spec to state that given an int_tree t: if t is sorted, then the tree obtained by mapping t by fun (x : int) -> x + 1 (via map_int_tree) is also sorted.

let sorted_plus1_spec (t : int_tree) : bool = failwith "TODO"

As in Q5, you can use tester to test if sorted_plus1_spec always holds.

Q9: Another theorem about sorted (Manually graded)

Implement the property sorted_new_node_spec to state that given an int_tree t and an integer i: if t is sorted and has a maximum Some v (computed from int_tree_max), and if i is greater than or equal to v, then Node(t, i, Leaf) is also sorted.

let sorted_new_node_spec (t : int_tree) (i : int) : bool = failwith "TODO"

As in Q5, you can use tester to test if new_node_spec always holds. (To use this one with tester, you have to create a suitable prop of type int_tree -> bool. This prop will need to internally sample a random integer i and call sorted_new_node_spec using that i.)