Problem Set 1: An Introduction to OCaml

Due 9/8/09

Instructions

This problem set has three parts. You will 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 and edit these files. Once you have finished, submit your solution using CMS, linked from the course website.

Important notes about grading:

Compile errors: All programs that 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 and hand in a file that compiles, rather than handing in a more complete file that does not compile.
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.
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.
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 after the deadline still constitutes a late assignment.

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.

[("New York", 8008278); ("Los Angeles", 3694820); ("Chicago", 2896016)]
(fun x y -> x y) (fun x -> x + 1)
Some (fun (x,y,z) -> x + y + z)

Give expressions that have the following OCaml types:

char list option
(float * bool * char) -> float -> bool
(int -> string -> int * string) -> (string * int) -> (int * string)

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.

let rec foo f = 
  match f with
      (a, b) :: t -> a + b + foo t
    | _ -> 0 in
let rec zardoz z =
  match z with
      h :: t -> foo h + zardoz t
    | _ -> failwith "empty" in
zardoz ???

let nums = ??? in
let add n = match n with (a,b,c) -> a+b+c in
let split z = match z with (a,b) -> add a + add b
in let rec zardoz z = match z with
    [] -> []
  | h :: t -> (split h) :: (zardoz t) in
zardoz nums

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.

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

Part 3: OCaml Functions (60 pts)

(10 pts) Write a function n_times: ('a -> 'a) -> int -> 'a -> 'a such that n_times f n x that takes a function and applies it to x n times.
```
n_times (fun x -> x + 1) 50 0 = 50
```
(10 pts) Write a function count_caps : string list -> string list such that count_caps lst returns the number of strings in lst that begin with a capital letter. Use functions in the OCaml standard library. For full credit, write this function without using the rec keyword.
```
count_caps ["Ocaml"; "curry"; "Rec"; "fun"; "3110"] = 2
```

(20 pts) 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)

(20 pts) Write a function transpose: 'a list list -> 'a list list that takes a matrix, represented as a list of lists and transposes it. For full credit, your implementation should raise an exception, with a descriptive error message (ex: "Matrix has no rows"), for invalid matrices. The three invalid cases are matricies with no rows ([]) or no columns ([ []; []; [] ]) and non-rectangular matrices (i.e. the sub-lists have different lengths). For example:
```
traspose [[1]] = [[1]]
transpose [[1;2]; [3;4]] = [[1;3]; [2;4]]
transpose transpose [[1;2]; [3;4]] = [[1;2]; [3;4]]
transpose [[1;2]; [3;4;5]; []] = "Error, non-rectangular matrix"
```
Karma: transpose can be written without using the rec keyword. Look into the OCaml Library functions of List.fold and List.map2
Karma: Write a function random_k_sublist: 'a list -> int -> 'a list that takes a list of length n and returns a random list of length k. All possible sublists must have an equal probability of being selected. Order is irrelevant, as in combinatorial selection.