# CS计算机代考程序代写 B tree ocaml CSE 130, Spring 2012 Name/ID Instructor: Ranjit Jhala

CSE 130, Spring 2012 Name/ID Instructor: Ranjit Jhala

Midterm Exam

Instructions: read these first!

Do not open the exam, turn it over, or look inside until you are told to begin.

Switch off cell phones and other potentially noisy devices.

Write your full name on the line at the top of this page. Do not separate pages.

You may refer to any printed materials, but no computational devices (such as laptops, calculators, phones, iPads, friends, enemies, pets, lovers).

Read questions carefully. Show all work you can in the space provided. Where limits are given, write no more than the amount specified.

The rest will be ignored.

Avoid seeing anyone else’s work or allowing yours to be seen.

Do not communicate with anyone but an exam proctor.

If you have a question, raise your hand.

When time is up, stop writing.

The points for each part are rough indication of the time that part should take.

Run LATEX again to produce the table

CSE 130, Spring 2012 Midterm Exam Page 1 of ?? 1. [?? points]

(a) [5 points] What type does Ocaml infer for (<.>) let (<.>) = fun f g x -> f (g x)

(b) [5 points] What does the following expression evaluate to? (The <.>) is as defined for the previous part.)

let foo = fun x -> x + 10 in

let bar = fun x -> x * 10 in

let goo = foo <.> bar in

goo 0

(c) [10 points] Write a tail-recursive function whose behavior is identical to the function below:

let rec giftList l = match l with

| [] -> “that’s what I want for Christmas!”

| g::l’ -> g ˆ ” and ” ˆ giftList l’

CSE 130, Spring 2012 Midterm Exam Page 2 of ?? 2. [?? points]

In this question, we have given you three concrete recursive functions. Your goal is to write generalized (polymorphic, higher-order) versions of the functions that encapsulate the recursion pattern and make it easily reusable.

(a) [4 points] let rec getEven xs = match xs with | [] -> None

| x::xs’ -> if (x mod 2 = 0)

then Some x

else getEven xs’

WhatisthetypeofgetEven?(Recall:type ’a option = None | Some of ’a)

(b) [6 points] Write a function:

val find_first: (’a -> bool) -> ’a list -> ’a option suchthatgetEvenisequivalenttofindFirst (fun x -> x mod 2 = 0)

let rec find_first f xs = match xs with |[] ->

| x::xs’ ->

(c) [3 points] Consider the tree type

type ’a tree = Leaf | Node of ’a * ’a tree * ’a tree

What is the type of the following function tree_to_string

let rec tree_to_string t = match t with

| Leaf -> “”

| Node(x, l, r) -> let ls = tree_to_string l in

let rs = tree_to_string r in

ls ˆ “, ” ˆ x ˆ “, ” ˆ rs

CSE 130, Spring 2012 Midterm Exam Page 3 of ??

(d) [7 points] Write a function

val post_fold: (’a -> ’b -> ’b -> ’b) -> ’b -> ’a tree -> ’b such that tree_to_string is equivalent to

post_fold (fun x ls rs -> ls ˆ “, ” ˆ x ˆ “, ” ˆ rs) “”

let rec post_fold f b t = match t with

| Leaf ->

| Node (x,l,r) ->

(e) [10 points] Write a function

val in_fold: (’a -> ’b -> ’a) -> ’a -> ’b tree -> ’a suchthattree_to_stringisequivalenttoin_fold (fun str x -> str ˆ “, ” ˆ x ˆ “, “) “”

let rec in_fold f b t = match t with

| Leaf ->

| Node (x,l,r) ->

CSE 130, Spring 2012 Midterm Exam Page 4 of ?? 3. [?? points]

Consider the following datatype

type (’a, ’b) either = Left of ’a | Right of ’b

The either type is a generalization of option which instead of just representing the junk value as None, allows you

to attach some information of type ’a.

(a) [2 points] Write down an expression that has the type

(int, string) either

and also has the type (int, bool) either

(Say what?! How can an expression have two types? Remember [] can have type int list and also have type string list.)

