Midterm Exam Spring '23 v2 (solutions)

CS131 Spring 23 - Midterm #1 version 2 rubric 1. [10 points-2 each] For each of the items below, write a Haskell type signature for the expression. If the item is a function then use the standard haskell type notation for a function. If the item is an expression, write the type of the expression (e.g., [Int]). For any answers that use one or more type variables where concrete types can't be inferred , use "t1", "t2", etc. for your type variable names. a. foo bar = [] b. z = foldl (\x y -> x ++ y) c. z = \x -> x ++ ["carey"] d. m = [(take 3 y, (\a -> length a < 7) x) | x <- ["matt","ashwin","siddarth","ruining"], y <- ["monday","tuesday","wednesday","thursday","friday"]] e. foo bar = map (\x -> 2 * x) bar Answers: Any option listed below is worth full credit. Answers that fail to use types t1, t2, etc. but instead use other letters or type names should get full credit if their answer is valid. An answer is either entirely correct or entirely wrong, a. foo :: t1 -> [t2] b. z :: [t1] -> [[t1]] -> [t1] z :: Foldable t2 => [t1] -> t2 [t1] -> [t1] (the 2nd answer involves type classes, which we didn’t learn!) c. z :: [[Char]] -> [[Char]] z :: [String] -> [String] d. m :: [([Char], Bool)] m :: [(String, Bool)] [([Char], Bool)] [(String, Bool)] e. foo :: Num t1 => [t1] -> [t1] foo :: [Int] -> [Int] foo :: [Integer] -> [Integer] 2. [5 points] Suppose a language does not support closures. Is it possible for the language to still support currying and partial function application? If so, how would this work; if not, explain why not. Note: Limit your answer to five or fewer sentences, and avoid adding superfluous, incorrect answers as this will result in a point deduction. Answer: ● Any answer that hits the following points gets full credit: Currying requires closures to capture free variables used in the inner lambda expressions. If there are no closures then we can't create curried functions or do partial application. ● If the student just says currying/PA is not possible but does not give a rationale they get 1 point ● If the student also includes superfluous answers that are not correct, take one point off for each incorrect answer that is present. ● The minimum score for this problem is zero. 3. [16 points-2/2/2/10] In this question, you will be implementing directed graph algebraic data types and algorithms in Haskell. Recall that a graph is composed of vertices that hold values, and edges which connect vertices to other vertices. In a directed graph, edges are unidirectional, so an outgoing edge from vertex A to vertex B does NOT imply that B also has a direct connection to A. You may assume that all graphs have at least one vertex. a. Show the Haskell definition for an algebraic data type called "DirectedGraph" that has a single “Vertex” variant. Each vertex must have one Integer value, and a list of zero or more adjacent vertices that can be reached from the current vertex. Answer: Any of the following answers is OK: data DirectedGraph = Vertex Int [DirectedGraph] data DirectedGraph = Vertex Integer [DirectedGraph] data DirectedGraph = Vertex [DirectedGraph] Int data DirectedGraph = Vertex [DirectedGraph] Integer If the student uses a type variable with a type of Integral that's ok too. All other answers get a zero. b. Using your DirectedGraph ADT, write down a Haskell expression that represents a graph with two vertices: 1. A vertex with the value 5 with no outgoing edges 2. A vertex with the value 42, with an outgoing edge to the previous vertex Answer: The students may use any variable names they like (instead of a and b). Given these definitions from part a: data DirectedGraph = Vertex Int [DirectedGraph] data DirectedGraph = Vertex Integer [DirectedGraph] Either of the following options are valid: a = Vertex 5 [] – 1 point b = Vertex 42 [a] – 1 point b = Vertex 42 [Vertex 5 []] – 2 points

