Question

Using guarded equations, implement a function myInsert that behaves the same way as the insert function defined in Data. List package. The Data. List. Insert function takes an element and a list and inserts the element into the list at the first position where it is less than or equal to the next element. In particular, if the list is sorted before the call, the result will also be sorted.


myInsert : : Ord a â a â [a]â a[a]


a. Explain your nylnsert function definition.

b. Using nylnsert and foldr, implement insertion sort (named mySort).

nySort : : Ord a â a â [a]â a[a]

c. Explain how your nySort works when it is applied as below. Your explanation should be closely related to how foldr works.

nySort [3,1,4,2,5]

Answer 1

Sorting involves arranging a set of elements in a particular order (ascending or descending)

The insert function

The insertion sort function written in Python, where comments are used to explain each line is as follows:

#This defines the function

def mySort(myList):

   #This iterates through the list

   for i in range(1, len(myList)):

       #This gets the current element

       currElem = myList[i]

       #This gets the index of the previous element

       j = i - 1

       # This compares the adjacent elements, and rearrange them (if needed)

       while j >= 0 and currElem < myList[j]:

           myList[j + 1] = myList[j]

           j = j - 1

       # This places the current element after a smaller element

       myList[j + 1] = currElem

Read more about sorting techniques at:

https://brainly.com/question/15263760