Problem Set 1: An Introduction to OCaml

Due 2/3/11

Instructions

This problem set is to be done individually. No partners or collaboration, please!

The problem set has three parts. Write your solution to each part in a separate file: part1.txt, part2.ml, and part3.ml. To get you started, we have provided a stub file for each part. You should download these files from CMS and edit them. Once you have finished, submit your solutions using CMS. Please conform to our formatting instructions exactly, as we will be running a testing script on your solutions. Be sure to include your name and netid in the files.

Please make sure you submit your solutions, not the blank stubs you downloaded.

Important notes about grading:

1. Compile errors: All programs that you submit must compile (definitions in part1.txt excluded, except your definitions should load into the OCaml interpreter without error). Programs that do not compile will likely 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 and hand in a file that compiles, rather than handing in a more complete file that does not compile.
2. Missing functions: 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 past 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 it after the deadline still constitutes a late assignment.

Part 1: Expression Types (25 pts)

For a–e, supply a definition of answer_a through answer_e for which the OCaml type inference engine will infer the given type. Do not include any type declarations in your answer. Example: if the given type is bool -> int, your answer might look like

let answer = fun x -> if x then 2 else 4

# let answer = fun x -> if x then 2 else 4;;
val answer : bool -> int = 

1. int * float
2. string option list
3. int list list list -> int list
4. (int * char -> float) -> bool
5. string * int -> (string -> int -> string * int) -> int * string

For f and g, supply a definition of answer_f and answer_g that makes the given expression evaluate to 42. Include the type of the expression you chose. Example: if the given expression is

answer * (answer + 1)

let answer : int = 6

# let answer : int = 6;;
val answer : int = 6
# answer * (answer + 1);;
- : int = 42

6. let foo a b = a - b + 7 in
   let rec zardoz z =
     match z with
         x :: y :: z :: t -> foo x y + foo y z + foo z x + zardoz t
       | [] -> 0
       | _ -> failwith "sorry" in
   zardoz answer_f
   

7. let add (a, b, c) = a + b + c in
   let split (a, b) = add a * add b in
   let rec zardoz z = match z with
       [] -> []
     | h :: t -> split h :: zardoz t in
   List.hd (zardoz answer_g)
   

Part 2: Code Style (15 pts)

The following function executes correctly, but it was written with poor style. Your task is to rewrite it with better style. Please consult the CS 3110 style guide. Make sure that you use pattern matching. Try to be as concise as possible.

let rec zardoz f ls acc =
  if (((List.length ls) = 1) = true) then (f (List.hd(ls)) (acc))
  else if (((List.length ls) = 0) = true) then acc
  else let hd = List.hd(ls) in
  let tl = List.tl(ls) in
  let ans = f (hd) (acc) in
  let ans = zardoz f tl ans in
    ans

Part 3: OCaml Functions (60 pts)

1. (10 pts) Give recursive implementations using let rec of the functions split and combine in the module List. See the OCaml reference manual for the specification of these functions. Your functions should raise the same exception as the built-in OCaml versions for invalid inputs. Give a direct implementation using let rec, do not use any of the higher-order functions in the List module.
2. (10 pts) Write a function convolve : float list -> float list -> float that produces the convolution product of two discrete vectors of real numbers. The convolution product of (x₀,x₁,...,x_n) and (y₀,y₁,...,y_n) is x₀y_n + x₁y_n-1 + ... + x_ny₀. You may use let rec, but for extra karma, do not use let rec, but give a one-line definition using the higher-order functions from the List module.
3. (20 pts) Write a recursive function

   mc : int -> ('a -> 'a) -> 'a -> 'a
   

   that takes a nonnegative integer n and a function f : 'a -> 'a and produces the n-fold composition of f with itself. For example, mc 3 f x = f(f(f(x))). By convention, mc 0 f is equivalent to the identity function and mc 1 f is equivalent to just f.

   # mc 3000 ((+) 1) 3110;;
   - : int = 6110
   (* Note: (+) is shorthand for the function fun x y -> x + y. *)
   (* Thus (+) 1 is just the successor function on integers. *)
   
   # let square x = x * x;;
   val square : int -> int = 
   # mc 0 square 2;;
   - : int = 2
   # mc 1 square 2;;
   - : int = 4
   # mc 2 square 2;;
   - : int = 16
   # mc 3 square 2;;
   - : int = 256
   

4. (20 pts) Now write a function successor that, given a function equivalent to mc n as defined in the last exercise, produces a function equivalent to mc (n + 1).

   # mc 0 square 2;;
   - : int = 2
   # successor (mc 0) square 2;;
   - : int = 4
   # successor (successor (mc 0)) square 2;;
   - : int = 16
   # successor (successor (successor (mc 0))) square 2;;
   - : int = 256
   # (mc 3 successor) (mc 0) square 2;;
   - : int = 256
   

Karma (Optional)

1. Write a function make_index: (int * string list) list -> (string * int list) list that takes a list of (integer, string list) pairs and produces a list of (string, integer list) pairs such that (n, [...; s;...]) is in the input list if and only if (s, [...; n;...]) is in the output list. This function would be useful for producing the index for a book. The input list would be obtained by scanning each page n in order, creating a list of all the index words s on that page; then your function would be used to map that list to a list of index words s along with a list of all pages n on which they occur.
2. Write a function random_sublist: 'a list -> int -> 'a list that takes a list of length n and a nonnegative integer k and returns a random sublist of length k. All sublists of length k must be equally likely. The elements of the returned sublist should be in the same order as in the original list. Raise an exception if k is out of bounds.