Change 1/29/08: Part 3 clarified to say that multiple leading zeros are not permitted.
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.
Give the types of each of the following SML expressions:
([1],#2("a",#"b"))
(fn x => x,if b then (1,"312") else (~1,"213"))
fun g(a, b, c) = case a of [] => (round c) = 1 | 1::xs => not (null xs) | _ => b
(fn (x, y) => (y, x)) (tl [3,1,2], "312")
fn (x, y, z) => (x = "hello") andalso (y < 3) orelse z
[[]]
Give expressions with the following SML types:
'a -> ('a -> 'b) -> 'b
((int -> real) list) * ((int * real) list list)
'a * 'b -> ('a -> 'b -> 'c) -> 'c
(bool list -> bool) list
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.
fun addAList'sContentsQuickly l = if (null l) = true then 0 else (hd (List.drop(l,0))) + (addAList'sContentsQuickly(List.drop(l,1)))
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)
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 = ...