# Ocaml代写 | CS440 , Spring 2021

1 Fill in the Blank (30 points)
For each code snippet, ll in the blank(s) with an expression such that the whole code snippet
evaluates exactly to the integer 42 (that is, it should not evaluate to 42.0, \42″, [42], etc.) or, if
this is not possible, explain why. The code you put in each blank should be a complete OCaml
expression (i.e., you should be able to type it into the OCaml toplevel by itself without a syntax
error).
(a) (3 points)
let rec f n =
if n <= 1 then 1
else n + f (n – 1)
in (f ____________) – 3
9
(b) (3 points)
int_of_string (“4″ ^ ________________)
\2”

(c) (3 points)
match _______________________ with
| [] -> 0
| x::[] -> 1
| x::y::[] -> 2
| x::y::z::t -> y
[21;42;63] (any list of length  3 with 42 as the second element)
(d) (3 points)
“4” + _______
Not possible: \4″ is a string, + takes ints
(e) (3 points)
let rec f x n =
if n <= 0 then x
else f (x + x) (n – 1)
in
let n = _________ in
if n <= 0 then 0 else
f _______ n
1, 21

(f) (3 points)
let rec f n =
if n <= 0 then 1
else n + f n
in f ____________
Not possible: this code will either return 1 or loop forever.
(g) (3 points)
let rec f x n =
if n <= 0 then x
else f (x + n) (n – 1)
in
let n = _________ in
if n <= 0 then 0 else
f _______ n
1, 41
(h) (3 points)
let f = ______________________
in
(List.fold_right f [2; 4] 0)
* (List.fold_right f [1; 0] 0)
fun d r -> r * 10 + d

(i) (3 points)
let f = ______________________
in List.map f [42]
Not possible: this must return a list
(j) (3 points)
try
21 / _______________
with Division_by_zero -> 42
02 Regular Expressions (8 points)
Give a regular expression that accepts the following languages. Use only the following regular
expression notations:
rs r followed by s (concatenation)
r j s r or s
r zero or more repetitions of r
 empty string
a the symbol a
[a z] symbols a; : : : ; z (similar for [0-9], etc.)
(a) (4 points)  = fa; bg
Every \a” is (eventually) followed by a \b”.
Examples: aaaaab, b, bbabb, , aabbbbbb
Not examples: bbbbbba, aaaaa
b(abb)
(b) (4 points)  = fa; : : : ; z; 0; : : : 9; :g
Filenames, possibly ending with a dot followed by an extension. Filenames and extensions
can’t start with a digit. Filenames can’t be empty and if there’s a dot, the extension can’t be
empty.
Examples: hw1, cs440:txt, parse:ml, login:c, arch:bz2
Not examples: 0:ml, hw:, file:0, :ml [a z]([0 9]j[a z])  (j:[a z]([0 9]j[a z]))

E-mail: vipdue@outlook.com  微信号:vipnxx