Problem Set 2: Folding, Datatypes, and Stacking

Due Feb. 18, 2010

Important notes about grading:

1. Compile errors: All programs that you submit must compile. Programs that do not compile will probably receive an automatic zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile and hand in a file that compiles, rather than handing in a more complete file that does not compile.
2. Missing functions: We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set instructions, and that you place the functions in the correct files. Otherwise you may not receive credit for a function properly written.
3. Code style: Finally, please pay attention to style. Refer to the CS 3110 style guide and lecture notes. Ugly code that is functionally correct may still lose points. Take the extra time to think out the problems and find the most elegant solutions before coding them up. Even though only the second part of the assignment explicitly addresses the style issue, good programming style is also required for the other parts of this assignment, and for all the subsequent assignments in the rest of the semester.
4. Late assignments: Please carefully review the course website's policy on late assignments, as all assignments handed in past the deadline will be considered late. Verify on CMS that you have submitted the correct version, before the deadline. Submitting the incorrect version before the deadline and realizing after the deadline still constitutes a late assignment.

Part 1: List Folding (20 pts)

Folding is one of the most useful tools in functional programming and you will certainly use it many times over the course of the semester. The following exercises are designed to get you comfortable with folding to do useful computations on lists. Note: This exercise is to get you used to folding, so every function must include either List.fold_left or List.fold_right. For full credit, do not use the rec keyword.

1. (4 points) Using folding, write a function mean : int list -> float that calculates the mean score of all students in the class.
2. (4 points) Using folding, write a function min2 : int list -> int that returns the second-smallest value in the list. Do not sort the list. Fail with an appropriate exception if the list is too short.
3. (6 points) Using folding, write a function filter : ('a -> bool) -> 'a list ->'a list * 'a list that takes in a function and list, and returns two lists, where the first list contains every element in the input that causes the given function to evaluate to true, and the second list the elements where the function evaluates to false. The original order of the list is maintained in the returned lists.
   For example, filter (fun x -> x > 0) [1;2;-3;4;-5;-6;7;0] = ([1;2;4;7],[-3;-5;-6;0]).
4. (6 points) Using folding, write a function allPrefixes: 'a list -> 'a list list that returns a list of all non-empty prefixes of the given list, ordered from shortest prefix to longest prefix.
   For example, allPrefixes [1;2;3;4] = [[1]; [1;2]; [1;2;3]; [1;2;3;4]].

Part 2: Dictionaries, Lists, and Polymorphic Types (16 pts)

We often need a data structure to group related pairs of values. Such a data structure is called a dictionary. Operations on a dictionary include inserting a key/value pair and looking up the value that corresponds to a given key. We can implement dictionaries in OCaml by using a list of pairs, i.e. an associative list. For the moment, assume that the keys and values are both strings. Note: For this part, you are not permitted to use any of the OCaml library functions (particularly the List functions).

1. (4 points) To insert into an associative list, we can simply add a key/value pair to the head of the list. By appending to the head and by searching the list from the head toward its tail, we have an easy way to "overwrite" old entries with new ones.
   Write function insert with type string -> string -> (string * string) list -> (string * string) list that implements the insertion method described above.
2. (4 points) Write function lookup with type string -> (string * string) list -> string. Given a key and an associative list, this function returns the value corresponding to that key.
   For example, given a phonebook, we can retrieve Alice's phone number with expression lookup "Alice" phonebook. If the key is not present in the list, your code should failwith some reasonable exception. (Yes, our phone numbers can contain dashes and special characters like * and #, so they can't be simple integers.)
3. (4 points) Why restrict ourselves to strings? We can think of other kinds of key/value pairs. For example, we may want a data structure that maps Cornell ids to student names. Instead of rewriting the lookup function for each possible type of key/value pair, we will create its polymorphic version, polymorphicLookup, whose type will be ('a * 'a -> bool) -> 'a -> ('a * 'b) list -> 'b. Here the function of type 'a * 'a -> bool is a comparison function that returns true if and only if both arguments are equal.
4. (4 points) Use your polymorphicLookup to write function lookupCUID : int -> (int*string) list -> string that takes an id number and a list of (int * string) key/value pairs and returns the corresponding string. For full credit, you must make your answer concise and use polymorphicLookup smartly. It can be done with one line, though a few more would still qualify as concise.

Part 3: Recursive Types (28 pts)

Consider the following declaration for nested lists: type 'a llist = LList of 'a llist list | Elem of 'a A nested list thus consists of an element of unspecified type, or of a list of nested lists. Consider some examples:

- LList([]);
- Elem(3);
- LList([Elem(1); LList([Elem(2); LList([]); Elem(3)]); Elem(4)]);

1. (7 points) Write function flatten that takes a nested list as its unique argument and returns a "flat" list of all elements in the nested list.
   For example: flatten(LList([Elem(1); LList([Elem(2); LList([]); Elem(3)]); Elem(4)])) returns [1; 2; 3; 4]. Note that the elements in the resulting list are in the same order as in the nested list. Your solution must have the same property.
2. (7 points) Write function depth that takes a nested list as its unique argument and return the highest level of nesting in the list.
   For example: depth(Elem(5))= 0, depth(LList([])) = 1, depth(LList([Elem(1); LList([Elem(2); LList([]); Elem(3)]); Elem(4)])) = 3.
3. (14 points) Write function cutOff that takes a non-negative integer n, and a nested list, and returns only those parts of the nested list that are at a level equal to or less than n in the original nested list. Thus we must have depth(cutOff(n, lst)) = Int.min(n, depth(lst)). Some examples:

   
   cutOff(0, Elem(3)) = Elem(3)
   cutOff(1, LList([Elem(1); LList([Elem(2)])])) = LList([Elem(1)])
   cutOff(100, LList([Elem(1); LList([Elem(2)])])) = LList([Elem(1); LList([Elem(2)])])
   
   

   Given the above, what should cutOff(0, List([])) return? Well, a nested list of depth 0, i.e. an Elem. But there is no obvious value we could use to build an Elem, and we can't easily pick one (say, 0), as the nested list is a polymorphic type. Rather, this case and all the analogous ones should result in the program failing with a helpful message.

Part 4: Stack Language (36 Points)

In this part you will use higher-order functions to implement a simple stack language that computes on integers. The commands in this language are:

We can implement each of the commands as OCaml functions, in a way that lets us write a series of stack-language commands directly as OCaml expressions. The value of the OCaml expression should be the final stack configuration.
For example, the following series of commands: start (push 2) (push 3) (push 4) mul mul halt evaluates to a stack with one element, 24.

1. (24 points) Your task is to implement the above commands in this language (start and halt are already done for you). Use a list to implement the stack such that the previous example returns the stack [24], and fail with StackException if a command cannot be performed on the current stack, e.g. the command add in the program start add halt
2. (12 points) Why stop here? Using what you did in part 2, create a way to store and load variables by keeping them in a dictionary. Add the commands:

   (store "str")	Stores the value current value on top of the stack with name str. This command is always parenthesized with its argument.
   (load "str")	Loads the value associated with the string str in memory and puts it on top of the stack. This command is always parenthesized with its argument.

   To implement this, you will need to modify your above functions (including the provided stubs), as well as start and halt. For start, assume the memory is empty, and for halt you can throw away anything in memory (still return just the stack). If done correctly, programs without the new commands behave identically, with no additional syntax required.
   If you have trouble with store and load working, but have the first part working correctly, submit the working version for the first part and a commented-out version of what you did for the second part. This way we can test your first part before you modified them for the second part, and then award partial credit for the second part.