Problem Set 1: An Introduction to OCaml

Due Thursday January 31, 23:59

Version: 6
Last modified: Tuesday, January 29, 19:00
Changes:

• Version 6: Fixed typos in string_rev "zardoz" and function declaration of int_of_roman
• Version 5: Explicitly banned imperative features
• Version 4: Fixed the dot function in Part 3
• Version 3:
  • Added explicit restriction against using type constraints in Part 1
  • Updated 1.g. (accidentally had old version before)
  • Updated 1.j. (accidentally had old version before)
• Version 2: Fixed the second example in the roman numeral problem

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.

For this problem set, you are restricted to the functional programming. OCaml has imperative features like mutable arrays and while loops. You may not use these or any other state-changing constructs. Contact the course staff if you are uncertain whether a given feature is imperative, but as a general rule, if it returns unit it is not functional. To reiterate:

NO SIDE EFFECTS

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. ("(3110, 4410)", [[1]; [2; 3]; [4; 5; 6]])
2. (fun n -> n + 4) 7
3. [Some (fun x y z -> [(x, y); z]); None]
4. fun x -> function (y, z) -> (fun y z -> y + z) x

5. 'a option option -> 'a
6. string option list -> int -> string * string list
7. ('a -> 'a -> 'b) -> 'a -> ('a -> 'b) * 'b
8. 'a list -> 'b list -> ('a -> 'b -> 'a * 'b list)

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.

9. let rec zardoz foo =
     match foo with
     | ((x, y), z)::t -> x (y + z + (zardoz t))
     | _ -> 1 in
   zardoz ???  

10. let lst = ??? in
    let num n = match n with (a, b, c) -> a / ((String.length b) * c) in
    let sneaky z = match z with (a, b) ->
      let c = num a in
      let d = num b in
      (max c d) / (min c d) in
    let rec zardoz z =
      match z with
      | [] -> []
      | h :: t -> (sneaky h) :: (zardoz t) in
    let connery z =
      if z = [] then failwith "too easy" else zardoz z in
    connery lst

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 zardoz zardoz yolo =
  let rec roll desert turn around =
    let up = fun x -> x in
    let never = if List.length turn > 0 = true then List.tl turn else [] in
    let gonna = List.length turn in 
    let give = let you = 42 in up in
    let lie = give gonna in
    if lie = 1 then desert (List.hd turn) around else
    if lie = 0 = false then desert (List.hd turn) (roll desert never around) else
    if List.length turn = 0 then around else failwith "zardoz"
  in
  let rick = ([], []) in
  match yolo with [] -> rick
  | _ -> roll (fun for_ (so, long) -> (function true -> (for_::so, long)
         | false -> (so, for_::long)) (zardoz for_)) yolo rick

Part 3: OCaml Functions (60 pts)

1. Complete the following function to reverse a string:

   let string_rev (s : string) : string = ...

   Examples:

   string_rev "zardoz" = "zodraz"
   string_rev "radar" = "radar"
   string_rev "" = ""

2. Consider the dot function:

   let dot (x1, x2) (y1, y2) = x1 *. y1 +. x2 *. y2

   Fill in the ??? below to implement the above function using higher-order functions:

   let dot x y =
     let compose f g x = ??? in
     let uncurry f (x, y) = ??? in
     let distribute f (x, y) = ??? in
     let zip_pairs (a, b) (x, y) = ??? in
     let pairwise_mult x y =
       (distribute (uncurry ( *. )) (zip_pairs x y)) in
     (compose (uncurry (+.)) (uncurry pairwise_mult)) (x, y)

   (Of course this is just a puzzle exercise, not an example of good style with higher-order functions.)
3. Roman Numerals
   A roman numeral can be defined as a list of characters from the set {I, V, X, L, C, D, M}. We can define this in OCaml as:

   type numeral = I | V | X | L | C | D | M
   type roman = numeral list

   In any number written with Roman numerals, the numerals are usually ordered from greater valued characters to smaller valued characters. For example, MMXII is a valid number, but IIXMM is not. The exception is the shorthand for numbers such as 4. 4 is represented as IV (which is read as V - I) rather than IIII. The rules for subtraction are:

   This numeral	Can be subtracted from
   I	V and X
   X	L and C
   C	D and M

   
   As a reference for Roman numerals, you can visit wikipedia.
   
   Complete int_of_roman assuming only valid roman numerals as input:

   let rec int_of_roman (r : roman) : int =
     let int_of_numeral = function
       | I -> 1
       | V -> 5
       | X -> 10
       | L -> 50
       | C -> 100
       | D -> 500
       | M -> 1000 in
     ???

   Examples:

   int_of_roman [I; I; I] = 3
   int_of_roman [X; L; I; I] = 42
   int_of_roman [M; C; M; X; C; I; X] = 1999

4. Write a function subset : 'a list -> 'a list list which creates all subsets of a given set. Examples:

   subset [] = [[]]
   subset [1; 2; 3] = [[]; [1]; [2]; [3]; [1; 2]; [2; 3]; [1; 3]; [1; 2; 3]
   subset [1; 2] = [[]; [1]; [2]; [1; 2]]