Question
Here is an ML function that returns the int that is least in a nonempty list of ints: =================================================== (* least : int list ->
Here is an ML function that returns the int that is least in a nonempty list of ints:
=================================================== (* least : int list -> int returns the smallest int in NONEMPTY list, ns. E.g., least [3,1,2] returns 1 least [4] returns 4 least [5, 3, 8, 3] returns 3 *) fun least [n] = n | least (n::ns) = let val m = least ns in if n < m then n else m end | least nil = raise Empty (* the "empty list" error. This equation is optional *) ===================================================
For example, least [3,2,7,8] returns 2. This is because
least [8] = 8 least [7,8] = 7 least [2,7,8] = 2
The recursive calls lead to least [3,2,7,8] = 2.
Now, make a file, Q1.sml, and place the above coding of least in it. Run it and test it with the above three test cases.
Next, code this function and add it to Q1.sml:
=================================================== (* remove : int * int list -> int list builds an answer list that is exactly ns but with the first occurrence, if any, of m removed. For example, remove(2, [3, 2 ,7]) returns [3, 7] remove(2, [3, 2, 7, 2]) returns [3, 7, 2] remove(2, [3]) returns [3] *) remove(m, nil) = ... remove(m, (n::ns)) = ... ===================================================
Test your function on at least the three test cases listed above.
Here's the last part: Selection sort repeatedly finds and moves the least element of a sequence to the front:
[3 2 5 1 4] => 1 [3 2 5 4] => 1 2 [3 5 4] => 1 2 3 [4 5] => 1 2 3 4 [5] => 1 2 3 4 5
You can understand the process as
(i) finding the least element in the unsorted sequence,
(ii) moving it to the front,
(iii) repeating steps (i) and (ii) with what's left.
Use least and remove in your ML coding of selection sort, which you add to Q1.sml:
=================================================== (* ssort : int list -> int list uses the selection-sort strategy to build a list that contains the ints in the argument list, sorted in ascending order E.g., ssort [3,2,5,1,4] returns [1,2,3,4,5] ssort [3] returns [3] ssort [3,2,1,2] returns [1,2,2,3] *) fun ssort nil = ... (* empty-list case *) | ssort xs = ... (* non-empty list case *) ===================================================
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started