Description

There is the theory assignment for you, which teach the new guys to know what the OCaml is. So it’s very simply for you if you are good at OCaml. Please following the requirement and give me the code with comments as detailed as you can because I’m first to learn OCaml.

Homework #1

1 – Type Inference (20 points)

1) Suppose we have the following expressions (we omit some

information and we replace it with #n):

a :

b :

let

let

#1 list

#2

c = b :: a

d = (1, true) :: c

where the last expression type checks without error.

Ã¢â€”Â What is the type #1?

Ã¢â€”Â What is the type #2?

Ã¢â€”Â What is the type of the expression([d])?

2) Suppose we have the following expressions (we omit some

information and we replace it with #n):

a :

b :

c :

let

int list

#1

#2

(x,y) = b in (x :: a, [x < y] @ c)
where the last expression type checks without error.
Ã¢â€”Â What is the type #1?
Ã¢â€”Â What is the type #2?
Ã¢â€”Â What is the type of the expression([[x]] , c :: [])?
1
3) Suppose x0 could be matched as below without error
match x0 with
| [ ]
| x::xs
match
| 3.5
| _
| _
-> [0.]

-> (

x with

, []

->

, []

->

, x::xs ->

[ ]

[3.14]

[x +. 7.])

Ã¢â€”Â What is the type of the variable x0?

Ã¢â€”Â Now consider the first match for x0, where x0 is getting pattern

matched with [ ]. Let us suppose that we replace[0.] with [0]

Ã¢â€”â€¹ Do you think this replacement will result in some kind of error

indicating that the types are no longer consistent? Answer this

question either with a YES or a NO.

Ã¢â€”â€¹ Now provide an explanation supporting your answer from the

previous part.

2

4) Consider the following program:

let foo1 ls =

let rec aux ls a =

match ls with

| [ ]

->

| hd::tl

in aux ls 0.

->

let rec foo2 ls =

match ls with

| [ ]

->

| hd::tl

->

Ã¢â€”Â

a

aux tl (hd +. a)

1

hd + (foo2 tl)

What are the types of foo1 and foo2? Briefly explain your

reasoning.

Ã¢â€”Â If foo1 and foo2 were applied to the same input, do they compute

the same value? Briefly explain your reasoning.

3

2 – Pattern matching (18 points)

1) Consider the following expressions

a: bool

b: bool

c: bool

Complete the following match so that every possible expression that

replaces a, b and c in the matching statement is matched. You must ensure

that you have exhausted all possible cases for a, b and c. Please do not

use underscore in your match.

match (a,b,c) with

2) Consider the following expressions

a: int list * unit

b: float list

Complete the following match so that every possible expression that

replaces a and b in the matching statement is matched, distinguishing cases.

Please do not use underscore in your match.

match (a,b) with

4

3)

Ã¢â€”Â Suppose l : (t list) list, and consider the following

pattern matching.

match l with

| ([]::xs) -> …

| ((x::xs)::xs) -> …

| [] -> ….

Does this match explore all the possible top-level forms?

Ã¢ÂÂ Yes

Ã¢ÂÂ No

Ã¢â€”Â Suppose l : (int,int) list, and consider the following

pattern matching.

match l with

| [] -> ….

| ((x,y)::xs) -> …

Does this match explore all the possible top-level forms?

Ã¢ÂÂ Yes

Ã¢ÂÂ No

5

3 – Let-binding reduction (12 points)

1) Reduce the following expression to a value. Make sure that you show

all the steps:

let x= 2 in let z= 2 + x in let w= z + z + x in w

2) Reduce the following expression to a value. Make sure that you show

all the steps:

let x= 7+3 in let (z,y)=(x + x, 3) in let

(x,u,w)=(5,y,z+z) in u + x

6

Purchase answer to see full

attachment