CSE341 Sample Midterm handout #10 Unless otherwise noted, you may call any of the functions available in the standard top-level environment including: the standard operators (~, +, -, *, /, div, mod, ::, @, ^, o, not, andalso, orelse, <, >, <=, >=, =, <>) the numeric function abs the list functions hd, tl, length, rev, foldl, foldr the conversion functions real, trunc, floor, ceil, ord, chr, str the string functions implode, explode, concat, size the standard tuple functions #1, #2, etc. You also may call any function that is included as a problem on this exam, whether or not you correctly solve that problem. You may call the functions described below that that we have discussed (notice that these versions of map and filter replace the standard ones): fun msort(f, list) Returns the result of sorting the given list using the given comparison function where f(a, b) indicates that a < b (runs in O(n log n) time) fun m--n Returns a list of the sequential integers from m to n inclusive; returns an empty list if m > n fun map(f, list) Returns the list obtained by applying f to every value of the given list fun filter(f, list) Returns a list of the values from the given list for which f(a) is true fun reduce(f, list) For a list [x1, x2, x3, ..., xn], returns x1 for a list of length 1, otherwise returns f(x1, f(x2, f(x3, ..., f(xn-1, xn)...))) Unless otherwise specified, you can write your own helper functions, but you are not allowed to use library functions like List.nth or List.last unless they are defined in the top-level environment. Helper functions must be defined with a let so that they do not become part of the top-level environment. 1. ML Expressions, 20 points. For each ML expression in the left-hand column of the table below, indicate in the right-hand column its value. Be sure to put any string value inside double-quotations marks ("hello" vs hello). Assume that the following value has been declared: val lst = [1--2, 2--4, 17--17, 7--9, 3--6]; Expression Value ------------------------------------------------------------------------------- reduce(op *, 4--6) _______________________________ map(hd, lst) _______________________________ reduce(op +, map(length, map(tl, lst))) _______________________________ map(fn(x) => reduce(op *, x), lst) _______________________________ reduce(op @, [1--2, 2--3, 3--4]) _______________________________ filter(fn(x) => x mod 3 = 1, 1--20) _______________________________ map(fn(x) => reduce(op *, 3--x), 4--6) _______________________________ reduce(op ^, ["cs", "is", "fun"]) _______________________________ map(fn(x) => (x, 2 * x), 3--6) _______________________________ filter(fn(x, y) => x < y, [(1, 1), (2, 3), (1, 4), (5, 4), (2, 3)]) _______________________________ 2. ML Types, 10 points. For each ML expression in the left-hand column of the table below, indicate its type in the right-hand column assuming the expression was added to the standard top-level environment. Assume that the following value has been declared: val lst = [17, 9, 4, 8, 12]; Expression Type ------------------------------------------------------------------------------- lst _______________________________ (tl(lst), hd(lst)); _______________________________ fn x => round(real(x) * 1.5); _______________________________ abs o hd o hd; _______________________________ fn (x, y) => x @ [y]; _______________________________ 3. Scope, 5 points. What value is answer bound to after executing the following code? val n = 2; fun f(x) = let val y = let val y = x + n val n = 20 in x + y + n end val x = 30 in x + y + n end val n = 4; val answer = f(10); 4. Curried functions, 10 points. For this problem, in addition to being able to call the functions listed on the front page of the test, you may call the function curry and the curried versions of map, filter and reduce that we used in homework #3: fun curry f x y Returns a curried version of the 2-argument function f fun map2 f list curried version of map fun filter2 f list curried version of filter fun reduce2 f list curried version of reduce As in homework #3, you may use only val definitions to solve the following problems. You may not use "fun" or "fn" definitions to define a function. (3 points) Define a function f1(lst) that takes a list of integers as an argument and that returns the number of integers in the list that are greater than 7 (3 points) Define a function f2(ch) that takes a character as an argument and that returns the character with ordinal value one higher (e.g., f2(#"a") returns #"b") (4 points) Define a function f3(n) that returns the maximum value of a nonempty list of integers (remember that you may not use Int.max) 5. Functions, 6 points. Write a function isMagnitudeSorted that takes a list of integers and that returns true if and only if the values in the list are sorted in non-decreasing order by magnitude (i.e., absolute value). By definition, an empty list and a list of length one are sorted. 6. Functions, 6 points. Implement the list function nth that takes a list and an integer position as arguments and that returns the value at the given position in the list. As in Java, we use zero-based indexing so that the first element of the list has index 0. For example: nth([1, 8, 7, 9, 12, 15], 2) returns 7 nth(["hello", "how", "are", "you"], 1) returns "how" You may assume that the index is a legal position in the list, which means that you may also assume that your function is passed a nonempty list. 7. Functions, 11 points. Write a function median that returns the median value of a list of real numbers. The median is defined as the value with the property that half of the numbers come before it numerically and half come after it numerically. If the list has odd length, there will be exactly one median value. If the list has even length, then you should return the average of the two middle values. You may assume that your function is passed a nonempty list of reals, but you may not assume that the list is in sorted order. 8. Datatypes, 11 points. Recall the datatype we discussed in lecture for storing a binary search tree of integers: datatype intTree = Empty | Node of int * intTree * intTree; (5 points) Write a function max that takes an intTree as a parameter and that returns the maximum value in the tree as an int option. Your function should return NONE if the tree is empty and otherwise should return the maximum value. Your function must take advantage of the fact that it is a binary search tree so that it can run in O(log n) time assuming the tree has n nodes and is balanced. (6 points) Write a function atLevel that takes an int and an intTree as parameters and that returns a list of the values that appear at the given level of the tree ordered from left to right. The root is considered to be at level 0, its children are at level 1, their children are at level 2, and so on. 9. Functions, 11 points. Write a function rotations that takes a list as an argument and that returns a list of rotations of the list that involve moving values from the front of the list to the back of the list. The first value in your answer should be the original list, followed by the list obtained by rotating one value from the front to the back, followed by the list obtained by rotating two values from the front to the back and so on. For example: rotations(1--4) should return [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]] Your function should work on lists of any type. Your function should return an empty list if passed an empty list. 10. Functions, 10 points. Write a function inversions that takes a list of integers as an argument and that returns a list of the inversions in the list as a list of tuples. An inversion is a pair of numbers x and y where x occurs before y in the list and x is greater than y. For example: inversions([5, 7, 6, 8, 3, 19, 2, 24]) should return [(5,3),(5,2),(7,6),(7,3),(7,2),(6,3),(6,2),(8,3),(8,2),(3,2),(19,2)] The value 5 has two inversions because later in the list we find the values 3 and 2, which are less than 5. Similarly the value 7 has three inversions because later in the list we find the values 6, 3 and 2 which are less than 7. The inversions may appear in any order in your answer, so the answer above is just one possible correct answer. The list may contain duplicates, as in: inversions([5, 3, 7, 3, 1, 9, 3, 12]) should return [(5,3),(5,3),(5,1),(5,3),(3,1),(7,3),(7,1),(7,3),(3,1),(9,3)] Notice that each duplicate can generate an inversion, as in the 3 occurrences of (5,3) and the two occurrences of (3,1).