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.
Give the types of each of the following OCaml expressions. For example, the type of (1, 2)
is int * int
.
(["cs", "312", "foo", "3110"], 312)
(fun (x, y) -> x ^ " " ^ y) ("hello", "world")
Some(fun x -> x + 2)
Give expressions that have the following OCaml types:
int -> int * int -> int
((float * int) list * char) list list
(string -> string) -> (int -> bool) list
Replace ???
with an expression that makes the code type check correctly. Give the type of the expression you chose.
let rec zardoz foo = match foo with ((a, b), c)::xs -> a (b + c + (zardoz xs)) | _ -> 1 in zardoz ???
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
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 []
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
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.
addbin : int list * int list -> int list
that adds two numbers written in this form.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.
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]]
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.