CSE341 Sample Midterm handout #6 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 numbers = [3, 4, 9]; Expression Value ------------------------------------------------------------------------------- reduce(op +, numbers) _______________________________ map(fn x => x--(x+1), numbers) _______________________________ map(length o tl, [1--5, 3--5, 5--5, 2--5]) _______________________________ filter(fn x => 24 mod x = 0, 1--7) _______________________________ reduce(op *, map(fn x => x - 1, numbers)) _______________________________ map(fn x => (x, x), numbers) _______________________________ reduce(op +, map(fn x => 2 * x - 1, 1--5)) _______________________________ reduce(op @, map(fn x => [x, x], numbers)) _______________________________ filter(fn x => x div 4 = 3, 1--15) _______________________________ implode(map(hd o rev o explode, ["foo","bar","baz"])) _______________________________ 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 = ["to", "be", "or", "not", "to", "be"]; Expression Type ------------------------------------------------------------------------------- lst _______________________________ (lst, lst) _______________________________ [lst, lst] _______________________________ fn x => (x, [[x + 1], [x + 2]]) _______________________________ fn (x, y) => [(x, 1), (2, y)] _______________________________ 3. Scope, 5 points. What value is answer bound to after executing the following code? val x = 40; val y = 5; val z = 25; fun f(x) = let val z = let val y = 2 val x = 10 in x + y end val y = x - 5 val x = y - 5 in x + y + z end val answer = f(20); 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 product that takes a list of integers as an argument and that returns the product of the nonzero values in the list. For example, product([2, 0, 3, 0, 4]) should return 24. You may assume there is at least one nonzero value in the list. (6 points) Define a function starString that takes a list of strings as an argument and that returns a new string obtained by concatenating the strings together with an asterisk in front of each. For example: starString(["one"]) should return "*one" starString(["foo", "bar", "baz"]) should return "*foo*bar*baz" starString(["a", "b", "c", "d"]) should return "*a*b*c*d" You may assume the list has at least one string. 5. Functions, 6 points. Write a function zip that takes two lists as arguments and that returns the list obtained by combining pairs of values in corresponding positions into tuples. The first tuple should contain the first values from each list. The second tuple should contain the second values from each list. And so on. If one list is shorter than the other, then zip should return a list of that shorter length. For example: zip([1, 2, 3], ["a", "b", "c"]) should return [(1,"a"),(2,"b"),(3,"c")] zip([1, 2, 3, 4, 5], ["a", "b", "c", "d"]) should return [(1,"a"),(2,"b"),(3,"c"),(4,"d")] zip(["a", "b", "c", "d"], [1, 2]) should return [("a",1),("b",2)] 6. Functions, 6 points. Write a function digitSum that takes an integer n as an argument and that returns the sum of the digits of n. For example: digitSum(384) should return 15 digitSum(333) should return 9 digitSum(~71) should return 8 digitSum(0) should return 0 digitSum(208034239) should return 31 7. Functions, 11 points. Write a function maxSizeSublist that takes a list of strings and an integer n as arguments and that returns a list of n of those strings whose sizes are maximal. In other words, the function is picking the n elements of the list that have the greatest size. Any given string can be used only once. Assume that the list contains no duplicates. The list you return can be in any order and if there is more than one list of maximal size, then you can return any one of them. For example: maxSizeSublist(["four", "score", "and", "seven", "years", "ago"], 1) could return ["seven"] maxSizeSublist(["four", "score", "and", "seven", "years", "ago"], 3) could return ["seven","score","years"] maxSizeSublist(["aaaa", "b", "cc", "ddd", "eeeee"], 3) could return ["eeeee","aaaa","ddd"] Recall that the function called size is used to find the size of a string. You may assume that the parameter n is greater than or equal to 0 and that it is less than or equal to the length of the list. 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; (5 points) Write a function sameStructure that takes two intTrees as arguments and that returns whether or not the two trees have the same structure (true if they do, false otherwise). Two trees are considered to have the same structure if they have the same number of nodes in the same relative positions (the data stored in the tree doesn't matter). (6 points) Write a function atLevel that takes an intTree and an integer n as arguments and that returns a list of the data values stored at level n in the tree. The overall root is considered to be at level 1, its children are at level 2, its grandchildren are at level 3, and so on. The 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). You may assume that n is greater than or equal to 1. 9. Functions, 10 points. Write a function sameDigitSum that takes two lists of integers and that returns a list of all (x, y) tuples where x is from the first list, y is from the second list, both are in the same position in their respective lists, and both have the same digit sum. For example: sameDigitSum([13, 8, 72, 308], [202, 13, 308, 2020403]) should return [(13,202),(308,2020403)] The first pair of numbers has a digit sum of 4 and the second pair of numbers has a digit sum of 11. Notice that we don't get (13, 13) as an answer even though the number 13 appears in both lists. That match doesn't appear because the two occurrences of 13 are in different positions in the list. Also notice that the pairs should be listed in the order in which they appear in the original lists. Notice that one list can be shorter than the other. For example: sameDigitSum([12, 42, 73], [111, 55, 82, 19, 201, 24]) should return [(12,111),(73,82)] 10. Functions, 11 points. Write a function combine that takes a list of integers and a minimum value n as arguments and that returns a list of tuples formed by combining sequences of sequential values from the list so that their sum is greater than or equal n. Your function should combine values from the front of the list by adding them up until their sum is at least n. Once you have a sum that is at least n, you should include a tuple in the result that includes the count of values combined and the sum. The function should then combine values again until it finds a sum that is at least n and should include a count/sum tuple for that group of combined values. It should continue combining values in this way until it reaches the end of the list. For example: combine([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 10) should return [(4,10),(2,11),(2,15),(2,19),(1,11),(1,12)] This result indicates that the first 4 values from the list were combined for a sum of 10 (the values 1, 2, 3, and 4), then 2 values were combined for a sum of 11 (the values 5 and 6), then 2 values were combined for a sum of 15 (the values 7 and 8), then 2 values were combined for a sum of 19 (the values 9 and 10), then 1 value was combined for a sum of 11 (the value 11), and finally 1 value was combined for a sum of 12 (the value 12). It is possible that your function will run out of values to combine at the end of the list, so that the final sum might not be greater than or equal to n. That is okay. For example: combine([3, 8, 7, 6, 12, 2, 4, 7, 2, 9, 5, 2], 11) should return [(2,11),(2,13),(1,12),(3,13),(2,11),(2,7)] Notice that the final tuple has a sum of 7, which is less than the 11 minimum we are trying to achieve. This should happen only for the last sequence of numbers combined. You may assume that all of the numbers in the list are positive. If there are no values to combine, your function should return an empty list.