CSE 341, ML Quiz, Autumn 1997

Quiz 1, October 21, 1997

Problem 1 (15 points) 

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
Problem 2 (15 points) 


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;
Problem 3 (15 points) 


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);