Given these definitions from part a: data DirectedGraph = vertex [DirectedGraph] Int data DirectedGraph = vertex [DirectedGraph] Integer Either of the following options are valid: a = Vertex [] 5 – 1 point b = Vertex [a] 42 – 1 point b = Vertex [Vertex [] 5] 42 – 2 points c. Carey has designed his own graph ADT, and written a Haskell function that adds a vertex to the “front” of an existing graph g that is passed in as a parameter: add_to_front g = Vertex 0 [g] In Haskell, creating new data structures incurs cost. Assuming there are N vertices in the existing graph g , what is the time complexity of Carey's function (i.e., the big-O)? Why? Answer: O(1) because only a single new vertex is being created, and it links to the original graph. The existing graph need not be regenerated in any way. d. Write a function called vertices_sum that takes in one argument (a DirectedGraph) and returns the sum of all vertices in the graph. Your function must include a type annotation for full credit. You may assume that the passed-in graph is guaranteed to have no cycles. You may have helper function(s). Your solution MUST be shorter than 8 lines long. Answer: Any of these answers deserves full marks. They require one of the following type annotations: sum_of_vertices :: DirectedGraph -> Int sum_of_vertices :: DirectedGraph -> Integer --- carey's solution sum_of_vertices (Vertex val vertices) = val + (sumx_aux vertices) where value (Vertex val vertices) = val + (sumx_aux vertices) sumx_aux vertices = sum [value n | n <- vertices] --- matt’s solution (map + sum) sum_of_vertices (Vertex val vertices) = val + sum (map sum_of_vertices vertices) --- matt’s solution (map + fold) sum_of_vertices (Vertex val vertices) = foldl (+) val (map sum_of_vertices vertices) --- optionally, students might include a base case like the following, though observe that it’s not strictly necessary sum_of_vertices (Vertex val []) = val --- many other solutions are possible. other neat ones we saw included: --- - parsing the vertices vertex-by-vertex, which required: --- - a mutually recursive helper function --- - “recreating” a new node with value 0, and the tail as its vertices --- - foldl/foldr, but calling sum_of_graph on each edge Rubric Sketch (negative grading) ● Perfect (-0 pts) ● Minor syntax error(s) that did not affect understanding (-1 pts) ○ ex: forgetting the parens for an ADT variant argument ● Incorrect base case / singleton vertex (-2 pts) ○ ex: base case has value 0 ● Minor recursive logic bug (-2 pts) ○ requires a fully-working solution, with one minor tweak ○ ex: switching the order of the args to foldl/foldr ○ ex: used sum improperly ● Major recursive logic bug / multiple minor bugs (-5 pts) ○ ex: recursive solution tries to add a DirectedGraph and Integer ○ ex: recursive solution tries to call sum_of_vertices [DirectedGraph] ○ ex: recursive solution misses multiple levels of children ● Incorrect/missing type definition (-1 pts) ○ all-or-nothing; did give ECF ○ if only submitted typedef, received 1 pt total ● Did not attempt (-10 pts) A handful of students noted that our definition of acyclic was unclear (is this acyclic in the undirected sense, or in the directed sense)? The latter has a “diamond problem” built-in; we were expecting solutions for the former. If you tried to deal with this but had a minor logic bug, we gave you full credit. 4. [10 points] Write a Haskell function called extract_each_nth that takes in an Integer n and a list of generic types that returns a sublist of every n th element. For example: extract_each_nth 2 ["hi","what up","hello"] should return ["what up"] extract_each_nth 5 [31 .. 48] should return [35, 40, 45] Your function must have a type signature and must use either filter, foldr or foldl. It must be less than 8 lines long. Hint: If you use fold, your accumulator doesn't need to be the same type as your returned value or your input, and a tuple might be useful! Carey's answer: extract_each_nth :: Integer -> [a] -> [a] extract_each_nth n lst = map (\tup -> snd tup) (filter (\tup -> (fst tup) `mod` n == 0) (zip [1..] lst)) Ruining's answer: get_every_nth :: Integer -> [a] -> [a] get_every_nth n lst = let f = \(res,index) x -> if mod index n == 0 then (x:res, index+1) else (res,index+1) -- this 'let' is one line in reverse( fst (foldl f ([],1) lst)) also acceptable; (\(x,_) ->x) instead of fst Possible common mistakes: - using foldr instead of foldl -> -3 pts - indexing starts at 0 instead of 1 -> -2 pts - forget to convert from tuple back to list -> -2 pts - syntax error with order of operands for f function in fold (need to match) -> -2 pts - if foldl: forget to reverse the list -> -1 pt - 3 points for having a good idea of what to do as a baseline

