<![CDATA[
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)
]]>