Problem Set 1: An introduction to SML

Due Wednesday, September 6, 2006, 11:00 pm.

The goal of this problem set is to expose you to the basics of the SML language while learning a bit about functional style programming. If you are not already familiar with SML, it may be a fair amount of new material, so please begin this problem set early.

Instructions

This problem set has three parts. You will write your solution to each part in a separate file: part1.sml, part2.sml, part3.sml. To get you started, we have provided a stub file for each part. You can download and edit these files. Please write your name and NetID as a comment at the top of each file. In SML, comments are written (*like this*). Once you have finished, submit your solution using CMS.

Three important notes about grading:

Compile errors: All programs that you submit must compile. Programs that do not compile will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile and hand in a file that compiles, rather than handing in a more complete file that does not compile.
Missing functions: We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set instructions, and that you place the functions in the correct files. Crucial. Names and argument order. According to instructions. Crucial. Do not break this rule. You will be penalized. It would be tragic for you to not receive credit for a function properly written simply because our grading script couldn't find it.
Code style: Finally, please pay attention to style. Refer to the CS 312 style guide and lecture notes. Programs that compile and execute correctly WILL NOT RECEIVE FULL CREDIT if they are poorly written/unstylistic. Take the extra time to think out the problems and find the most elegant solutions before coding them up. Even though only the first part of the assignment explicitly addresses the style issue, good programming style is also required for the other parts of this assignment, and for all the subsequent assignments in the rest of the semester.

Part 1: Code style

[ Download stub file: part1.sml ]
The functions below compile and execute correctly. However, they are poorly written. Your task is to rewrite each of the function in an elegant, stylistic, and efficient manner, without changing their functionality. Take the time to carefully read the SML style guide before you write your solution.

fun solve(a:real, b:real, c:real) : real*real =
	if b * b - 4.0 * a * c >= 0.0 andalso a > 0.0 then
	((~b + Math.sqrt(b*b-4.0*a*c))/(2.0*a), (~b - Math.sqrt(b*b-4.0*a*c))/(2.0*a))

	else (0.0,0.0)

fun multiply(l:int list) : int =
	if (null(l)) then 1 else ((hd(l)) * (multiply(tl(l))))

fun add(n:int*int, m:int*int) : int*int =
	((#1 n * #2 m) + (#2 n * #1 m), #2 n * # 2 m)

Part 2: Writing Basic Functions

[ Download stub file: part2.sml ]

Write a function binary : int -> bool * string that takes an integer and returns a pair of: a boolean that indicates the sign; and a string showing the binary representation of its absolute value. The result must not have leading zeroes, except for number 0.
```
binary 0 = (true, "0")
binary 6 = (true, "110")
binary ~6 = (false, "110")
binary 312 = (true, "100111000")
```
Write a function swap : int list -> int list that takes a list of integers and swaps each pair of consecutive numbers (i.e., it swaps the numbers at positions 2i and 2i+1). If the list has an odd number of elements, the last element remains unchanged. For instance:
```
swap [1,2,3,4] = [2,1,4,3]
swap [1,2,3,4,5] = [2,1,4,3,5]
```

Part 3: String Manipulations

[ Download stub file: part3.sml ]
In this part you will write functions that process strings. One particularly elegant way to code string-processing functions involves lists. We suggest that you look at the function explode (and other functions) in the STRING structure in the Basis Library. You can call such functions using the syntax String.explode(args).

Write a function compact : string -> string that replaces each sequence of one or more whitespace characters with a single blank character.
Write a function capitalize: string -> string that capitalizes strings. Given a string, the function rewrites each word in the string such that the first letter is upper-case, and all of the others are lower-case. Words are sequences of alphanumeric characters (digits or letters); all other characters separate distinct words.
```
capitalize "FUNctional programming is FUN" = "Functional Programming Is Fun"
captialize "red-black trees" = "Red-Black Trees"
```