Important notes about grading:

1. Compiler errors: Programs that cannot be compiled will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit recitation or office hours.
2. 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. Submitting an incorrect version before the deadline and realizing that you have done so after the deadline will be counted as a late submission.

Compile and run your code:

After downloading and unzipping the file for assignment2, in your command-line window, cd into the directory which contains src. You should write your code in src/assignment2.ml.

Use ocamlc -o test src/assignment2.ml to compile the code. Then, use ./test to excute it.

Submission:

Please submit to Sakai with assignment2.ml only.

Please do not use any functions in the List module for Problem 1-4. You can use @ for list concatenation.

Problem 1

Write a function

cond_dup : 'a list -> ('a -> bool) -> 'a list

that takes in a list and a preciate and duplicates all elements which satisfy the condition expressed in the predicate. For example, cond_dup [3;4;5] (fun x -> x mod 2 = 1) = [3;3;4;5;5].

let rec cond_dup l f =
  (* YOUR CODE HERE *)

assert (cond_dup [3;4;5] (fun x -> x mod 2 = 1) = [3;3;4;5;5])

Problem 2

Write a function

n_times : ('a -> 'a) * int * 'a -> 'a

such that n_times (f,n,v) applies f to v n times. For example, n_times((fun x-> x+1), 50, 0) = 50. If n<=0 return v.

let rec n_times (f, n, v) =
  (* YOUR CODE HERE *)

assert (n_times((fun x-> x+1), 50, 0) = 50)

Problem 3

Write a function

zipwith : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

such that zipwith f l1 l2 generates a list whose ith element is obtained by applying f to the ith element of l1 and the ith element of l2 . If the lists have different lengths, the extra elements in the longer list should be ignored. For example, zipwith (+) [1;2;3] [4;5] = [5;7].

let rec zipwith f l1 l2 =
  (* YOUR CODE HERE *)

assert (zipwith (+) [1;2;3] [4;5] = [5;7])

Problem 4

Write a function

buckets : ('a -> 'a -> bool) -> 'a list -> 'a list list

that partitions a list into equivalence classes. That is, buckets equiv lst should return a list of lists where each sublist in the result contains equivalent elements, where two elements are considered equivalent if equiv returns true. For example:

buckets (=) [1;2;3;4] = [[1];[2];[3];[4]]
buckets (=) [1;2;3;4;2;3;4;3;4] = [[1];[2;2];[3;3;3];[4;4;4]]
buckets (fun x y -> (=) (x mod 3) (y mod 3)) [1;2;3;4;5;6] = [[1;4];[2;5];[3;6]]

The order of the buckets must reflect the order in which the elements appear in the original list. For example, the output of buckets (=) [1;2;3;4] should be [[1];[2];[3];[4]] and not [[2];[1];[3];[4]] or any other permutation.

The order of the elements in each bucket must reflect the order in which the elements appear in the original list. For example, the output of buckets (fun x y -> (=) (x mod 3) (y mod 3)) [1;2;3;4;5;6] should be [[1;4];[2;5];[3;6]] and not [[4;1];[5;2];[3;6]] or any other permutations.

Assume that the comparison function ('a -> 'a -> bool) is commutative, associative and idempotent.

Just use lists. Do not use sets or hash tables.

List append function @ may come in handy. [1;2;3] @ [4;5;6] = [1;2;3;4;5;6].

let buckets p l =
  (* YOUR CODE HERE *)

assert (buckets (=) [1;2;3;4] = [[1];[2];[3];[4]]);
assert (buckets (=) [1;2;3;4;2;3;4;3;4] = [[1];[2;2];[3;3;3];[4;4;4]]);
assert (buckets (fun x y -> (=) (x mod 3) (y mod 3)) [1;2;3;4;5;6] = [[1;4];[2;5];[3;6]])

Tail Recursion

Problem 5

The usual recursive formulation of fibonacci function

let rec fib n = 
  if n = 0 then 0
  else if n = 1 then 1
  else fib (n-1) + fib (n-2)

has exponential running time. It will take a long time to compute fib 50. You might have to interrupt its execution if you did try to do fib 50 in the notebook.

But we know that fibonacci number can be computed in linear time by remembering just the current cur and the previous prev fibonacci number. In this case, the next fibonacci number is computed as the sum of the current and the previous numbers. Then the program continues by setting prev to be cur and cur to be cur + prev.

Implement a tail recursive function fib_tailrec that uses this idea and computes the nth fibonacci number in linear time.

fib_tailrec : int -> int

let fib_tailrec n =
  (* YOUR CODE HERE *)

assert (fib_tailrec 50 = 12586269025)

Map and Fold

For the following problems, you must only use List.map, List.fold_left, or List.fold_right to complete these functions, so no functions should be defined using the rec keyword. You will lose points if this rule is not followed.

Some of these functions will require just List.map or List.fold_left, but some will require a combination of the two. The map/reduce design pattern may come in handy, e.g. map over a list to convert it to a new list which you then process a second time using fold. The idea is that you first process the list using map, and then reduce the resulting list using fold.

Problem 6

Write a function

assoc_list: 'a list -> ('a * int) list

that, given a list, returns a list of pairs where the first integer represents the element of the list and the second integer represents the number of occurrences of that element in the list. This associative list should not contain duplicates. Order does not matter. For example, assoc_list [1; 2; 2; 1; 3] = [(2,2); (1, 2); (3, 1)].

let assoc_list l =
  (* YOUR CODE HERE *)

assert (assoc_list [1; 2; 2; 1; 3] = [(2,2); (1, 2); (3, 1)])

Problem 7

Write a function

ap: ('a -> 'b) list -> 'a list -> 'b list

ap fs args applies each function in fs to each argument in args in order. For example, ap [(fun x -> x^"?"); (fun x -> x^"!")] ["foo";"bar"] = ["foo?";"bar?";"foo!";"bar!"] where ^ is an OCaml operator for string concatenation.

let ap fs args = 
  (* YOUR CODE HERE *)

assert (ap [(fun x -> x^"?"); (fun x -> x^"!")] ["foo";"bar"] = ["foo?";"bar?";"foo!";"bar!"])