Key to CSE413 Sample Midterm handout #4 1. Expression Value ----------------------------------------------------------------------- reduce(uncurry(+), numbers) 16 map((fun x -> x--(x+1)), numbers) [[3; 4]; [4; 5]; [9; 10]] map(List.length % List.tl, [1--5; 3--5; 5--5; 2--5]) [4; 2; 0; 3] filter((fun x -> 24 mod x = 0), 1--7) [1; 2; 3; 4; 6] reduce(uncurry( * ), map((fun x -> x - 1), numbers)) 48 map((fun x -> (x, x)), numbers) [(3, 3); (4, 4); (9, 9)] reduce(uncurry(+), map((fun x -> 2 * x - 1), 1--5)) 25 reduce(uncurry(@), map((fun x -> [x; x]), numbers)) [3; 3; 4; 4; 9; 9] filter((fun x -> x/4 = 3), 1--15) [12; 13; 14; 15] implode(map(List.hd % reverse % explode, ["foo"; "bar"; "baz"])) "orz" 2. Expression Type ------------------------------------------------------------------------- lst string list (lst, lst) string list * string list [lst; lst] string list list fun x -> (x, [[x + 1]; [x + 2]]) int -> int * int list list fun (x, y) -> [(x, 1); (2, y)] int * int -> (int * int) list 3. The binding is: val answer = 37 4. One possible solution appears below. let product = reduce2 ( * ) % (filter2 ((<>) 0)) let star_string = reduce2 (^) % (map2 ((^) "*")) 5. One possible solution appears below. let rec zip(lst1, lst2) = match (lst1, lst2) with | (_, []) -> [] | ([], _) -> [] | (x::xs, y::ys) -> (x, y)::zip(xs, ys) 6. One possible solution appears below. let rec digit_sum(n) = if n < 0 then digit_sum(-n) else if n < 10 then n else digit_sum(n / 10) + n mod 10 7. One possible solution appears below. let max_size_sublist(lst, n) = let rec helper(l, n) = match (l, n) with | (_, 0) -> [] | (x::xs, m) -> x::helper(xs, m - 1) in helper(qsort( (fun (a, b) -> String.length(a) > String.length(b)), lst), n) 8. One possible solution appears below. let rec same_structure(t1, t2) = match (t1, t2) with | (Empty, Empty) -> true | (Empty, Node(_, left, right)) -> false | (Node(_, left, right), Empty) -> false | (Node(_, left1, right1), Node(_, left2, right2)) -> same_structure(left1, left2) && same_structure(right1, right2) let rec at_level(tree, n) = match (tree, n) with | (Empty, _) -> [] | (Node(root, left, right), 1) -> [root] | (Node(_, left, right), n) -> at_level(left, n - 1) @ at_level(right, n - 1) 9. One possible solution appears below. let same_digit_sum(lst1, lst2) = filter((fun (x, y) -> digit_sum(x) = digit_sum(y)), zip(lst1, lst2)) 10. One possible solution appears below. let combine(lst, min) = match lst with | [] -> [] | x::xs -> let rec process(lst, sum, count) = match lst with | [] -> [(count, sum)] | x::xs -> if sum < min then process(xs, sum + x, count + 1) else (count, sum)::process(xs, x, 1) in process(xs, x, 1)
Stuart Reges
Last modified: Wed Feb 7 15:01:20 PST 2024