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.
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]]
(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:
(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.)
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.