Problem Set 1: An introduction to SML

Due Thursday, January 31, 2008, 11:59 pm.

Change 1/29/08: Part 3 clarified to say that multiple leading zeros are not permitted.

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 should 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, linked from the course website.

Three important notes about grading:

  1. Compile errors: All programs that you submit must compile. Programs that do not compile will probably 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.
  2. 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. Otherwise you may not receive credit for a function properly written.
  3. Code style: Finally, please pay attention to style. Refer to the CS 312 style guide and lecture notes. Ugly code that is functionally correct may still lose points. 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: Expression Types

Give the types of each of the following SML expressions:

  1. ([1],#2("a",#"b"))
  2. (fn x => x,if b then (1,"312") else (~1,"213"))
  3. fun g(a, b, c) = case a of
                   []    => (round c) = 1
                 | 1::xs => not (null xs)
                 | _     => b
  4. (fn (x, y) => (y, x))   (tl [3,1,2], "312")
  5. fn (x, y, z) => (x = "hello") andalso (y < 3) orelse z
            
  6. [[]]

Give expressions with the following SML types:

  1. 'a -> ('a -> 'b) -> 'b
  2. ((int -> real) list) * ((int * real) list list)
  3. 'a * 'b -> ('a -> 'b -> 'c) -> 'c
  4. (bool list -> bool) list

Part 2: Code Style

The following SML code is correct but hazardously unreadable and aesthetically blood-curdling. Please rewrite each piece of code so as to maintain correctness, minimize confusion, and maximize readability. Space and time complexity are also concerns.

  1. fun addAList'sContentsQuickly l =
if (null l) = true
then 0
else (hd (List.drop(l,0))) + (addAList'sContentsQuickly(List.drop(l,1)))
  2. fun boolFun (a,b,c) =
if a=true then
(case (b,c) of
(true,true) => true orelse a
| (true,false) => a orelse b
| (false,true) => a orelse not b
| (false,false) => true)
else (case (b,c) of
  (true,true) => a
| (true,false) => b
| (false,true) => not c
| (false,false) => true)

Part 3: SML Functions and Datatypes

Implement an SML function that parses a string as a signed integer. Throw a NumberFormatException if the string does not represent an integer. We allow an optional minus sign followed by one or more digits. The leading digit may be zero only if the string is exactly "0", representing the number zero. 

(* Parses a string as a signed integer *)
(* Raises NumberFormatException if s does not represent a signed integer *)
fun parseInt(s:string):int = ...

Write an SML function that carries out a simple computation on a data structure: the size of a graph. A brief specification is given below and in the stub file. 

(* We represent a graph as a collection of nodes each containing *)
(* a list of children. If a node has no children, the list is empty *)
datatype tree = Node of tree list

(* Traverses the tree counting nodes *)
(* example:                          *)
(* G = o--o--o--o                    *)
(*     |\                            *)
(*     o o--o                        *)
(*     |  \                          *)
(*     o   o--o                      *)
(* treeSize(G) = 10                  *)
fun treeSize(s:tree):int = ...

Implement an SML function that does a simple string manipulation: token reversal. A brief specification is given below and in the stub file. In this problem we will define tokens as alphanumeric strings, that is letters and numbers only. Whitespace will be defined as spaces only. Multiple consecutive spaces should be considered as one single block of whitespace. 

(* Takes a string containing space-separated tokens and returns *)
(* a new string containing the same tokens in reverse order.    *)
(* Example: reverseWords("A MAN A PLAN A CANAL PANAMA") =
 *  "PANAMA CANAL A PLAN A MAN A" *)
fun reverseWords(s:string):string = ...