- Open Book, Open Notes
- Time limit: 50 minutes
- Answer the problems on the exam paper.
- If you need extra space use the back of a page
- Problems are not of equal difficulty, if you get stuck on a problem, move on.

Evaluate the following ML expressions (you do not need to give the types). These are all legal ML expressions. 1. rev [[1, 2], [3, 4], [5, 6]]; val it = [[5,6],[3,4],[1,2]] : int list list 2. map tl [[1, 2], [3, 4], [5, 6]]; val it = [[2],[4],[6]] : int list list 3. map (fn x => hd x + hd (tl x)) [[1, 2], [3, 4], [5, 6]]; val it = [3,7,11] : int list 4. hd (tl [[1, 2], [3, 4], [5, 6]]); val it = [3,4] : int list 5. tl (tl [[1, 2], [3, 4], [5, 6]]); val it = [[5,6]] : int list list 6. length [[1, 2], [3, 4], [5, 6]]; val it = 3 : int 7. (fn x => hd x @ hd (tl (tl x))) [[1, 2], [3, 4], [5, 6]]; val it = [1,2,5,6] : int list

Give ML expressions that do the following. (Do not give function definitions). 1. Determines if exactly one of the booleans x and y are true. -- This is the solution I expected: (x andalso not y) orelse (not x andalso y); -- And here is the simplest x <> y; 2. Removes the second element from a list L. (Assume that L has at least two elements.) -- This is what I intended (hd L) :: tl (tl L); -- but many of you interpreted this as getting the second element hd (tl L); 3. Converts all of the characters of a string S to upper case. You may use the function toUpper. The result should also be a string. implode (map toUpper (explode S)); 4. (Tricky) Adds one to each integer in a list L of lists of integers. (So the list[[1, 2], [3, 4, 5]] is converted to [[2, 3], [4, 5, 6]]). map (map (fn x => x + 1)) L;

Use the following datatype to represent a binary tree: datatype binTree = Leaf of int | Node of binTree * binTree; 1. Write a function which adds up the values of all of the leaves of a tree. fun addUp (Leaf x) = x | addUp (Node (t1,t2)) = (addUp t1) + (addUp t2); 2. Write a function where the ``summation'' operation is supplied to the function, so that it can be used to compute an arbitrary ``sum'' of the tree nodes (e.g., compute their product or the maximum). This is similar to Reduce for lists. fun treeReduce1 f (Leaf x) = x | treeReduce1 f (Node (t1,t2)) = f (treeReduce1 f t1) (treeReduce1 f t2); -- a slight variant fun treeReduce2 f (Leaf x) = x | treeReduce2 f (Node (t1,t2)) = f (treeReduce2 f t1,treeReduce2 f t2); 3. How would you call your function to compute the product of the leaf values? treeReduce1 (fn x => (fn y => x*y)) tree; fun times x y = x * y; treeReduce1 times tree; treeReduce2 (op * ) tree; treeReduce2 (fn (x,y) => x*y) tree;Problem 4 (15 points)

Write the following functions using patterns: 1. Given a list of integers, create a new list by summing adjacent pairs. (If there are an odd number of elements, the last element is added to 0.) Thus, the list [1, 2, 3, 4, 5] gives the result [3, 7, 5]. fun sumPairs nil = nil | sumPairs [a] = [a] | sumPairs (x :: y :: ys) = (x+y) :: sumPairs ys; 2. Test if a list of strings contains the string "A" followed immediately by the string "B". Thus, the test would be true for the ["X", "A", "B", "Y"] but false for the list ["B", "A", "X", "B"]. fun abTest nil = false | abTest ("A"::"B"::_) = true | abTest (x :: xs) = abTest xs;Problem 5 (15 points)

Give short answers to the following questions: 1. When is it necessary to declare the types of variables in ML? Declarations are necessary if the types cannot be infered. (SML97 has introduced default types - so it may also be necessary to declare types if the defaults are not right.) 2. How does value binding in ML differ from assignment in an imperative programming language? New bindings are created, without overwriting old bindings. In imperative programming, a new assignment replaces an old value. 3. When does an ML program allocate and deallocate memory? Memory is allocated automatically when tuples or list cells are needed. Memory is deallocated by the garbage collector. The system determines the frequency of garbage collection. 4. Why do proponents of Functional Programming consider side effects to be evil? One problem that side effects create is that the value of a function may depend on more than just the values that it is called with - so it is not possible to predicts its results. 5. What is a benefit of having functions as first class values? Groups of functions with common behavior can be combined together into single higher order functions, reducing the amount of code, and hopefully increasing clarity.Problem 6 (15 points)

Write a function which determines the number of occurrences of each string in a list of strings. The input is a list of strings, and the output is a list of string/integer pairs, giving the number of occurrences of each string in the list. For example, if the input is: ["A", "B", "A", "C", "B", "B", "D", "C"], the output is [("A", 2), ("B", 3), ("C", 2), ("D", 1)]. The tuples may appear in any order. You may want define and use additional functions. Please provide a brief description of your algorithm to help with the grading. -- This algorithm works by counting the number of occurences of the head -- in the list, and then deletes all occurences of the head before -- making the recursive call fun count x nil = 0 | count x (y :: ys) = if (x = y) then 1 + count x ys else count x ys; fun delete x nil = nil | delete x (y :: ys) = if (x = y) then delete x ys else y :: delete x ys; fun tuplize nil = nil | tuplize (x :: xs) = ( x, count x xs + 1) :: tuplize (delete x xs); -- insertTuple adds an element to a list of pairs, counting occurrences, -- if a value is not presenet, a new pair is created. The main routine -- then inserts all the elements into this list of pairs fun insertTuple s nil = [(s, 1)] | insertTuple s (x::xs) = if (s = #1 x) then (s, 1 + #2 x) :: xs else x :: insertTuple s xs; fun countStrings nil = nil | countStrings (x :: xs) = insertTuple x (countStrings xs); -- A similar idea to above, except the list is passed as a variable (which -- causes the output to come out in a different order). fun add1 str nil = [(str, 1)] | add1 str ((s, n) :: xs) = if (s = str) then (str, n+1) :: xs else (s, n) :: add1 str xs; fun countPairs nil a = a | countPairs (x :: xs) a = countPairs xs (add1 x a);