Key to CSE341 Sample Midterm       handout #11

1. 	Expression				Value
	-----------------------------------------------------------------------
	reduce(op *, 4--6)			120
	map(hd, lst)				[1,2,17,7,3]
	reduce(op +, map(length, map(tl, lst))) 8
	map(fn(x) => reduce(op *, x), lst)	[2,24,17,504,360]
	reduce(op @, [1--2, 2--3, 3--4])	[1,2,2,3,3,4]
	filter(fn(x) => x mod 3 = 1, 1--20)	[1,4,7,10,13,16,19]
	map(fn(x) => reduce(op *, 3--x), 4--6)	[12,60,360]
	reduce(op ^, ["cs", "is", "fun"])	"csisfun"
	map(fn(x) => (x, 2 * x), 3--6)		[(3,6),(4,8),(5,10),(6,12)]
	filter(fn(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
     (tl(lst), hd(lst));		     int list * int
     fn x => round(real(x) * 1.5);	     int -> int
     abs o hd o hd;			     int list list -> int
     fn (x, y) => x @ [y];		     'a list * 'a -> 'a list

3.  The binding is:

        val answer = 74

4. One possible solution appears below.

        val f1 = length o (filter2 (curry op< 7));
        val f2 = chr o (curry op+ 1) o ord;
        val f3 = hd o (curry msort op>=)

5. One possible solution appears below.

        fun isMagnitudeSorted([]) = true
        |   isMagnitudeSorted([x]) = true
        |   isMagnitudeSorted(a::b::rest) =
                abs(a) <= abs(b) andalso isMagnitudeSorted(b::rest);

6. One possible solution appears below.

        fun nth(a::_, 0) = a
        |   nth(_::rest, n) = nth(rest, n - 1);

7. One possible solution appears below.

        fun median(lst) =
            let val n = length(lst)
                val half = n div 2;
                val lst2 = msort(op <, lst)
            in
                if n mod 2 = 1 then nth(lst2, half)
        	else (nth(lst2, half - 1) + nth(lst2, half)) / 2.0
            end;

8. One possible solution appears below.

        fun max(Empty) = NONE
        |   max(Node(root, _, Empty)) = SOME root
        |   max(Node(_, _, right)) = max(right);
        
        fun atLevel(_, Empty) = []
        |   atLevel(0, Node(root, _, _)) = [root]
        |   atLevel(n, Node(_, left, right)) = 
                atLevel(n - 1, left) @ atLevel(n - 1, right);

9. One possible solution appears below.

        fun rotations([]) = []
        |   rotations(lst) =
                let fun process(x::xs, n) =
        	    if n = 0 then []
        	    else (x::xs)::process(xs @ [x], n - 1)
        	in process(lst, length(lst))
        	end

10. One possible solution appears below.

        fun inversions([]) = []
        |   inversions(a::rest) =
             map(fn(x) => (a, x), 
                 filter(fn(x) => x < a, rest)) @ inversions(rest);