Skip to content

Homework 2

Due: Friday, Jan 23rd 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 (10pts, 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 (10pts, 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 (10pts, 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 (10pts, 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: Maximum of int_tree (10pts, 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

Q6: Defining whether an int_tree is sorted (10pts, 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.