Problem Set 1: An introduction to SML

Due Thursday, February 2, 11:59:59 pm.

The goal of this problem set is to expose you to as much of the SML language, and functional style programming, as possible. This means that, if you are not familiar with SML, there will be a lot of new material in this problem set. It would be prudent to begin working on it early.

Instructions: This problem set has three parts; you will write each in a separate file. Label the files part1.sml, part2.sml, and part3.sml. Each file should have your name, netID, and what section you're in in a comment at the top. (Comments are written (*like this*) in SML.) 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. Also, 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.

An important note about grading

We will not be providing files with function stubs for you to work from. However, 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. Crucial. Names and argument order. According to instructions. Crucial. Do not break this rule. You will be penalized.

There are three files that you will write in this assignment. The files will be named part1.sml, part2.sml, and part3.sml. Each will include several functions. Please make sure to include your functions in the correct files; it would be tragic for you to not receive credit for a function properly written simply because our grading script couldn't find it.

Do NOT compress the files into a zip file. You must submit each file individually using CMS. Make sure that you download all the stub files from this page, and place all your code inside the structure, as shown in the stub files -- this is very important.

Part 1

Donwload stub file
A complex number is one of the form a+bi, where i is the square root of -1. Complex numbers can be added, subtracted, multiplied, and even divided (read how here). You should write methods to perform all of these tasks. Each method should have type ((real*real)*(real*real))->(real*real). 
    add((1.2,1.1),(1.0,~1.0)) = (2.2,0.1)

    subtract((1.2,1.1),(1.0,~1.0)) = (0.2,2.1)

    multiply((1.2,1.1),(1.0,~1.0)) = (2.3,~0.1)

    divide((1.2,1.1),(1.0,~1.0)) = (0.05,1.15)

Part 2

Donwload stub file
Write a function reverse:string->string that takes a string and reverses it. You will probably want to look up some functions from the basis library. 
reverse("abc") = "cba"

reverse(" a  b c") = "c b  a "

Part 3

Donwload stub file
The function below is supposed to work as described in the comment. It should take two positive integers, and return an integer x as described. However, the given code isn't quite correct or complete. First off, the pow method is not provided, so you will have to implement that (without using any library functions). Then, try running it on an input where no such value of x exists (like findroot(2,2)). You should modify the code so that it returns ~1 in cases like this where no such x exists. However, you do not need to worry about the cases where either or both of the inputs are non-positive. Finally, you should clean up the code to make it more readable (just don't change the name of the function -- findroot) and more efficient. It is ok if your code overflows when using larger inputs -- this is an inherent problem with the algorithm being used. You may want to refer to the ML Style Guide for some ideas. 

(* This function should find the nth root of an integer
 * if that root is also a positive integer.  More specifically, it 
 * should return x, such that xtheroottofind = thenumber.  It 
 * does this through binary search.  The function f uses binary 
 * search to try to find x in the range [a,b].
 *)

fun findroot(thenumber:int, theroottofind:int):int =
    let fun f(a, b) = 
                    if(pow((a+b) div 2,theroottofind) > thenumber) 
                        then
                        f(a,((a+b) div 2) -1)
                    else 
                        if(pow((a+b) div 2,theroottofind) < thenumber) 
                        then
                        f(((a+b) div 2)+1,b)
                    else 
                        ((a+b) div 2)
    in
        f(1,thenumber)
    end