Problem Set 1: An Introduction to OCaml

Due 2/4/10

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

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

[(3110, [("2:30", "Ups 111"); ("3:30", "Ups 111"); ("6:30", "Phl 213")])]
(fun x -> x "a") (fun x -> [x])
Some(fun (x,y,z) -> x + y + z)

Give expressions that have the following OCaml types:

(int * ((string * int) list))
(float * bool * char) -> float -> bool
(string -> 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 zardoz zardoz =
   let rec foo zardoz =
      match zardoz with [] -> [] | h::t -> (foo t)@[h]
   in
   if (zardoz = foo zardoz) then () else failwith "argh"
in
zardoz [[[]]; [[1]]; ???]

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 (65 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_nat : int list -> int such that count_nat lst returns the number of integers >0 occurring in lst. Use functions in the OCaml standard library, specifically the List module. For full credit, write this function without using the rec keyword.
```
count_nat [3110, -3, 1, 0, 55] = 3
```

(20 pts) Consider the function dyck: string -> bool that, given a string, checks whether the parentheses "(" ")" occurring in it are well-matched; characters "[", "]", "{", "}" as well as all other characters are to be ignored. For example,

dyck "((()())())" = true;;
dyck "(" = false;;
dyck ")" = false;;
dyck "(abc)" = true;;
dyck "(abc))" = false;;
dyck "open)(close" = false;;
dyck "open()close" = true;;
dyck "((()))()(()())((()())())()" = true;;
dyck "()()()(())()(()(()())())" = true;;
dyck "()()()(())()(()(()())())]" = true;;
dyck "{(]][}}})[" = true;;
dyck "(a)(ge)(gtrhr)rhr(rht(t)th)th(r)th((th)(th(t)(h)t)(th))th" = true;;
dyck "(a)(ge)(gtrhr)rhr(rht(t)th)th(r)th((th)(th(t)(h)t)(th)th" = false;;

Fill in the ??? below to implement the above function:

let dyck (s: string): bool =
   let rec aux s n =
      if s = "" then ???
      else
         let n2 = n +
            (match s.[0] with
               '(' -> 1
             | ')' -> ???
             | _   -> 0)
         in
         if n2 ??? 0 then false
         else
            let rest = String.sub s 1 ((String.length s) - 1) in
            (aux rest n2)
   in
   aux s 0

(25 pts) Write a function mycalc: string list -> int * (string list) that takes a list of strings and interprets it as an arithmetic expression in prefix notation built from +, *, and integers followed possibly by further strings (called the residual list). The function returns a pair (v, residual_list) of the value v of the expression and the residual list. If the input list is too short, that is, it is either empty [] or there are too few integers to be able to evaluate the arithmetic operations in the expression (e.g., ["+"; "1"] or ["*"; "+"; "2"; "3"]), then raise an exception. For example:
```
mycalc ["*"; "3"; "2"] = (6, []);;  (* 3 * 2 = 6 *)
mycalc ["+"; "5"; "*"; "3"; "2"] = (11, []);;  (* 5 + (3 * 2) = 11 *)
mycalc ["*"; "+"; "+"; "-7"; "3"; "11"; "+"; "2"; "-5"] = (-21, []);;  (* ((-7 + 3) + 11) * (2 + -5) *)
mycalc ["5"; "*"; "3"; "2"] = (5, ["*"; "3"; "2"]);;
mycalc ["3"; "2"] = (3, ["2"]);;
mycalc ["2"] = (2, []);;
mycalc ["+"; "1"; "+"; "2"; "*"; "3"; "4"] = (15, []);;
mycalc ["+"; "1"; "+"; "2"; "*"; "3"; "4"; "*"; "2"; "2"] = (15, ["*"; "2"; "2"]);;

mycalc [] ... throws exception
mycalc ["+"; "5"; "*"; "3"] ... throws exception
mycalc ["foo"] ... throws exception. 
mycalc ["2"; "foo"] = (2, ["foo"]);; (* it is also ok to throw an exception here, but it is not required *)
```
Hint: the residual list is not there to annoy you but allows for a very elegant recursive solution of the problem.
Karma: Consider a list on which mycalc does not throw an exception and on which it returns the empty residual list, that is, a well-formed prefix arithmetic expression. Write a function myccount: string list -> int that, given such a well-formed expression as a string list, counts the number of distinct values that can be produced by reordering the elements of the list, not considering the reorderings for which mycalc returns a nonempty residual list, and not double-counting two expressions that have the same value. For example, myccount ["+"; "*"; "2"; "2"; "3"] = 2 because mycalc ["+"; "*"; "2"; "2"; "3"] = ["+"; "3"; "*"; "2"; "2"] = (7, []) and mycalc ["+"; "*"; "2"; "3"; "2"] = ["+"; "*"; "3"; "2"; "2"] = ... = (8, []) and there are no other values that can be produced by reordering the list. (mycalc ["3"; "+"; "*"; "2"; "3"] = (3, ["+"; "*"; "2"; "3"]) does not qualify because the residual list is empty.) If you solve this problem, add your solution to part3.ml