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.
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.
1. The following three functions execute properly, but are written improperly. As masters of the style guide and programming efficiency, you, the students, are given the task of cleaning up the code into functions that are elegant, well-designed, stylistic, and efficient. Change indentation and naming of values; if you see fit, factor expressions using let-in-end and even change implementation to create the cleanest, best SML code that you can, without degrading the functionality of any of the functions.
fun evrynth(x,y) = let fun inner (x,y,z1,z2) = if z1 > String.size(x) then z2 else if(z1 mod y = 0) then inner(x,y,z1+1,z2 ^ String.str(String.sub(x,z1-1))) else inner(x,y,z1+1,z2) in inner(x,y,1,"") end fun SQROOT(squarerootnumber:int) = let fun SQROOT_TWO(sqrootnumber2, guess) = if (guess * guess > sqrootnumber2) then ~1 else if (guess * guess = sqrootnumber2) then guess else if(guess * guess < sqrootnumber2) then SQROOT_TWO(sqrootnumber2, guess+1) else ~1 in if (SQROOT_TWO(squarerootnumber,1) = ~1) then ~1 else SQROOT_TWO(squarerootnumber,1) end fun fibonacci(x:int):int = if x = 1 orelse x <= 0 then 1 else fibonacci(x-1) + fibonacci(x-2)
2. The following expression was written by a deranged ML
programmer.
-Is it a legal expression?
-If so, what does it
compute?
-Rewrite the expression so that there is only
one binding for each name used in the expression. COMMENT OUT the
rewritten expression in your .sml file.
let
val n = 5
val m = let
val n = n*n
in let
val n = n*n
in n
end
end
in let
val n = n*n
in let
val n = n*n
in n
end
end
end
1. Write a function division:(int*int)->(int*int) that takes in two positive integers, m and n, and returns a tuple (d,r) where d is the quotient (m div n) and r is the remainder (m mod n). You may not use any integer operations other than addition, subtraction, and comparison. For example:
division(43,12)=(3,7)
division(19,27)=(0,19)
2. Write a function extract:real->(int*real) that takes in a real and returns a tuple (i,r) where i is the integer truncation of the real and the r is the fractional part of the real. For example:
extract(4.5)=(4,0.5)
extract(~8.74)=(~8,~0.74)
1. Write a function isPalindrome:string->bool that takes in a string and returns true iff that string is a palindrome. Your function should disregard case and spaces. It should be implemented recursively. For example:
isPalindrome("racecar") = true
isPalindrome("A man a plan a canal PANAMA") = true
isPalindrome("I pity the fool") = false
2. Write a function bearish:string->bool that returns true iff its argument contains the letters "b", "e", "a", and "r" in any order. Remember that the way to write the character "b" in SML is #"b". For example:
bearish("Sgt. Bad Attitude Barrackus") = true
bearish("barb") = false
bearish("baer") = true
HINT: One particularly elegant (but unnecessary; you won't be docked for ignoring this hint) way to code this function involves lists. Look at the function "explode" in the STRING structure in the Basis Library. You can call it with the syntax String.explode(args). You might want to use it in conjunction with a function from the LIST structure to make your life easier.
3. This previous functionality is rather narrow; we'd like something more general. Write a function fooish:(string*string)->bool. fooish returns true iff, for every character c in its first input, its second input contains at least as many occurrences of c as its first input does. In the interest of keeping things simple, the first input will contain only alphabetic characters. For example:
fooish("horse","shortie")=true
fooish("array","i love our superb TAs")=false
fooish("extra","exxtra")=true
HINT: If you've gone the list route, look at List.partition in the Basis Library. If you choose to use List.partition, note that it is a curried function; that is, its two arguments should NOT be passed in a tuple. The proper syntax is "List.partition arg1 arg2".