CS 217: Programming Languages

Programming Assignment 2: SML

Assigned on Wednesday, 1/21.
Due by 4:45 PM on Friday, 2/6.

Use hsp to turn in an entire directory called sml that contains the files problem1.sml, problem2.sml, and problem3.sml. If you need to resubmit your homework, resubmit the entire directory with a version number. For example, if I need to resubmit my sml directory, I would name it sml2 (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.

For all parts of this assignment, you may not use side-effects (e.g. !, ref, etc.).

You should use recursion, and not iteration, on each of these problems.

Note that these problems vary significantly in amount of difficulty. You should start early and look at each problem.

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 non­decreasing (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(m &minus 3) + f(m &minus 2) + f(m &minus 1) 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? (If these are really quick on your computer, keep going up until you find a value that causes f to run over 1 minute long.)

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

(b) In a functional language without side-effects or assignments, the value of a function always depends solely on its arguments. This allows us to use an optimization known as memoizing. You can pass a list of previous answers (a "memo") as a parameter that the function can use to speed its work. Write an SML function fastF(m) that is a solution to part (a) using memoizing. How long does it take now to compute your answer?

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 | entry 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 an entry 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 '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 entry in this lazyList should indicate the current value, as usual. The second value should be a function that calls sieve again appropriately.)

Many thanks to Prof. Charles Fischer at University of Wisconsin-Madison.