<![CDATA[
Key to CSE413 Midterm handout #6
1. Expression Value
-----------------------------------------------------------------------
map(List.hd, map(List.tl, lst)) [8; 3; 4; 13]
map((fun x -> reduce(uncurry(+), x)),
List.tl(lst)) [14; 12; 39]
map((fun (x, y) -> x + y), [(1, 3); (4, 5)]) [4; 9]
reduce(uncurry( * ), map(List.length, lst)) 108
filter((fun x -> x/4 = 2), 1--15) [8; 9; 10; 11]
List.length(reduce(uncurry(@), lst)) 13
map((fun x -> x * x), map(List.hd, lst)) [49; 4; 9; 144]
map((fun x -> (x, 2 * x)), 1--4) [(1, 2); (2, 4);
(3, 6); (4, 8)]
reduce(uncurry(+),
map((fun x -> 2 * x - 4), 10--15)) 126
map((fun x -> 2--x), 3--5) [[2; 3]; [2; 3; 4];
[2; 3; 4; 5]]
2. Expression Type
-------------------------------------------------------------------------
lst int list list
(List.hd(lst), List.hd(List.hd(lst))) int list * int
List.hd % reverse % explode string -> char
fun x -> x::[x + 1] int -> int list
fun (x, y) -> ((x + y), x, y) int * int -> int * int * int
3. The binding is:
val answer = 20
4. One possible solution appears below.
let f1 = List.hd % reverse % explode
let f2 = (<>) 0 % (mod) 120
let f3 = map2 (( * ) 2) % (--) 1
5. One possible solution appears below.
let rec member(a, lst) =
match lst with
| [] -> false
| b::rest -> a = b || member(a, rest)
6. One possible solution appears below.
let rec stutter(lst) =
match lst with
| [] -> []
| x::xs -> x::x::stutter(xs)
7. Two possible solutions appear below.
let partition_mod_n(lst, n) =
qsort((fun (x, y) -> x mod n < y mod n), lst)
let partition_mod_n2(lst, n) = reduce(uncurry(@),
map((fun x -> filter((fun y -> y mod n = x), lst)),
0--(n - 1)))
8. One possible solution appears below.
let rec product(t) =
match t with
| Empty -> 1
| Node(n, left, right) -> n * product(left) * product(right)
let rec same_structure(t1, t2) =
match (t1, t2) with
| (Empty, Empty) -> true
| (Node(_, left1, right1), Node(_, left2, right2)) ->
same_structure(left1, left2) && same_structure(right1, right2)
| _ -> false
9. One possible solution appears below.
let adjacent(v, lst) =
map((fun (a, b) -> b), filter((fun (x, y) -> x = v), lst))
10. One possible solution appears below.
let reachable(v, lst) =
let rec explore(list, found) =
match list with
| [] -> found
| a::rest ->
if member(a, found) then explore(rest, found)
else explore(rest @ adjacent(a, lst), a::found)
in explore(adjacent(v, lst), [])
]]>