CS 217: Programming Languages

Programming Assignment 2: SML

Assigned on Monday, 1/20.
Due at 5 PM on Monday, 2/3.

Use hsp to turn in an entire directory called sml2 (named so for the first SML assignment), that contains the files problem1.sml, problem2.sml, etc. You may define any helper functions that you wish. If you need to resubmit your homework, resubmit the entire directory with an additional underscore and a version number. For example, if I need to resubmit my sml2 directory, I would name it sml2_2 (for version 2).

You should not use any functions from SML's basis or utility libraries, as this might defeat the purpose of some of these exercises.

Problem 1

Your mission is to extend your solution for Problem 2 on Programming Assignment 1 to allow sets to contain other sets.

An added bit of complexity here is that SML, with its strict type checking, does not allow arbitary combinations of lists within lists. For example, the list [1,2,[3,4]] is not valid. To get around this, you should create a polymorphic datatype for nested lists as follows:

datatype 'a nestedList = List of 'a nestedList list | Elem of 'a;

You may assume that the lists input to your functions are both legal nestedLists. Here are some examples of legal inputs and outputs:

setEquals(List [Elem 1,Elem 2,Elem 3],List [Elem 3,Elem 2,Elem 1]) ---> true
setEquals(List [Elem 1,List [Elem 2,Elem 3]],List [List [Elem 3,Elem 2],Elem 1]) ---> true
setEquals(List [Elem 1,Elem 2,Elem 3],List [List [Elem 3,Elem 2],Elem 1]) ---> false
setEquals(List [Elem 1,Elem 2,Elem 3],List [List [Elem 1,Elem 2,Elem 3]]) ---> false
setEquals(List [List [Elem 1,Elem 4], List [Elem 2, Elem 3]], List [List [Elem 3, Elem 2], List [Elem 4, Elem 1]]) ---> true

union(List [List [Elem 1, Elem 2, Elem 3]], List [List [Elem 3, Elem 4, Elem 5]])
   ---> List [List [Elem 1,Elem 2,Elem 3],List [Elem 3,Elem 4,Elem 5]]
union(List [List[Elem 1,Elem 2,Elem 3]], List[List[Elem 3,Elem 2,Elem 1]])
   ---> List [List [Elem 1,Elem 2,Elem 3]]

intersect(List [List [Elem 1,Elem 2,Elem 3]],List [List [Elem 3,Elem 2,Elem 1]])
   ---> List [List [Elem 1,Elem 2,Elem 3]]
intersect(List [List [Elem 1,Elem 2,Elem 3]],List [List [Elem 4,Elem 5,Elem 6]])
   ---> List []
intersect(List [List [Elem 1],List [Elem 2],List [Elem 3]],List [List [Elem 2],List [Elem 3],List [Elem 4]])
   ---> List [List [Elem 2], List [Elem 3]]

Problem 2

(a) Define a curried function

map_first_two: ('a * 'a -> 'b) -> 'a list -> 'b list

that works like SML's built-in map function except that the function argument is always a function of two arguments (like the operator +). Use the first and second elements of the list argument as the first pair of arguments to the function argument, then the second and third elements, then the third and the fourth, and so on. If there are fewer than two elements in the list, the empty list should be returned. Here is an example:

map_first_two (op +) [2,3,4,5,7] ---> [5,7,9,12]

(b) Define a function curry3: ('a * 'b * 'c -> 'd) -> 'a -> 'b -> 'c -> 'd that takes a three-argument function and returns a curried version of that function. Thus ((curry3 f) x y z) returns the result of f(x,y,z).

Problem 3

(a) Recall that a lazy list is a useful structure for representing a long or even infinite list. In SML a lazy list can be defined as

datatype 'a lazyList =

    nullList | cons of 'a * (unit -> 'a lazyList)

This definition says that lazy lists are polymorphic, having a type of 'a. A value of a lazy list is either nullList or a cons value consisting of the head of the list and a function of zero arguments that, when called, will return a lazy list representing the rest of the list. Write the following SML functions that create and manipulate lazy lists:

seq(first,last)
This function takes two integers and returns an integer lazy list containing the sequence of values first, first+1, ... , last
infSeq(first)
This function takes an integer and returns an integer lazy list containing the infinite sequence of values first,first+1, ....
firstN(lazyListVal,n)
This function takes a lazyList and an integer and returns an ordinary SML list containing the first n values in the lazyList. If the lazyList contains fewer than n values, then all the values in the lazyList are returned.
Nth(lazyListVal,n)
This function takes a lazyList and an integer and returns an option representing the n-th value in the lazyList (counting from 1). If the lazyList contains fewer than n values, then none is returned. (Recall that we defined 'a option = some of 'a | none).
filterMultiples(lazyListVal,n)
This function returns a new lazy list that has n and all integer multiples of n removed from a lazyList. For example, a non-lazy list version of filterMultiples would behave as follows:
filterMultiples([2,3,4,5,6],2) = [3,5] filterMultiples([3,4,5,6,7,8],3) = [4,5,7,8]

(b) A wide variety of techniques have been devised to compute prime numbers (numbers evenly divisible only by themselves and one). One of the oldest techniques is the "Sieve of Eratosthenes.'' This technique is remarkably simple.

You start with the infinite list L = 2, 3, 4, 5, .... The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7, 9, .... The head of this list (3) is a prime. Moreover, if you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, .... Repeating the process, you repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples of the head value.

You are to write an SML function primes() that computes a lazyList containing all prime numbers, starting at 2, using the ``Sieve of Eratosthenes.'' To test your function, evaluate firstN(primes(),10). You should get [2,3,5,7,11,13,17,19,23,29]. Try Nth(primes(),20). You should get some 71. (This computation may take a few seconds, and do several garbage collections, as there is a lot of recursion going on.)

(Hint: Create a recursive function sieve(lazyListVal) that returns a new lazyList. The first element of the cons in this lazyList should indicate the current value, as usual. The second value should be a function that calls sieve again appropriately.)

Problem 4 (d)

Do Problem 4, part (d), from SML Programming Assignment 1.

I am indebted to Prof. Gary T. Leavens at Iowa State University for problem 2, and Prof. Charles Fischer at University of Wisconsin-Madison for problems 1 and 3, and 4.