CS 217: Programming Languages

Programming Assignment 2: SML

Assigned on Wednesday, April 17.
Due at 5 PM on Friday, May 3.

Use hsp to turn in each part of this assignment separately, using filenames sml1a.sml, sml1b.sml, sml2a.sml, etc. You may define any helper functions that you wish. If you need to resubmit your homework, add an additional underscore with a version number. For example, if I need to resubmit my sml1a.sml file, I would name it sml1a_2.sml (for version 2).

Problem 1

(a) Assume we have a list L of integers. Define a function listify(L) that divides L into one or more sublists so that each sublist contains integers in nondecreasing (sorted) order. That is, if v1 and v2 are adjacent in L and v1 <= v2 then v1 and v2 are adjacent in the same sublist. However if v1 > v2 then v2 ends one sublist and v2 begins the next sublist. For example,

listify([3,5,1,8,9,2,1,0]) returns [[3,5],[1,8,9],[2],[1],[0]]
listify([1,2,3,4,5,6]) returns [[1,2,3,4,5,6]]
listify([5,4,3,2,1]) returns [[5],[4],[3],[2],[1]]

(b) If the output of listify contains a single sublist, then we know the input list L was in sorted order. Otherwise, we can implement a sorting algorithm (a merge sort) as follows. Take the first two sublists produced by listify and merge them into a single sorted list. Take the next two sublists and merge them. Repeat until all sublists are considered. (The last sublist is copied unchanged if it has no partner to merge with). If only one sublist remains, we are done. Otherwise, repeat the process, merging sublists pairwise. At each stage, the number of sublists is cut in half. For example,

[[3,5],[1,8,9],[2],[1],[0]] is reduced to [[1,3,5,8,9],[1,2],[0]]
and then to [[1,1,2,3,5,8,9],[0]] and finally to [[0,1,1,2,3,5,8,9]].

Implement a function mergesort(L) using listify as a subroutine.

Problem 2

(a) Write an SML function that computes the following recursive function:

f(0) = 1
f(-1) = 0
f(-2) = 0
f(m) = f(m3) + f(m2) + f(m1) for m >= 1

(Be sure to remember that in SML ~ is unary minus and is binary minus.)

What are the values of f(28), f(29), and f(30)? How long does it take to compute each of these values?

To start a ``CPU timer'' in SML use

val t = Timer.startCPUTimer();

To determine how much CPU time (in seconds) has elapsed since timer t was created use

Time.toReal(#usr(Timer.checkCPUTimer(t)));

Estimate how long f(33) will take to compute (using your timings for f(28), f(29), and f(30)).

(b) In a functional language like SML without side-effects or assignments, the value of a function always depends solely on its arguments. This allows us to use the memoizing optimization. When a function is called, its arguments and result value can be recorded. If the function is called again with the same arguments, the stored result can be returned immediately. Write an SML function fastF(m) that is a solution to part (a) using memoizing. What is the value of fastF(34)? How long does it take to compute?

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.)

I am indebted to Charles Fischer at University of Wisconsin-Madison for writing these wonderful problems.