[Note that Standard ML of New Jersey ordinarily prints only the first 12 items in a list. If you enter the command
Compiler.Control.Print.printLength := 1000;it will print the first 1000 items instead.]
- revlists [[0,1,1],[3,2],[],[5]]; val it = [[1,1,0],[2,3],[],[5]] : int list listNote that this is extremely easy to do, using map.
- nth (["a","b","c","d","e"], 3); val it = "d" : stringDon't worry about what happens if n is out of bounds.
By the way, List.nth is actually a built-in function. Needless to say, you aren't allowed to use it in solving this problem!
- middle [1,2,3,4,5]; val it = 3 : intIf the list has an even number of elements, return the first element of the second half of the list:
- middle [true, false]; val it = false : bool
- cartesian ["a","b","c"] [1,2]; val it = [("a",1),("a",2),("b",1),("b",2),("c",1),("c",2)] : (string * int) list
fun merge([], ys) = ys | merge(xs, []) = xs | merge(x::xs, y::ys) = if x < y then x::merge(xs, y::ys) else y::merge(x::xs, ys) fun split [] = ([],[]) | split [a] = ([a],[]) | split (a::b::cs) = let val (M,N) = split cs in (a::M, b::N) end fun mergesort [] = [] | mergesort [a] = [a] | mergesort [a,b] = if a <= b then [a,b] else [b,a] | mergesort L = let val (M,N) = split L in merge (mergesort M, mergesort N) endNote that mergesort includes three base cases ([], [a], [a,b]) and all are handled correctly.
Suppose we delete the third line of mergesort, so that [a,b] is no longer handled as a base case. You can verify that this change makes no difference in the type of mergesort or in its behavior.
Now suppose we also delete the second line of mergesort, leaving
fun mergesort [] = [] | mergesort L = let val (M,N) = split L in merge (mergesort M, mergesort N) endWhat effect does this change have on the type that SML infers for mergesort? You can verify that mergesort no longer works correctly. Explain what has gone wrong, referring explicitly to the three steps in the "Checklist for Programming with Recursion" presented in class.