Version: 6
Last modified: Tuesday, January 29, 19:00
Changes:
This problem set has three parts. You should
write your solution to each part in a separate file: part1.txt
,
part2.ml
, and part3.ml
. To help get you started,
we have provided a stub file for each part on CMS. You should download and
edit these files. Once you have finished, submit your solution using CMS,
linked from the course website.
For this problem set, you are restricted to the functional programming. OCaml has imperative features like mutable arrays and while loops. You may not use these or any other state-changing constructs. Contact the course staff if you are uncertain whether a given feature is imperative, but as a general rule, if it returns unit it is not functional. To reiterate:
NO SIDE EFFECTS
Give the types of each of the following OCaml expressions. For
example, the type of (1, 2)
is int * int
.
("(3110, 4410)", [[1]; [2; 3]; [4; 5; 6]])
(fun n -> n + 4) 7
[Some (fun x y z -> [(x, y); z]); None]
fun x -> function (y, z) -> (fun y z -> y + z) x
let f (x : int) : string = ...
).
'a option option -> 'a
string option list -> int -> string * string list
('a -> 'a -> 'b) -> 'a -> ('a -> 'b) * 'b
'a list -> 'b list -> ('a -> 'b -> 'a * 'b list)
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 zardoz foo = match foo with | ((x, y), z)::t -> x (y + z + (zardoz t)) | _ -> 1 in zardoz ???
let lst = ??? in let num n = match n with (a, b, c) -> a / ((String.length b) * c) in let sneaky z = match z with (a, b) -> let c = num a in let d = num b in (max c d) / (min c d) in let rec zardoz z = match z with | [] -> [] | h :: t -> (sneaky h) :: (zardoz t) in let connery z = if z = [] then failwith "too easy" else zardoz z in connery lst
The following function executes correctly, but it was written with poor style. Rewrite it with better style. Please consult the CS 3110 style guide.
let zardoz zardoz yolo = let rec roll desert turn around = let up = fun x -> x in let never = if List.length turn > 0 = true then List.tl turn else [] in let gonna = List.length turn in let give = let you = 42 in up in let lie = give gonna in if lie = 1 then desert (List.hd turn) around else if lie = 0 = false then desert (List.hd turn) (roll desert never around) else if List.length turn = 0 then around else failwith "zardoz" in let rick = ([], []) in match yolo with [] -> rick | _ -> roll (fun for_ (so, long) -> (function true -> (for_::so, long) | false -> (so, for_::long)) (zardoz for_)) yolo rick
let string_rev (s : string) : string = ...Examples:
string_rev "zardoz" = "zodraz" string_rev "radar" = "radar" string_rev "" = ""
let dot (x1, x2) (y1, y2) = x1 *. y1 +. x2 *. y2Fill 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)(Of course this is just a puzzle exercise, not an example of good style with higher-order functions.)
type numeral = I | V | X | L | C | D | M type roman = numeral listIn any number written with Roman numerals, the numerals are usually ordered from greater valued characters to smaller valued characters. For example,
MMXII
is a
valid number, but IIXMM
is not. The exception is the shorthand for numbers
such as 4. 4 is represented as IV
(which is read as V - I
)
rather than IIII
. The rules for subtraction are:
This numeral | Can be subtracted from |
---|---|
I | V and X |
X | L and C |
C | D and M |
int_of_roman
assuming only valid roman numerals as input:
let rec int_of_roman (r : roman) : int = let int_of_numeral = function | I -> 1 | V -> 5 | X -> 10 | L -> 50 | C -> 100 | D -> 500 | M -> 1000 in ???Examples:
int_of_roman [I; I; I] = 3 int_of_roman [X; L; I; I] = 42 int_of_roman [M; C; M; X; C; I; X] = 1999
subset : 'a list -> 'a list list
which creates
all subsets of a given set. Examples:
subset [] = [[]] subset [1; 2; 3] = [[]; [1]; [2]; [3]; [1; 2]; [2; 3]; [1; 3]; [1; 2; 3] subset [1; 2] = [[]; [1]; [2]; [1; 2]]