(* Exercise 1 *) (* Look at the following type definition. *) type color = Red | Yellow | Blue | Green | Orange | Other of string type favorite = Color of color | Movie of string | Tvshow of string | Number of float | Letter of char (* We've defined some sample lists of favorite movies/colors/etc. * You can think of each of these lists as representing someone's * input describing their favorite things. * You may want to use these for testing your functions later.*) let a : favorite list = [Movie "Love Story"; Color Blue; Tvshow "The Simpsons"; Color Orange] let b : favorite list = [Number 1.0; Number 2.0; Number 5.0; Number 14.0; Number 42.0] let c : favorite list = [Movie "A Beautiful Mind"; Tvshow "House"; Letter 'P'; Color Orange] let d : favorite list = [Tvshow "Lost"; Number 3.14] let students = [a; b; c; d] (* 1a. Define a value of type favorite list for someone whose * favorite color is Aubergine and whose favorite number is 5. *) (* let prob1a : favorite list = *) (* 1b. Write a function that takes a value of type favorite list (like the * ones above) and returns the title of this person's favorite movie, or * None if a favorite movie isn't given. If multiple movies are listed, * return the first. What is the type signature for this function? *) (* let favmovie_type = "" *) (* let rec favmovie lst = *) (* 1c. Write a function that takes a value of type favorite list and * returns true if and only if this person has listed Orange as a * favorite color. What is the type signature for this function?*) (* let princetonpride_type = "" *) (* let rec princetonpride lst = *) (* Exercise 2 *) (* 2a. Define an algebraic data type representing either ints or floats *) (* type realnum = *) (* 2b. Define two functions to create realnums from an int and a float, respectively *) (* let real_of_int (i:int) : realnum = let real_of_float (f:float) : realnum = *) (* 2c. Define a function testing whether two realnums are equal. It shouldn't * matter whether they are ints or floats, e.g (realequal 4 4.0) => True. *) (* let realequal (a: realnum) (b: realnum) : bool = *) (* Exercise 3: an expansion of last week's "form", as seen in precept *) type var = string type form = | Var of var | And of forms | Or of forms and forms = form list type env = (var * bool) list (* We have defined a variable type 'var' and a boolean formula that is * made up of 'And's and 'Or's of variables. An environment is a mapping * from variables to boolean values. *) (* 3a. Write a function that given a boolean formula returns the list of all * unique variables that may be found in the bolean formula *) (* let fvars (f:form) : var list = *) (* 3b. Write a function that takes a boolean formula and returns * Some e -- if there exists a satisfying environment for the formula * (and e is one such satisfying assignment) * None -- if there does not exist a satisfying assignment *) (* let is_Sat (f: form) : env option = *) (* 3c. Reimplement the types and functions from the rest of part3 to * include a negation formula (Not of form'). For the autograder, add ' * to each type or function name (e.g. types var', form', forms', env' * and functions fvars' and is_Sat' *) type var' = string type form' = Var of var' | Not of form' | And of forms' | Or of forms' and forms' = form' list type env' = (var' * bool) list (* let fvars' (f:form') : var' list = *) (* let is_Sat' (f: form') : env' option = *) (* Exercise 4 *) (* 4a. Given the function below, give a short proof that * double N = 2*N *) let double (n: int) : int = n + n (* 4b. Given the function below, prove that for any natural number N: sum_sqrs N = (N * (N+1) * (2*N + 1))/6 You may assume that we have already proved this lemma: If N=k+1 and N is a natural number > 0, then k must also be a natural number *) let rec sum_sqrs (n: int) : int = if n <= 0 then 0 else (n*n) + sum_sqrs(n-1) (* 4c. Given the functions below, prove that for any list: behead ( prepend xs x) = xs *) let prepend (xs: 'a list) (x: 'a) : 'a list = x::xs let behead (xs: 'a list) = match xs with | [] -> [] | hd::tl -> tl (* 4d. Given the function below, prove that for any list: noop xs = xs *) let rec noop (xs: 'a list) : 'a list = match xs with | [] -> [] | hd::tl -> hd :: noop tl