lease use the standard ML of New Jersey to complete this. Do not use Here is an SML mergesort program: ---------------------------------------------------------------------------------------------- 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) end --------------------------------------------------------------------------------------------------- Note 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) end ---------------------------------------------------------------------- What effect does this change have on the type that SML infers for mergesort? Verify that whether updated mergesort works correctly by running on your system and explain your findings.
Please use the standard ML of New Jersey to complete this. Do not use
Here is an SML mergesort program:
----------------------------------------------------------------------------------------------
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)
end
---------------------------------------------------------------------------------------------------
Note 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)
end
----------------------------------------------------------------------
What effect does this change have on the type that SML infers for mergesort?
Verify that whether updated mergesort works correctly by running on your
system and explain your findings.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
