Key to CSE341 Sample Midterm handout #14
1. Expression Value
------------------------------------------------------------------------
map(hd, map(tl, lst)) [8,3,4,13]
map(fn x => reduce(op +, x), tl(lst)) [14,12,39]
map(fn(x, y) => x + y, [(1, 3), (4, 5)]) [4,9]
reduce(op *, map(length, lst)) 108
filter(fn(x) => x div 4 = 2, 1--15) [8,9,10,11]
length(reduce(op @, lst)) 13
map(fn(x) => x * x, map(hd, lst)) [49,4,9,144]
map(fn(x) => (x, 2 * x), 1--4) [(1,2),(2,4),(3,6),(4,8)]
reduce(op +, map(fn(x) => 2 * x - 4, 10--15)) 126
map(fn(x) => 2--x, 3--5) [[2,3],[2,3,4],[2,3,4,5]]
2. Expression Type
-------------------------------------------------------------------------
lst int list list
(hd(lst), hd(hd(lst)) int list * int
hd o rev fn : string -> char
fn x => x::[x] fn : 'a -> 'a list
fn (x, y) => ((x + y), x, y) fn : int * int -> int * int * int
3. The output for standard Java is:
18
23
28
143
38
163
4
6
The output for dynamic Java is:
14
26
12
146
24
27
24
146
The binding is:
val answer = 20
4. One possible solution appears below.
val f1 = hd o rev o explode;
val f2 = (curry op<> 0) o (curry op mod 120);
val f3 = map2 (curry op* 2) o (curry op-- 1);
5. One possible solution appears below.
fun member(a, []) = false
| member(a, b::rest) = (a = b) orelse member(a, rest);
6. One possible solution appears below.
fun pow2(n) =
let fun explore(0, pow) = []
| explore(m, pow) = pow::explore(m - 1, pow * 2)
in explore(n, 1)
end;
7. Two possible solutions appear below.
fun partitionModN(lst, n) = qsort(fn(x, y) => x mod n < y mod n, lst);
fun partitionModN(lst, n) = reduce(op@,
map(fn(x) => filter(fn(y) => y mod n = x, lst), 0--(n - 1)));
8. One possible solution appears below.
fun product(Empty) = 1
| product(Node(n, left, right)) = n * product(left) * product(right);
fun sameStructure(Empty, Empty) = true
| sameStructure(Node(n1, left1, right1), Node(n2, left2, right2)) =
sameStructure(left1, left2) andalso sameStructure(right1, right2)
| sameStructure(t1, t2) = false;
9. One possible solution appears below.
fun adjacent(v, lst) = map(#2, filter(fn(x, y) => x = v, lst));
10. One possible solution appears below.
fun reachable(v, lst) =
let fun explore([], found) = found
| explore(a::rest, found) =
if member(a, found) then explore(rest, found)
else explore(rest @ adjacent(a, lst), a::found)
in explore(adjacent(v, lst), [])
end;