<![CDATA[
Key to CSE341 Midterm, Spring 2024 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 is_magnitude_sorted(lst) =
match lst with
| [] -> true
| [x] -> true
| x::y::zs -> abs(x) <= abs(y) && is_magnitude_sorted(y::zs)
6. One possible solution appears below.
let rec nth(list, n) =
match (list, n) with
| (x::_, 0) -> x
| (_::rest, n) -> nth(rest, n - 1)
7. One possible solution appears below.
let median(lst) =
let n = List.length(lst)
in let half = n / 2
in let lst2 = qsort(uncurry(<), lst)
in if n mod 2 = 1 then nth(lst2, half)
else (nth(lst2, half - 1) +. nth(lst2, half)) /. 2.0
8. One possible solution appears below.
let rec product(tree) =
match tree with
| Empty -> 1
| Node(root, left,right) -> root * product(left) * product(right)
let rec leaf_product(tree) =
match tree with
| Empty -> 1
| Node(root, Empty, Empty) -> root
| Node(root, left,right) -> leaf_product(left) * leaf_product(right)
9. One possible solution appears below.
let rotations(lst) =
match lst with
| [] -> []
| lst ->
let rec process(x::xs, n) =
if n = 0 then []
else (x::xs)::process(xs @ [x], n - 1)
in process(lst, List.length(lst))
10. One possible solution appears below.
let rec inversions(lst) =
match lst with
| [] -> []
| a::rest -> map((fun x -> (a, x)),
filter((fun x -> x < a), rest)) @ inversions(rest)
]]>