<![CDATA[
Key to CSE341/413 Midterm, Spring 2026 handout #7
1. Expression Value
-------------------------------------------------------------------------------
reduce(uncurry( * ), 4--6) 120
map(List.hd, lst) [1; 2; 17; 7; 3]
reduce(uncurry(+), map(List.length,
map(List.tl, lst))) 8
map((fun x -> reduce(uncurry( * ), x)), lst) [2; 24; 17; 504; 360]
reduce(uncurry(@), [1--2; 2--3; 3--4]) [1; 2; 2; 3; 3; 4]
filter((fun x -> x mod 3 = 1), 1--20) [1; 4; 7; 10; 13; 16; 19]
map((fun x -> reduce(uncurry( * ), 3--x)),
4--6) [12; 60; 360]
reduce(uncurry(^), ["cs"; "is"; "fun"]) "csisfun"
map((fun x -> (x, 2 * x)), 3--6) [(3, 6); (4, 8); (5, 10); (6, 12)]
filter((fun (x, y) -> x < y),
[(1, 1); (2, 3); (1, 4); (5, 4); (2, 3)]) [(2, 3); (1, 4); (2, 3)]
2. Expression Type
-------------------------------------------------------------------------------
lst int list
(List.tl(lst), List.hd(lst)) int list * int
fun x -> Float.round(float_of_int(x) *. 1.5) int -> float
abs % List.hd % List.hd int list list -> int
fun (x, y) -> x @ [y] 'a list * 'a -> 'a list
3. The binding is:
val answer = 74
4. One possible solution appears below.
let insert_42 = map2 ((@) [42])
let starts_with_42 = filter2 ((=) 42 % List.hd)
5. One possible solution appears below.
let rec permut(n, m) =
if n < 0 || m < 0 || n < m then invalid_arg("no solution")
else if m = 0 then 1
else n * permut(n - 1, m - 1)
6. One possible solution appears below.
let difference(lst1, lst2) =
let sum(lst) = reduce(uncurry (+), 0::lst)
in sum(lst1) - sum(lst2)
7. One possible solution appears below.
let rec delta(lst1, lst2) =
match (lst1, lst2) with
| ([], []) -> 0
| ([], y::ys) -> abs(y) + delta([], ys)
| (x::xs, []) -> abs(x) + delta(xs, [])
| (x::xs, y::ys) -> abs(x - y) + delta(xs, ys)
8. One possible solution appears below.
let rec remove_leaves(tree) =
match tree with
| Empty -> Empty
| Node(_, Empty, Empty) -> Empty
| Node(root, left, right) ->
Node(root, remove_leaves(left), remove_leaves(right))
let rec add(tree1, tree2) =
match (tree1, tree2) with
| (t1, Empty) -> t1
| (Empty, t2) -> t2
| (Node(root1, left1, right1), Node(root2, left2, right2)) ->
Node(root1 + root2, add(left1, left2), add(right1, right2))
9. One possible solution appears below.
let similar(lst) =
let rec helper(lst) =
match lst with
| [] -> []
| x::xs -> map((fun y -> (delta(x, y), x, y)), xs) @ helper(xs)
in qsort(uncurry (<), helper(lst))
10. One possible solution appears below.
let partitions(lst) =
let rec helper(rest, part1, part2) =
match rest with
| [] -> if difference(part1, part2) = 0 then [(part1, part2)]
else []
| x::xs -> helper(xs, x::part1, part2) @
helper(xs, part1, x::part2)
in helper(lst, [], [])
]]>