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
None ->
|Some y -> (let (z,w)= y in match z with
None ->
|Some u -> …)
Another more compact alternative solution
match x with
None ->
|Some (None,w) ->
|Some (Some y,w) ->
1.2
y: string option list option
match y with
None ->
|Some [] ->
|Some (None::ys) ->
|Some ((Some z)::ys) ->
1.3
z: int list option option
match z with
None ->
|Some None ->
|Some (Some []) ->
|Some (Some (x::xs)) ->
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
String -> int * int -> unit option Or
‘a -> ‘b -> unit option
Or other variations
‘a -> int * int -> unit option
‘a -> ‘b * int -> unit option
‘a -> int * ‘b -> unit option string -> ‘b -> unit option string -> ‘b * ‘c -> unit option string -> ‘b * int -> unit option string -> int * ‘b -> unit option ‘a -> ‘b * ‘c -> unit option
b) What is the type of f
int -> int * int -> unit option
Or
‘a -> ‘b -> unit option
Or other variations
‘a -> int * int -> unit option ‘a -> ‘b * int -> unit option ‘a -> int * ‘b -> unit option int -> ‘b -> unit option
int -> ‘b * ‘c -> unit option int -> ‘b * int -> unit option int -> int * ‘b -> unit option ‘a -> ‘b * ‘c -> unit option
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 -> ‘u -> ‘w ) -> ((‘z -> ‘r) -> `d) -> (‘c -> ‘h) -> ‘e
or
(string -> string -> string) -> ((int -> string) -> ‘a ) -> (int -> string) -> ‘e
Or many other variations in between
b) Is the expression f x g y 39 well-typed? Provide reasons to support your answer. There is not enough information to say if it is well typed or not.
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)
yes, it is well-typed and it has type int -> int
b) f(Some1) (fun(x,y)->x+y)
no, it is not well-typed. ‘a needs to be int option and int at the same time and this is not possible.
c) letg=fNone(fun(x,y,z)->Some(y+2))ing(1,2,3) yes, it is well-typed and its type is int * int * int.
Ex 2.4 – Suppose that the following expression is well-typed and returns true.
let g = f (Some ()) in
let h = g [3;6;7] in
h (Some (3.0, 4))
a) What is the type of h?
(float * int) option -> bool
b) What is the type of g?
int list ->(float * int) option -> bool
c) What is the type of f?
unit option -> int list ->(float * int) option -> bool
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.
‘a -> ‘a list -> bool
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)
fun x l -> fold_right (fun z y -> z=x || y) l false fun x l -> fold_right (fun z y -> z==x || y) l false Both solutions are Ok.
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?
‘a option list -> ‘a list
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 fold_right f l a =
let rec mystery x=
match x with
| [] -> []
| None :: t -> mystery t
| Some y :: t -> y :: mystery t
match l with []->a
|
h::t-> f h (fold_right f t a)
fun l -> fold_right (fun z y -> match z with None -> y |
Some u -> u:: y) l []
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.
fun f x y = f (x,y)