CSE 341 -- Assignment 3

February 1, 2002
Due in class February 8, 2002

Purpose: To become familiar with the ML programming environment; to experiment with elementary ML data types and operations; to practice writing your own ML functions (including recursive functions).

1. Experiment with the ML system. As usual, you don't have to hand in anything for this question.

2. Draw trees showing how the following pairs of patterns match (or don't match).

     1.  (a::b::c, (q, p))      and ([1,2], ("hello", "there"))
   
     2.  (a,b)::x::y            and [(1,2), (3,4), (5,6)]
   
     3.  ([3,4,z], x::nil)      and ([1,2,3], ["a", "b", "c"])
   

   For each variable or constant in the pattern, show what it matches against. If the patterns don't match, show where the mismatch is.

3. Write a function called sum, which sums the elements of an integer list. Write this function recursively and use pattern matching to handle the various cases.

4. Write a function called int2string, which takes an integer and returns a string representing that integer.

5. Write powerset, as described in exercise 3.3.13. We won't grade this one (because answers to *'ed questions are online), but it is a real challenge to see if you can come up with the answer yourself.

6. The standard recursive definition for x^n is:

     expt(x, n) = if (n=0) then 1 else x * expt(x, n-1);
   

   Implemented in this manner, it requires O(n) multiplies (and O(n) space for the stack). However, the following definition hints at a more efficient implementation of expt:

     expt(x, n) = 1                               if n=0
                  expt(x, n/2) * expt(x, n/2)     if even(n)
                  x * expt(x, n-1)                otherwise
   

   Using LET, implement a more efficient version of expt. What is the running time of your function?

7. For the next two questions, we give you the following three functions:

   fun map (f, nil)   = nil
     | map (f, x::xs) = f(x) :: map(f, xs);
   
   fun reduce (f, base, nil)   = base
     | reduce (f, base, x::xs) = f(x, reduce(f, base, xs));
   
   fun filter (pred, nil) = nil
     | filter (pred, x::xs) = if pred(x) then
   			       filter(pred, xs)
   			   else
   			       x::filter(pred, xs);
   

8. Write the function sum2, which sums the elements of an integer list. This time use the higher-order functions reduce.

9. Write the function max, using the higher-order function reduce. max should return the largest element in a list of integers. It doesn't have to behave nicely for the empty list.

10. Write the QuickSort function. For full credit, you should not implement helper functions such as biggers and smallers. By using patterns, a let expression, filter (as defined above), and anonymous functions, you ought to be able to express the algorithm in one concise function.
11. Write two short questions you have about ML. We ask this to (1) get you to think a little deeply about the language and (2) help us learn what we're not getting across in lecture and section.

Deliverables:

Please turn in the following (hard copy only): your documented source code, your answers to the written questions, your two questions about the course, and a transcript of the following (just file in your source code, and then file (or cut and paste) in the following statements): (If you named your functions as we did in the handout, this should be straightforward.)

val list1 = [435,5,~452,52,52,32452,1,44,~341,~52,41,524];
val list2 = [435,5,452,52,~53,41,41,~524,513];
val list3 = [1];
val list4 = [1,2,3,4,5,6,7,8,9,10];
val list5 = [~10, ~9, ~8, ~7, ~6, ~5, ~4, ~3, ~2, ~1, 0];
val list6 = nil;

sum(list1);
sum(list2);
sum(list3);
sum(list4);
sum(list5);
sum(list6);

int2String(324);
int2String(0);
int2String(1000);
int2String(~42);
int2String(~4352);

max(list1);
max(list2);
max(list3);
max(list4);
max(list5);

QuickSort(list1);
QuickSort(list2);
QuickSort(list3);
QuickSort(list4);
QuickSort(list5);
QuickSort(list6);