Key to CSE341 Sample Midterm handout #12
1. Expression Value
----------------------------------------------------------------------
reduce(op +, 4--7) 22
reduce(op *, map(hd, lst)) 504
filter(fn(x) => x mod 3 = 1, 0--15) [1,4,7,10,13]
map(fn(x) => reduce(op +, x), lst) [24,14,12,39]
map(fn(x) => real(x) + 0.25, 8--11) [8.25,9.25,10.25,11.25]
filter(fn(x) => length(x) = 3, lst) [[7,8,9],[3,4,5],[12,13,14]]
map(fn(x) => [x, x + 3], 3--6) [[3,6],[4,7],[5,8],[6,9]]
reduce(op +, map(real, 5--8)) 26.0
map(length, map(fn(x) => 3--x, 3--6)) [1,2,3,4]
reduce(op +, map(hd, map(tl, lst))) 28
2. Expression Type
----------------------------------------------------------------------
lst (string * int) list
hd(tl(lst)) string * int
tl(tl(lst)) (string * int) list
fn x => (trunc(x), x) real -> int * real
fn (x, y) => (y, x) 'a * 'b -> 'b * 'a
3. The output for standard Java is:
14
3
28
5
The output for dynamic Java is:
6
6
10
10
The binding is:
val answer = 3
4. One possible solution appears below.
val f1 = (curry op* 2.8) o real;
val f2 = (curry op mod 13) o (curry op* 2);
val f3 = filter2 (curry op> 100);
5. One possible solution appears below.
fun take(_, 0) = []
| take(a::rest, n) = a::take(rest, n - 1);
6. One possible solution appears below.
fun drop(lst, 0) = lst
| drop(a::rest, n) = drop(rest, n - 1);
7. One possible solution appears below.
fun insert(x, []) = [] |
insert(x, a::rest) = (x::a)::insert(x, rest);
8. One possible solution appears below.
fun length(Empty) = 0
| length(Node(x, lst)) = 1 + length(lst);
fun insertSorted(Empty, n) = Node(n, Empty)
| insertSorted(Node(x, lst), n) =
if n <= x then Node(n, Node(x, lst))
else Node(x, insertSorted(lst, n));
9. One possible solution appears below.
fun subsets([]) = [[]] |
subsets(a::rest) =
let val sub = subsets(rest)
in sub @ insert(a, sub)
end;