Problem Set 1: An Introduction to OCaml

Due 1/29/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.

Three important notes about grading:

  1. 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.
  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.

Part 1: Expression Types

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

  1. (["cs", "312", "foo", "3110"], 312)
  2. (fun (x, y) -> x ^ " " ^ y) ("hello", "world")
  3. Some(fun x -> x + 2)

Give expressions that have the following OCaml types:

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

Replace ??? with an expression that makes the code type check correctly. Give the type of the expression you chose.

  1. let rec zardoz foo =
  match foo with
      ((a, b), c)::xs -> a (b + c + (zardoz xs))
    | _ -> 1
in zardoz ???

  2. let coeffs = (5, 2, 1) in
let sq x = x * x in
let det v = match v with (a, b, c) -> sq b - 4 * a * c in
let uncurry = ??? in
let zardoz = int_of_float (uncurry det coeffs) in zardoz

Part 2: Code Style

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 rev l =
  let rec foo a b =
    if (((List.length a) = 0) = true) then b
    else let h = List.hd(a) in
         let t = List.tl a in
         let r = h::b in
         foo t r in
  foo l []

Part 3: OCaml Functions

  1. Write a function revint : int -> int that produces a number whose decimal digits are reversed. The sign of the number remains unchanged: 
    revint 312 = 213
revint (-312) = -213
revint 0 = 0
  2. Write a function middle : int list -> int that returns the middle element of a list. If the list is of even length you can return either "middle" element as long as you are consistent. Think before you code, there is a short and simple solution that doesn't necessarily involve counting and multiple passes through the list.
  3. Consider positive numbers in binary form written as sequences of 0's and 1's, starting with the most significant bit. For instance, [1, 1, 0] is number 6. The empty list represents number 0 and lists must have no leading zeroes. Write a function addbin : int list * int list -> int list that adds two numbers written in this form.
  4. Write a function flatten : int list list -> int list that given a list of lists, combines them into a single list with the order preserved. 
    flatten [[1; 2; 3]; [4; 5]; [6; 7; 8]] = [1; 2; 3; 4; 5; 6; 7; 8]
flatten [[1; 2; 3]; [1; 2; 4]; [1]] = [1; 2; 3; 1; 2; 4; 1]
flatten [[1; 2; 3; 4]; []] = [1; 2; 3; 4]
    Do not use List.flatten.
  5. Write a function unflatten : int * int list -> int list list that given a single list, breaks it up into a list of lists of the specified size. Return an empty list if the size is invalid (< 1).
    unflatten (2, [7; 8; 9; 0]) = [[7; 8]; [9; 0]]
unflatten (3, [1; 2; 3; 4; 5; 6; 7; 8]) = [[1; 2; 3]; [4; 5; 6]; [7; 8]]
unflatten (7, [1; 2; 3]) = [[1; 2; 3]]
  6. Write a function permutations : int list -> int list list such that permutations lst returns a list containing every permutation of lst. For example, one correct answer to permutations [1; 2; 3] is [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]. It doesn't matter what order the permutations appear in the returned list. Note that if the input list is of length n then the answer should be of length n!. Handle lists with duplicate elements as you see fit.