CSE341 Sample Midterm handout #8 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 words = ["live", "long", "and", "prosper"]; Expression Value ------------------------------------------------------------------------------- reduce(op *, 3--5) _______________________________ map(hd o tl, [8--12, 4--9, 7--8, 8--10]) _______________________________ map(fn x => x mod 4, 1--7) _______________________________ reduce(op +, map(fn x => x * x, 1--4)) _______________________________ filter(fn x => x mod 4 > 1, 1--12) _______________________________ map(fn x => "(" ^ x ^ ")", words) _______________________________ reduce(op @, [1--3, 4--6, 5--7]) _______________________________ map(fn x => real(x) + 0.5, 1--4) _______________________________ reduce(op +, map(size, words)) _______________________________ reduce(op *, map(fn x => 2 * x - 1, 2--4)) _______________________________ 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 = [("foo", 3), ("bar", 2), ("baz", 19)]; Expression Type ------------------------------------------------------------------------------- lst _______________________________ [tl(lst)] _______________________________ (8, [["a", "b"], ["c", "d"]]) _______________________________ fn x => (hd(x) mod 3, tl(x)) _______________________________ real o hd o tl _______________________________ 3. Scope, 5 points. What value is answer bound to after executing the following code? val y = 10; val z = 20; fun f(n, z) = let val x = 4 + y val y = let val x = 2 val z = 3 in n + x + z end in x + y + n + z end val answer = f(40, 100); 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. (4 points) Define a function sumPositives that takes a list of integers as an argument and that returns the sum of the positive values in the list. (6 points) Define a function strip that takes a list of nonempty strings as an argument and that returns the list obtained by stripping the last character from each string. For example: strip(["hello", "there", "old", "pal"]) should return ["hell", "ther", "ol", "pa"] 5. Functions, 6 points. Write a function powers(n, m) that takes integer arguments n and m and that returns a list of the powers of m from 0 to n inclusive. For example, powers(5, 2) should return [1,2,4,8,16,32] (which is 2^0, 2^1, ..., up to 2^5). Your function must run in O(n) time, which means that it should require approximately n multiplications. You may assume that n is not negative. 6. Functions, 6 points. Write a function sortedChars that takes a string s as an argument and that returns the string composed of the sorted lowercase version of the alphabetic characters from s. For example, sortedChars("Stuart Reges??") should return "aeegrrssttu". This function would be useful for finding anagrams. For example, if you make the call sortedChars("Sugar--Street"), you get the same result, indicating that these two strings are anagrams. In writing your function, you may call Char.isAlpha to test whether a character is a letter and Char.toLower to convert a letter to lowercase. 7. Functions, 11 points. Write a function interleave that takes two lists as arguments and that returns the list obtained by combining elements from the two lists in an alternating fashion. The first pair of values in the result should be the first values of the two lists. The second pair of values in the result should be the second values in the two lists. And so on. In each pair, the first value should be from the first list passed as a parameter and the second value should be from the second list passed as a parameter. For example, interleave([1, 2, 3], [10, 20, 30]) should return [1,10,2,20,3,30] while interleave([10, 20, 30], [1, 2, 3]) should return [10,1,20,2,30,3]. If one list has more values than the other, then those values should be appended after the interleaved pairs. For example, interleave([1, 2], [10, 20, 30, 40, 50]) should return [1,10,2,20,30,40,50] while interleave([1, 2, 3, 4, 5], [10, 20]) should return [1,10,2,20,3,4,5]. 8. Datatypes, 11 points. Recall the datatype we discussed in lecture for storing a binary tree of integers: datatype intTree = Empty | Node of int * intTree * intTree; (4 points) Write a function nodes that takes an intTree as a parameter and that returns a count of the number of nodes in the tree. (7 points) Write a function leaves that takes an intTree as a parameter and that returns a list of the data values stored in leaf nodes of the tree. The leaf values should be listed from left to right (i.e., in the same order in which they would be visited by any standard tree traversal). 9. Functions, 11 points. (8 points) Write a function cartesianProduct that takes two lists as arguments and that returns a list that contains each of the ordered pairs (x, y) where x is an element of the first list and y is an element of the second list. The pairs can appear in any order in the result. For example: cartesianProduct([1, 2, 3], ["a", "b"]) could return [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b")] or could return [(1,"a"),(2,"a"),(3,"a"),(1,"b"),(2,"b"),(3,"b")] These are only two possible answers because the pairs can be listed in any order in the result. If either list passed as a parameter is empty, the result should be an empty list. Your function should run in O(m * n) time where m and n are the lengths of the two lists. (3 points) Write a function product that takes two lists of integers as arguments and that returns the list of all possible products formed by multiplying a value from the first list by a value in the second list. You may assume that the lists contain no duplicates. The values may appear in any order in the result. For example, the call product([1, 2, 3], [5, 7]) should return a list of the 6 possible values obtained by multiplying one of the 3 numbers in the first list by one of the 2 numbers in the second list. One possible answer is [5,7,10,14,15,21]. You should use cartesianProduct to write your solution. As with cartesianProduct, if either list passed as a parameter is empty, the result should be an empty list. 10. Functions, 10 points. Write a function factors that takes the prime factorization of an integer as an argument and that returns a list of all of its factors. Recall that a factor of an integer is a number that goes evenly into it. For example, the factors of 24 are [1,2,3,4,6,8,12,24]. Your function will be passed a list of tuples of the form (p, n) where each tuple indicates that the number has a factor of p to the nth power where p is a prime. For example, the prime factorization of 24 is 2^3 * 3^1, so it would be represented as [(2, 3), (3, 1)]. The factors can appear in any order. For example: factors([(2, 3), (3, 1)]) could return [1,2,3,4,6,8,12,24] or it could return [1,3,2,6,4,12,8,24] Because the factors can appear in any order, these represent just two of the possible correct answers. As another example, if we wanted to compute the factors of 600, we would make this call: factors([(2, 3), (3, 1), (5, 2)]) One possible answer is: [1,5,25,3,15,75,2,10,50,6,30,150,4,20,100,12,60,300,8,40,200,24,120,600] Your function must use the prime factorization to solve this problem. You can't, for example, search for factors by checking each consecutive integer up to the square root, as we did in the bonus for homework 1. Another way of saying this is that the running time of your function has to be related to the number of factors rather than the magnitude of the factors.