Problem Set 1: An Introduction to OCaml

Due Thursday September 6, 23:59


Version: 6
Last modified: Tuesday September 4, 18:00
Changes:

Instructions

This problem set has three parts. You should write your solution to each part in a separate file: part1.txt, part2.ml, and part3.ml. To help get you started, we have provided a stub file for each part on CMS. You should download and edit these files. Once you have finished, submit your solution using CMS, linked from the course website.

Important notes about grading:

  1. Compile errors: All code you submit must compile. Programs that do not compile will probably receive an automatic zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile, than hand in a more complete file that does not compile.
  2. Naming: We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set instructions, and that you place the functions in the correct files. Otherwise you may not receive credit for a function properly written.
  3. Code style: Finally, please pay attention to style. Refer to the CS 3110 style guide and lecture notes. Ugly code that is functionally correct may still lose points. Take the extra time to think out the problems and find the most elegant solutions before coding them up. Even though only the second part of the assignment explicitly addresses the style issue, good programming style is also required for the other parts of this assignment, and for all the subsequent assignments in the rest of the semester.
  4. Late assignments: Please carefully review the course website's policy on late assignments, as all assignments handed in after the deadline will be considered late. Verify on CMS that you have submitted the correct version, before the deadline. Submitting the incorrect version before the deadline and realizing that you have done so after the deadline will be counted as a late submission.

Part 1: Expression Types (25 pts)

Give the types of each of the following OCaml expressions. For example, the type of (1, 2) is int * int.

  1. fun x y -> (x,y)::[(y,x)]
  2. [[None]]
  3. Some (fun f x -> f x x)
  4. (fun f x y z -> (x^y, z**2.)) "3110"
Give expressions that have the following OCaml types. For g and h, you may not use explicit type annotations in the expression (ex. let f (x : int) : string = ...).
  1. (string option list * float) option
  2. (int list -> int) list
  3. string list -> int option list -> string
  4. ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

Replace ??? with an expression that (1) makes the code type check correctly and (2) does not cause the code to raise an exception. Give the type of the expression you chose. 

  1. let zardoz zardoz =
  let rec foo daniel =
    let rec bar zardoz =
      if zardoz > 0 then daniel::(bar (zardoz-1)) else [] in
    bar daniel in
    let rec foo2 zardoz =
      match zardoz with
      | [] -> []
      | h::t -> (foo h) @ (foo2 t) in
    if (zardoz = foo2 [1;2;3]) then () else failwith "doh" in
    zardoz ???
  2. let x = ??? in
let rec zardoz lst =
  let rec helper lst1 lst2 =
    match lst1, lst2 with
    | h1::t1, h2::t2 -> (h1::h2)::(helper t1 t2)
    | h1::t1, [] -> [h1]::(helper t1 lst2)
    | [], [] -> []
    | _ -> failwith "Invalid args" in
  match lst with
  | h::t -> helper h (zardoz t)
  | [] -> [] in
if x = (zardoz x) && List.length x > 1 then print_string "Nice!"
else failwith "Try again."

Part 2: Code Style (15 pts)

The following function executes correctly, but it was written with poor style. Rewrite it with better style. Please consult the CS 3110 style guide. 

let rec zardoz q p =
  if ((List.length p) = 0) != false then p
  else if (((List.length p) = 1) = true) then
    if (q (List.hd p)) then [List.hd p]@[] else []
  else
    let yo = match p with |x::xs -> x | [] -> failwith "no head" in
    let lo = match p with |x::xs -> xs | [] -> failwith "no tail" in
    let ans = if (q yo) = true then yo::[]
              else [] in
    ans @ (zardoz q lo)

Part 3: OCaml Functions (60 pts)

Implement the following functions. You may use the rec keyword, but you may find some functions from the OCaml List module useful.

  1. Write a function is_unimodal : int list -> bool that takes in an integer list and returns true if the integers are unimodal. That is, they monotonically increase up to some max m, and monotonically decrease after m.

    Ex. is_unimodal [1;2;3;2] = true and is_unimodal [1;2;3;2;4] = false.

  2. Consider the distance function: 
    let distance (x1, y1) (x2, y2) = 
  sqrt ((x2-.x1) ** 2. +. (y2-.y1) ** 2.)
    Fill in the ??? below to implement the above function using higher-order functions: 
    let distance p1 p2 =
  let u f (x, y) = ??? in
  let d f (x, y) = ??? in
  let z (a, b) (x, y) = ??? in
  let s x = ??? in 
  sqrt (u (+.) (d s (d (u (-.) ) (z p1 p2))))
  3. Write a function product : 'a list -> 'b list -> ('a * 'b) list such that product l1 l2 returns the cartesian product of two sets l1 and l2, represented as lists. The cartesian product of sets X and Y is the set of all ordered pairs (x,y) where x ∈ X and y ∈ Y. Order of the final list does not matter. 
    product [1;2] ["a";"b";"c"] =
[(1,"a");(1,"b");(1,"c");(2,"a");(2,"b");(2,"c")]

product [1] [] = []

product [] [] = []
  4. Write a function choose : 'a list -> int -> 'a list list such that choose lst k returns a list of all subsets of lst with size k. Order of the final list you output and order within each subset do not matter. Your function should return the correct answer for all non-negative k. 
    choose ["A";"B";"C"] 2 = [["A";"B"];["A";"C"];["B";"C"]]

choose ["A";"B";"C"] 0 = [[]]

choose ["A";"B";"C"] 3 = [["A";"B";"C"]]

choose ["A";"B";"C"] 42 = []