Key to CSE341 Sample Midterm       handout #7

1. 	Expression					Value
	-----------------------------------------------------------------------
        reduce(op +, numbers)				16
        map(fn x => x--(x+1), numbers)			[[3,4],[4,5],[9,10]]
        map(length o tl, [1--5, 3--5, 5--5, 2--5])	[4,2,0,3]
        filter(fn x => 24 mod x = 0, 1--7)		[1,2,3,4,6]
        reduce(op *, map(fn x => x - 1, numbers))	48
        map(fn x => (x, x), numbers)			[(3,3),(4,4),(9,9)]
        reduce(op +, map(fn x => 2 * x - 1, 1--5))	25
        reduce(op @, map(fn x => [x, x], numbers))	[3,3,4,4,9,9]
        filter(fn x => x div 4 = 3, 1--15)		[12,13,14,15]
        implode(map(hd o rev o explode,			
            ["foo","bar","baz"]))			"orz"

2.   Expression                              Type
     -------------------------------------------------------------------------
     lst       	 			    string list
     (lst, lst)				    string list * string list
     [lst, lst]			  	    string list list
     fn x => (x, [[x + 1], [x + 2]])	    int -> int * int list list
     fn (x, y) => [(x, 1), (2, y)]	    int * int -> (int * int) list

3.  The binding is:
        val answer = 37

4. One possible solution appears below.
        val product = reduce2 op* o (filter2 (curry op<> 0));
        val starString = reduce2 op^ o (map2 (curry op^ "*"));

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

6. One possible solution appears below.
        fun digitSum(n) =
            if n < 0 then digitSum(~n)
            else if n < 10 then n
            else digitSum(n div 10) + n mod 10;

7. One possible solution appears below.
        fun maxSizeSublist(lst, n) =
            let fun helper(_, 0) = []
                |   helper(x::xs, m) = x::helper(xs, m - 1)
            in helper(msort(fn (x, y) => size(x) >= size(y), lst), n)
            end;

8. One possible solution appears below.
        fun sameStructure(Empty, Empty) = true
        |   sameStructure(Empty, Node(_, left, right)) = false
        |   sameStructure(Node(_, left, right), Empty) = false
        |   sameStructure(Node(_, left1, right1), Node(_, left2, right2)) = 
            sameStructure(left1, left2) andalso sameStructure(right1, right2);

        fun atLevel(Empty, _) = []
        |   atLevel(Node(root, left, right), 1) = [root]
        |   atLevel(Node(_, left, right), n) = 
                atLevel(left, n - 1) @ atLevel(right, n - 1);
        
9. One possible solution appears below.
        fun sameDigitSum(lst1, lst2) =
            filter(fn (x, y) => digitSum(x) = digitSum(y), zip(lst1, lst2));

10. One possible solution appears below.
        fun combine([], _) = []
        |   combine(x::xs, min) =
                let fun process([], sum, count) = [(count, sum)]
        	    |   process(x::xs, sum, count) =
        	            if sum < min then process(xs, sum + x, count + 1)
        		    else (count, sum)::process(xs, x, 1)
        	in process(xs, x, 1)
        	end;