Computer Science 510 Programming Languages Problem Set 1

Fall 2002 Due Sept 23

Rules for collaboration: You may discuss the problem sets with other students to increase your understanding of the material. However, what you write down and turn in should be your own work.

All problem sets are due at 11:00 a.m. in class on the due date.

1. Datatypes
   Write ML datatypes for digits, numbers, and expressions, as defined below.  Do not use integers or strings in your definition.  Use datatypes exclusively.

   • zero is a digit, one is a digit,..., nine is a digit
   • if d is a digit then d is a number
   • if n is a number and d is a digit then (n d) is a number
   • if n is a number then n is an expression
   • if e1 and e2 are expressions then e1 + e2 is an expression
   • if e1 and e2 are expressions then e1 * e2 is an expression
   Implement ML functions 

   • eval_dig : digit -> int 
   • eval_num : number -> int 
   • eval_exp  : exp -> int 

    These functions take a digit, number or expression and return the corresponding integer.  For example, the number ((3 4) 5) should evaluate to the integer three hundred and forty-five.  "+" and "*" should be interpreted as ordinary integer addition and multiplication.
   Prove by induction that for any number n, eval_num(n) is nonnegative.  Your proof should use the following induction principals:  

   For any property P, if P(zero) and P(one) and ... and P(nine) then for all digits d, P(d).

   For any property P, if P(d) and (for all n,d, P(n) and P(d) implies P(n d)) then for all numbers n, P(n).
   Change the fourth rule listed above so that instead of

   if n is a number and d is a digit then (n d) is a number, you have

   if n is a number and d is a digit then (d n) is a number and then write new versions of eval_num and eval_exp so that the expression (3 (4 5)) evaluates to three hundred and forty-five. Hint: the type returned by eval_num will have to change.

    

2. Implement quicksort in ML. That is, write the following functions

   get_pivot: int list -> int * int list
   partition: int * int list -> int list * int list
   sort: int list -> int list
   

   such that
   • if (i,L')=get_pivot(L) then i is some element of the list L and L' is a list of all the other elements of L;
   • if (L1,L2)=partition(i,L) then L1 @ L2 is a permutation of the list L, and all the elements of L1 are less than or equal to i, and all the elements of L2 are greater than i;
   • and if L' = sort(L) then L' is a permutation of L and the elements of L' are in nondecreasing order.
   Experiment with at least two implementations of get_pivot: for example, get the first element of the list, or get the middle element. Have your partition function print a "." whenever it does a comparison. How is the efficiency of the quicksort algorithm on an already-sorted input differ with your different get_pivot functions?
3. Modify your sort function (and the other two as necessary) so that the comparison function can be passed as an argument:

   sort: ('a * 'a -> bool) -> 'a list -> 'a list
   

   Demonstrate the polymorphism by sorting a list of strings into reverse alphabetical order; and by sorting a list of integers so that all the odd numbers come before all the even numbers (with the order otherwise arbitrary).

   As part of your demonstration, show the ML declarations that execute sort on these two lists, and the transcript of your ML session.

   (If you were not able to get your quicksort working, you may implement any polymorphic sorting algorithm (insertion sort, bubble sort, etc.) that takes a sort function as an argument.)

    

4. Consider the following datatype declaration for an integer-storing red-black tree:

datatype color = R | B

datatype tree = Empty | T of color * tree * int * tree

Red-black trees also maintain the following 3 invariants

• In any node T (c,t1,x,t2), x is greater than any element in t1 and any element in t2 is greater than x.
• No red node has a red parent.
• Every path from the route to an empty node contains the same number of black nodes.

Implement the following operations on red-black trees, making sure to maintain the three invariants above:

empty : tree                    (* an empty tree *)

member : int -> tree -> bool    (* member x t is true if x is in t *)

insert : int -> tree -> tree    (* insert x t returns a new tree

                                     containing the elements of t union {x} *)

You may use any algorithms textbook you choose to help you implement these functions (or you can try to figure it out yourself).  Hint:  the key to insertion is in the definition of an auxiliary function that rebalances trees.  There is a solution in which the core of the balance function can be written in five lines of code.  This question will be graded both on correctness and on elegance of the final solution.  (Of course, both correctness and elegance are important in all of the answers that you give in this course.)