Overview

Weight: This assignment will count for 11% of your final grade.
Due Date: Sunday, October 28, 2007, 11:59:59 PM. The second exam is the following week and material from this assignment will be important to know for the exam.

Fun with Lists

This assignment provides experience in ML programming. You have previously written some of these functions in Scheme for Homework 2. Now you get to see how they appear in a statically type-checked language. You can download ML from http://www.dina.dk/~sestoft/mosml.html . Moscow ML can be installed on most operating systems (eg,. Linux, Unix, Windows). The Windows installation package is 6MB. The software is also installed on the Windows machines in the Sloan 353 labs.

Other Standard ML implementations that you can use are PolyML and Standard ML of New Jersey.

If you scroll down Moscow ML page linked above you will find "Other on-line Standard ML resources" with a links to introductory material on ML programming. Any of these may be helpful. When you turn in your project include a list of the references you used as a comment at the head of the file. Tell me how/if each was helpful.

Turning in your work

All code should be developed in the file called assign3.sml. The problem solution will consist of a sequence of function definitions in one file. When you are done and certain that everything is working correctly, turn in the file using the turn-in page. Upload a file named assign3.sml. You may turn in your assignment as many times as you like. Everything you turn in is saved, but I will look at only the last turn-in before the deadline. Code you write to test your functions should be placed in a separate file. When you turn in assign3.sml it should contain only the required function definitions and needed auxilliary functions and type declarations.

Grading

The assignment will be marked for good programming style (indentation and appropriate comments), as well as clean compilation and correct execution.

General rules

Unless directed otherwise, you must implement your functions using recursive definitions built up from the basic built-in functions (i.e., when I ask you to implement filter you may not use the built-in filter function, nor can you use the built-in sort functions for the sorting assignment, etc. .). You must program "functionally" without using ref cells.

When auxiliary functions are needed, make them local functions and take advantage of static scoping to avoid unneeded arguments -- ones that don't change from one recursive call to the next.

in_list - 5%

This function should return true if the first argument is a member of the second argument.

- in_list (1,[]);
false
- in_list (1,[1,2,3]);
true
- in_list ([1],[[1]]); 
true
- in_list ([1],[[3],[5]]); 
false 
- in_list ("c",["b","c","z"]);
true

intersection - 10%

This function should return the intersection of two lists. Maybe you can make use of in_list?

- intersection ([1],[1]); 
[1] 
- intersection ([1,2,3],[1,2]); 
[1,2]
- intersection ([[2,3],[1,2],[2,3]], [[1],[2,3]]); 
[2,3]

Each value should appear in the output list only once.

filter - 10%

This function takes as its first argument a one-argument function, called a predicate, which returns true or false, and as its second argument a list. It returns a list of all elements in the second argument that satisfy that predicate. The elements must appear in the result in the same order that they appear in the original list.

- filter (fn (x) => (x = 1)) [1,2,3];
[1] 
- filter (fn (x) => (x <= 3))[1,2,3,4]; 
[1,2,3]

For this problem (only) your implementation is required to be tail recursive, so you will need to define an auxiliary function that takes a parameter in which the result is accumulated. The function filter will simply call the auxiliary function with [] as the initial result. It is the auxiliary function that will be tail recursive. You may use the built-in rev function (reverses a list) in implementing filter.

We have discussed tail recursion, auxiliary functions, and accumulating parameters in class.

quicksort - 20%

This function takes as its first argument a two-argument function called a comparator and as its second argument a list. For any pair the comparator returns true or false. The function quicksort returns a list consisting of the members of its second argument, ordered so that the comparator returns true on adjacent members.

- quicksort (fn (x,y) => (x <= y)) [1];
[1] 
- quicksort (fn (x,y) => (x <= y)) [3,2,1,2]; 
[1,2,2,3] 
- quicksort (fn (x,y) => (x >= y)) [3,2,1,2]; 
[3,2,2,1]

Recall the quicksort algorithm: partition the input into 2 pieces by picking a value and comparing all the remaining elements of the input to that value; put the elements for which the comparator returns true in one partition, those where it returns false in the other. Recursively quicksort the two partitions obtaining two sorted lists. Append the two lists with the initial element between them to get the final answer. Do not use any of the built-in sort functions. You will need to define an auxiliary partition function.

Practice with datatypes - 20%

Define an ML datatype datatype either = STRING of string | INT of int.
Define an ML datatype named eitherTree for binary trees containing values of type either where the data is only at the leaves of the tree.
Define an ML function eitherSearch having type eitherTree -> int -> bool that returns true if the int is in the tree and false otherwise. Define an ML function of no arguments, eitherTest that:

• constructs an eitherTree with at least 5 int-containing leaves, at least 5 string-containing leaves, and at least 4 levels;
• searches the tree using your eitherSearch function for a value that is present in the tree;
• and, searches the tree using your eitherSearch function for a value that is notpresent in the tree.

treeToString - 20%

A polymorphic tree type in SML might be represented using

   datatype 'a Tree = LEAF of 'a | LIST of ('a Tree) list

Write a function treeToString: ('a -> string) -> 'a Tree -> string that produces a parenthesized string representing an arbitrary Tree. treeToString is invoked as treeToString f t where f is a function that converts data of type 'a to a string and t is an 'a Tree. The parenthesization rules are as follows:

• For a LEAF node, the output is just f the-data-in-the-leaf.
• For a LIST node, concat the strings produced by treeToString on the elements of the list and surround the resulting string with parentheses.

For this function, you may use built-in functions map and String.concat in addition to the generally allowable functions listed above.

I suggest that you start by solving a simpler non-polymorphic problem using

   datatype Tree = LEAF of string | NODE of Tree list

Since the leaves in this simpler problem are already strings you don't need the function argument but you can see the overall structure of the solution. Then make the datatype polymorphic and add the function parameter.

Hint: The whole function is neatly expressed as the main function and a recursive auxiliary function in 8 total lines of code.

Here is some test data:

val L1a = LEAF "a"
val L1b = LEAF "b"
val L1c = LEAF "c"
val L2a = NODE [L1a, L1b, L1c]
val L2b = NODE [L1b, L1c, L1a]
val L3 = NODE [L2a, L2b, L1a, L1b]
val L4 = NODE [L1c, L1b, L3]
val L5 = NODE [L4]
val iL1a = LEAF 1
val iL1b = LEAF 2
val iL1c = LEAF 3
val iL2a = NODE [iL1a, iL1b, iL1c]
val iL2b = NODE [iL1b, iL1c, iL1a]
val iL3 = NODE [iL2a, iL2b, iL1a, iL1b]
val iL4 = NODE [iL1c, iL1b, iL3]
val iL5 = NODE [iL4]

treeToString String.toString L5 should produce "((cb((abc)(bca)ab)))" and treeToString Int.toString iL5 should produce "((32((123)(231)12)))".

Note that interactive SML systems typically do not print all of the contents of deeply nested data structures. So after evaluating the declaration for il5 the response may be something like

val iL5 = NODE [NODE [LEAF #,LEAF #,NODE #]] : int Tree

depending on what SML system you are using (in this case SMLofNJ).

Perms - 15%

Function perms is given a list, l, and returns a list of lists, each of the sublists being one of the length(l)! permutations of l.

Hints on working with Moscow ML

The following are a few tips to help you get started on working with Moscow ML on the Windows machines in the Sloan 353 lab.

• Finding Moscow ML in Windows

• Invoking ML on a file

• How to quit the ML environment