Define a function single : \'a list list -> \'a list which takes in input a list

Question

Define a function single : 'a list list -> 'a list

which takes in input a list of lists and gives back the list consisting of all the elements, in the same order in which they appear in the argument.

Here is an SML mergesort program:

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

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

fun merge (t), ys) ys I merge (xs, xs I merge (x: xs, y:: ys) if x y then x: merge (xs, ys) else y merge (x: :xs, ys) fun split split la ([a], I split (a :b: cs) let val M, N) split cs in (a M, b N) end fun mergesort mergesort la [aj I mergesort la,b if a b then a, b] else [b, aj I mergesort L let val (M, N) split L merge (mergesort M mergesort N) end Note that mergesort includes three base cases (CJ, Caj, a,b]) and all are handled correctly

Explanation / Answer

Mergesort now runs in infinite recursion without ever terminating in several cases. In simple base case like mergesort( [] ), it returns [].

For cases like mergesort( [2] ), it goes it (M,N) = split L, where M comes out to be [2], and N comes out to be [] list. Now we see that, input was list with single element, and it again recursively calls mergesort( M ), which essentially repeats the call. Thus it runs into infinite loop.

For list of size > 1, eventually it comes to call of mergesort with sublist of size 1, which again falls in infinite recursion and thus program doesn't terminate.

Thus we observe that mergesort doesn't terminate for inputs other than [] list. Explaination is already provided above.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.