(b) [2 points] Write down an expression that has the type

(int, string) either

but does not have the type (int, bool) either

(c) [6 points] Write a function

val assoc: ’k -> (’k * ’v) list -> (’k, ’v) either

The function should have the following behavior:

# assoc “z” [(“x”, 1); (“y”, 2); (“z”, 3); (“z”, 4)] ;;

– : (string, int) either = Right 3

# assoc “z” [(“x”, 1); (“y”, 2)] ;;

– : (string, int) either = Left “z”

let rec assoc key kvs = match kvs with

| [] ->

| (k,v)::kvs’ ->

CSE 130, Spring 2012 Midterm Exam Page 5 of ??

(d) [7 points] Write a function

val map: (’b -> ’c) -> (’a, ’b) either -> (’a, ’c) either

The function should have the following behavior:

# map (fun i -> i + 1) (Left “x”)

– : (string, int) either = Left “x”

# map (fun i -> i + 1) (Right 12)

– : (’a, int) either = Right 13

# map string_of_int (Right 12)

– : (’a, string) either = Right “12”

let map f e =

(e) [8 points] Write a function

val map2: (’b ->’c ->’d) -> (’a,’b) either -> (’a,’c) either -> (’a,’d) either

The function should have the following behavior:

# map2 (+) (Left “x”) (Left “y”) ;;

– : (string, int) either = Left “x”

# map2 (+) (Left “x”) (Right 12) ;;

– : (string, int) either = Left “x”

# map2 (+) (Right 12) (Left “x”) ;;

– : (string, int) either = Left “x”

# map2 (+) (Right 12) (Right 7) ;;

– : (’a, int) either = Right 19

let map2 f e1 e2 =

CSE 130, Spring 2012 Midterm Exam Page 6 of ?? 4. [?? points]

Consider the following (subset) of Nano-ML.

type binop = Plus | Div

type expr = Const of int | Var of string | Bin of expr * binop * expr

As you doubtless know, the evaluation of certain expressions can result in errors such as unbound variables and divide- by-zeros. Instead of using exceptions as (in the programming assignment) we will track errors via the type:

type error = UnboundVariable of string | DivideByZero

(a) [5 points] Use the function assoc above to write a function

val lookup: string -> (string * int) list -> (error, int) either The function should have the following behavior:

# lookup “z” [(“x”, 1); (“y”, 2); (“z”, 3); (“z”, 4)];;

– : (error, int) either = Right 3

# lookup “z” [(“x”, 1); (“y”, 2)] ;;

– : (error, int) either = Left (UnboundVariable “z”)

let lookup x env =

(b) [5 points] Write a function

val safeDiv: int -> int -> (error, int) either

SuchthatsafeDiv n mreturnstheintegerresultn/mwhenitisdefined(i.e.whenmisnotzero)andreturnsthe divide-by-zero error otherwise. Concretely, your function should have the following behavior:

# safeDiv 40 2;;

– : (error, int) either = Right 20

# safeDiv 40 0;;

– : (error, int) either = Left DivideByZero

let safeDiv n m =

CSE 130, Spring 2012 Midterm Exam Page 7 of ??

(c) [10 points] Use the function lookup to write a function

val eval: (string * int) list -> expr -> (error, int) either The function should have the following behavior:

# let e0 = Bin (Var “x”, Plus, Var “y”);;

# let e1 = Bin (e0, Div, Var “y”);;

# eval [(“x”, 1); (“y”, 2)] e1;;

– : (error, int) either = Right 1

# let e2 = Bin (e1, Div, Var “z”);;

# eval [(“x”, 1); (“y”, 2)] e2;;

– : (error, int) either = Left (UnboundVariable “z”)

# let e3 = Bin (e1, Div, Const 0);;

# eval [(“x”, 1); (“y”, 2)] e3;;

– : (error, int) either = Left DivideByZero

let rec eval env e = match e with

| Const i ->

| Var v ->

| Bin(e1, Plus, e2) ->

| Bin(e1, Div, e2) ->