7. [9 points-3/3/3] We know that int and float are usually not subtypes of each other. Assume you have a programming language where you can represent integers and floating-point values with infinite precision (call the data types Integer and Float). In this language, the operations on Integer are +, -, *, / and % and the operations on Float are +, -, *, and /. a. In this language, will Float be a subtype of Integer? Why or why not? Answer: 3 points for the following: No, Float is a NOT a subtype of Integer because: 1. Not every Float value can be represented by an Integer 1. Not every operation on an Integer can also be performed on a Float. 3 points off if they do not say "No" 1 point off for missing either requirement b. In this language, will Integer be a subtype of Float? Why or why not? Answer: 3 points for the following: Yes, Int is a subtype of Float because: 2. Every Integer value can be represented by a Float (with the fractional part being zero). 3. Every operation on Float can also be performed on an Integer. 3 points off if they do not say "Yes" 1 point off for missing either requirement c. If you discovered that the Float type also supports an additional operator, exponentiation, what effect would that have on your answers to a and b? Why? Answer: 3 points for the following: Neither would be subtypes of each other. Any one of the following reasons is sufficient for full credit: 1. Floats have an operator that Integers don't support so Integers can't be a subtype of Float 2. Integers have an operator that Floats don't support so Floats can't be a subtype of Integer 8. [9 points-3/3/3] Siddarth has created a compiler for a new language he's invented. He gives you the following code written in the language, with line numbers added for clarity: 00 # A mystery function in Siddarth's language 01 func mystery(x) { 02 y = x; 03 print(f”{y}”); 04 y = 4.5; 05 print(f"{y}"); 06 return y; 07 } 08 09 q = mystery(5); 10 print(f"{q}"); Siddarth tells you that the program above outputs the following: 5 4 4 a. What can you say about the type system of the language? Is it statically typed or dynamically typed? Explain your reasoning. Answer: 3 points for something close to this reasoning: ● It is statically typed. ● Why: because y's type remains an integer even when we assign it to a floating point value (4.5) 1 point for saying it's statically typed but without reasoning b. Is either casting or conversion being performed in this code? If so, what technique(s) are being used on what line(s)? If you do identify any casts/conversions, explain for each if they are narrowing or widening. Answer: 3 points for an answer that hits both of the items below: Yes, the code is using a conversion on line 4 where it converts 4.5 into an integer value of 4. This is a narrowing conversion since it loses precision when it truncates to an integer. 1 point off for saying casting assuming everything else is right 1 point off for saying widening instead of narrowing 1 point off for failing to specify the line number c. Assuming the language used the opposite type system as the one that you answered in part a, what would the output of the program be? Answer: 5 4.5 4.5 d. Ruining likes the language so much that she built her own compiler for the language, but with some changes to the typing system. Siddarth wants to determine what typing system Ruining chose for her updated language, so he changed line 4 above to: y = “4”; and found that the program still runs and produces the same output. What can we say about the typing system for Ruining's language? Is it static or dynamic? Or is it impossible to tell? Why? Answer: 3 points for the either of following options: Ruining's language must be dynamically typed. Why? Because the language allows the y variable to be assigned to two different types over time. Ruining's language is statically typed and the string "4" undergoes conversion into an int. (must explicitly mention conversions) 2 points off if the student doesn't explain why properly.