Key to CSE341 Sample Midterm       handout #9

1. 	Expression					Value
	-----------------------------------------------------------------------
	reduce(op *, 3--5)                              60
	map(hd o tl, [8--12, 4--9, 7--8, 8--10])        [9,5,8,9]
	map(fn x => x mod 4, 1--7)                      [1,2,3,0,1,2,3]
	reduce(op +, map(fn x => x * x, 1--4))          30
	filter(fn x => x mod 4 > 1, 1--12)              [2,3,6,7,10,11]
	map(fn x => "(" ^ x ^ ")", words)               ["(live)","(long)",
							 "(and)","(prosper)"]
	reduce(op @, [1--3, 4--6, 5--7])                [1,2,3,4,5,6,5,6,7]
	map(fn x => real(x) + 0.5, 1--5)                [1.5,2.5,3.5,4.5]
	reduce(op +, map(size, words))			18
	reduce(op *, map(fn x => 2 * x - 1, 2--4))      105

2.   Expression                              Type
     -------------------------------------------------------------------------
     lst				    (string * int) list 
     [tl(lst)]				    (string * int) list list
     (8, [["a", "b"], ["c", "d"]])	    int * string list list
     fn x => (hd(x) mod 3, tl(x))	    int list ->  int * int list
     real o hd o tl 	   		    int list -> real

3.  The binding is:
        val answer = 199

4. One possible solution appears below.
        val sumPositives = reduce2 op+ o (filter2 (curry op< 0));
        val strip = map2 (implode o rev o tl o rev o explode);

5. One possible solution appears below.
        fun powers(n, m) =
            let fun loop(0, product) = [product]
                |   loop(i, product) = product::loop(i - 1, product * m)
            in loop(n, 1)
            end;
        powers(5, 2);

6. One possible solution appears below.
        fun sortedChars(s) = implode(msort(op <=, map(Char.toLower, 
                                 filter(Char.isAlpha, explode(s)))));

7. One possible solution appears below.
        fun interleave([], ys) = ys
        |   interleave(xs, []) = xs
        |   interleave(x::xs, y::ys) = x::y::interleave(xs, ys);

8. One possible solution appears below.
        fun nodes(Empty) = 0
        |   nodes(Node(_, left, right)) = 1 + nodes(left) + nodes(right);
        
        fun leaves(Empty) = []
        |   leaves(Node(root, Empty, Empty)) = [root]
        |   leaves(Node(_, left, right)) = leaves(left) @ leaves(right);
        
9. One possible solution appears below.
        fun cartesianProduct([], _) = []
        |   cartesianProduct(x::xs, ys) =
                map(fn y => (x, y), ys) @ cartesianProduct(xs, ys);
        
        fun product(xs, ys) = map(fn (x, y) => x * y, cartesianProduct(xs, ys));

10. One possible solution appears below.
        fun factors([(p, n)]) = powers(n, p)
        |   factors((p, n)::rest) = product(powers(n, p), factors(rest));