CS 320 Theory Assignment #2 Due: Wed., October 14, 11:59 pm
EX 1 – Option Type
Exhaustively match the following expressions without using wildcards. OCaml should not raise warnings. You should match until there are only terminal types or the tuple with the terminal types to be matched with. Only int, bool, float, and string are considered terminal types for our purpose. List should be matched with at least two cases. You can use nested match.
At the end of the question, we provide you with some invalid examples.
1. Match the following expressions 1.1
x: (int option * float) option
match x with
1.2
y: string option list option
match y with
1.3
z: int list option option
match z with
Below are two examples that DO NOT satisfy our requirements.
WRONG EXAMPLE 1:
e: (int option * bool) option
match e with
| None -> …
| Some a -> …
Wrong, because a is a tuple with non-terminal type int option.
WRONG EXAMPLE 2:
x: (int option * bool) option
match x with
| None -> …
| Some a -> match a with (
(b, c) -> …
Wrong, because b is int option which is not a terminal type.
Ex 2 – Type Inference
Ex 2.1 – Consider a situation where the expression f 3 has the same type as the expression
g “hello”, and the expression g “world” (6, 12) evaluates to Some (). a) What is the type of g
b) What is the type of f
Ex 2.2 – Consider a situation where the expressions f x g y and g y and
(y 26) ^ “alpha” are well-typed. Now assume that the expression y 16 evaluates to the same value as the expression x “foo” “bar” evaluates to.
a) What is the type of f? If the information is not enough to decide the type of each argument, use ‘a, ‘b, ‘c , etc… to substitute the type of those arguments.
b) Is the expression f x g y 39 well-typed? Provide reasons to support your answer.
Ex 2.3 – Given the following type for the function f:
f: ‘a -> (‘b -> ‘a) -> ‘b -> ‘b
Are the following expressions well-typed? (Yes/No , no explanations needed) a) f7(funx->x+3)
b) f(Some1) (fun(x,y)->x+y)
c) letg=fNone(fun(x,y,z)->Some(y+2))ing(1,2,3)
Ex 2.4 – Suppose that the following expression is well-typed and returns true.
a)
b)
c)
let g = f (Some ()) in
let h = g [3;6;7] in
h (Some (3.0, 4))
What is the type of h?
What is the type of g?
What is the type of f?
Ex 3 – Higher Order Functions 1) Here is a mystery function:
We ask you to first study the above mystery function carefully. Make sure you understand what it does. a) What is the type of the mystery function? Make sure to explain your answer.
b) We now ask you to rewrite the mystery function. Your new implementation of the mystery function must be identical in every respect to what we have provided above, however, you must implement this mystery function using the fold_right function. The type of fold_right is as follows: (‘a -> ‘b -> ‘b) -> ‘a list -> ‘b -> ‘b and we also provide you
with the implementation of fold_right.
let rec mystery x m = match m with
| [] -> false
| hd :: tl -> x == hd || mystery x tl
let rec fold_right f l a = match l with
[]->a |
h::t-> f h (fold_right f t a)
2) Here is a mystery function:
We ask you to first study the above mystery function carefully. Make sure you understand what it does. a) What is the type of the mystery function?
c) We now ask you to rewrite the mystery function. Your new implementation of the mystery function must be identical in every respect to what we have provided above, however, you must implement this mystery function using the fold_right function. The type of fold_right is
as follows: (‘a -> ‘b -> ‘b) -> ‘a list -> ‘b -> ‘b and we also provide you with the implementation of fold_right.
let rec mystery x=
match x with
| [] -> []
| None :: t -> mystery t
| Some y :: t -> y :: mystery t
let rec fold_right f l a = match l with
[]->a |
h::t-> f h (fold_right f t a)
3)
Here is an add function that adds two integers and returns back an integer.
let add (x,y)=x+y
The type of the above add function is
int * int -> int
We call the above function of add as uncurried and not curried because in order to call the add function,
you must have both the input ints available.
We are now asking you to write a function call curry that has the following type: (‘a * ‘b -> ‘c) -> ‘a -> ‘b -> ‘c
Which takes in as input a function (which is uncurried) and then returns back the curried version of that function.