Description
1. exists – 10%
a) [8pts] Write a function exists which takes a tuple as input where the first element of the tuple is
a value and the second is a list. If the value is a member of the list, the function should return true.
Otherwise it should return false.
The function should have type ”a * ”a list -> bool.
Examples:
> exists (1,[])
false
> exists (1,[1,2,3])
true
> exists ([1],[[1]])
true
> exists ([1],[[3],[5]])
false
> exists (“c”,[“b”,”c”,”z”])
true
b) [2pts] Explain in a comment why the type is
”a * ”a list -> bool and not
‘a * ‘a list -> bool
2. listUnion – 15%
Write a function listUnion that takes two lists as input and returns the union of those lists. Your
function should have type ”a list -> ”a list -> ”a list.
Each value should appear in the output list only once, but the order does not matter. Please note that
the input lists may have duplicate values or there may be values that appear in both input lists. All such
duplicate values should be removed.
Examples:
> listUnion [1,3,4] [2,3,4,5]
[1,2,3,4,5]
> listUnion [1,1,2,3,3,3] [1,3,4,5]
[2,1,3,4,5]
> listUnion [“a”,”b”,”c”] [“b”,”b”,”d”]
[“c”,”a”,”b”,”d”]
> listUnion [[1,2],[2,3]] [[1],[2,3],[2,3]]
[[1,2],[1],[2,3]]
3. replace – 15%
Write a function replace that takes an index n, a value v, and a list L and returns a (new) list which is
the same as L, except that its nth element is v. Assume 0-based indexing for n and n≥0. (Note that n
can be greater than the length of the list L. )
The type of replace should be:
int -> ‘a -> ‘a list -> ‘a list.
Examples:
> replace 3 40 [1, 2, 3, 4, 5, 6]
[1,2,3,40,5,6]
> replace 0 “X” [“a”, “b”, “c”, “d”]
[“X”,”b”,”c”,”d”]
> replace 4 false [true, false, true, true, true]
[true,false,true,true,false]
> replace 5 6 [1,2,3,4,5]
[1,2,3,4,5]
> replace 6 7 [1,2,3,4,5]
[1,2,3,4,5]
4. prereqFor – 20%
Assume that we store the list of CptS courses and their prerequisites as a list of tuples. The first element
of each tuple is the course name and the second element is the list of the prerequisites for that course.
See below for an example. Please note that a course may have an arbitrary number of prerequisites.
val prereqsList = [
(“Cpts122” , [“CptS121”]),
(“CptS132” , [“CptS131”]),
(“CptS223” , [“CptS122”, “MATH216”]),
(“CptS233” , [“CptS132”, “MATH216”]),
(“CptS260” , [“CptS223”, “CptS233”]),
(“CptS315” , [“CptS223”, “CptS233”]),
(“CptS317” , [“CptS122”, “CptS132”, “MATH216”]),
(“CptS321” , [“CptS223”, “CptS233”]),
(“CptS322” , [“CptS223″,”CptS233”]),
(“CptS350” , [“CptS223″,”CptS233”, “CptS317”]),
(“CptS355” , [“CptS223”]),
(“CptS360” , [“CptS223″,”CptS260”]),
(“CptS370” , [“CptS233″,”CptS260”]),
(“CptS427” , [“CptS223″,”CptS360”, “CptS370”, “MATH216”, “EE234″])
]
a) [18pts] Assume that you are creating an application for WSU. You would like to write an ML function
prereqFor that takes the list of courses (similar to above) and a particular course number (in tuple
form) and returns the list of the courses which require this course as a prerequisite.
The type of prereqFor should be (‘a * ”b list) list * ”b -> ‘a list.
(Hint: You can make use of exists function you defined earlier.)
Examples:
> prereqFor (prereqsList,”CptS260″)
[“CptS360″,”CptS370″]
> prereqFor (prereqsList,”CptS223”)
[“CptS260″,”CptS315″,”CptS321″,”CptS322″,”CptS350″,”CptS355″,”CptS360”,
“CptS427″]
> prereqFor (prereqsList,”CptS355″)
[]
> prereqFor (prereqsList,”MATH216”)
[“CptS223″,”CptS233″,”CptS317″,”CptS427″]
b) [2pts] Explain in a comment why the type is
(‘a * ”b list) list * ”b -> ‘a list but not
(”a * ”a list) list * ”a -> ”a list
5. isPalindrome – 20%
A palindrome is a sentence or phrase that is the same forwards and backwards, ignoring spaces,
punctuation and other special characters, and upper vs. lower case. In this problem we will consider
palindromes that include only letters, digits, and spaces but don’t include any punctuation or any special
characters — for example “a01 02 2010A”, “Yreka Bakery”, and “Doc note I dissent a fast never prevents
a fatness I diet on cod”. Assume that letters are case insensitive — for example “Madam Im Adam”
Write an ML function isPalindrome that takes a string as argument and that returns true if the
string is a palindrome and false otherwise. (Note: you can make use of the following ML functions:
rev (for reversing a list), String.explode (for retrieving the list of characters in a given string), and
Char.toUpper (for retrieving the uppercase of a given character).)
The type of isPalindrome should be: string -> bool.
Examples:
> isPalindrome “a01 02 2010A”
true
> isPalindrome “Doc note I dissent a fast never prevents a fatness I diet on
cod”
true
> isPalindrome “Yreka Bakery”
true
> isPalindrome “top cart pop tracPOT”
6. groupSumtoN – 20%
groupSumtoN function takes two arguments where the first argument is an integer (N) and the
second is a list (L). The goal is to produce a result in which the elements of the original list have been
collected into ordered sub-lists each containing maximum number of consecutive elements from L
summing up to N or less (where N is the integer argument). The leftover elements (if there is any) are
included as the last sub-list with a sum less than N. If an element in the input list L is greater than N,
that element should be included in its own sublist (including that element only).
The type of groupSumtoN should be: int -> int list -> int list list.
Note: this function is not required to be tail-recursive.
Examples:
> groupSumtoN 15 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[1,2,3,4,5],[6,7],[8],[9],[10]]
> groupSumtoN 11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[1,2,3,4],[5,6],[7],[8],[9],[10]]
> groupSumtoN 1 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]
> groupSumtoN 5 []
[[]]
Testing your functions
For each problem, write a test function that compares the actual output with the expected (correct)
output.
– For exists, replace and prereqFor, the instructor will provide the test functions. But
you should add additional test inputs for these functions testing the uncovered boundary cases.
– For listUnion, isPalindrome, and groupSumtoN, you need to provide your own test
functions. Again, your test inputs should cover the boundary cases as much as possible.
If you don’t change the test inputs or don’t provide the additional test functions your will be deduced at
least 5% in this homework. Test functions should be included at the end of your HW1.sml file.
Below is an example test function for exists:
fun existsTest () =
let
val existsT1 = (exists(8,[7]) = false )
val existsT2 = (exists(“one”,[“two”,”one”]) = true )
val existsT3 = (exists(true,[false,false]) = false )
in
print (“\n————- \nexists:\n” ^
“test1: ” ^ Bool.toString(existsT1) ^ “\n” ^
“test2: ” ^ Bool.toString(existsT2) ^ “\n” ^
“test3: ” ^ Bool.toString(existsT3) ^ “\n”)
end
val _ = existsTest()
Hints about using files containing ML code
In order to load files into the ML interactive system you have to use the function named use.
The function use has the following syntax assuming that your code is in a file in the current directory
named HW4.sml: You would see something like this in the output:
> use “HW1.sml”;
[opening file “HW1.sml”]
…list of functions and types defined in your file
[closing file “HW1.sml”]
> val it = () : unit
The effect of use is as if you had typed the content of the file into the system, so each val and fun
declaration results in a line of output giving its type.
If the file is not located in the current working directory you should specify the full or relative path-name
for the file. For example in Windows for loading a file present in the users directory in the C drive you
would type the following at the prompt. Note the need to use double backslashes to represent a single
backslash.
– use “c:\\users\\example.sml”;
Alternatively you can change your current working directory to that having your files before invoking the
ML interactive system.
You can also load multiple files into the interactive system by using the following syntax
– use “file1”; use “file2”;…; use “filen”;
How to quit the ML environment
Control-Z followed by a newline in Windows or control-D in Linux will quit the interactive session.
ML resources:
• Standard ML of New Jersey
• Moscow ML
• Prof Robert Harper’s CMU SML course notes
