[Haskell-cafe] Writing insertionSort using foldr and a helper function

jorgemal1960 at gmail.com jorgemal1960 at gmail.com
Thu Sep 29 18:09:10 UTC 2016

I am posting the same question again because I had not subscribed to the 
list and I received a message saying it was automatically rejected.

I have the following function that 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.
So, if the list is sorted, then the list will remain sorted.

myInsert :: Ord a => a -> [a] -> [a]
myInsert x [] = [x]
myInsert x (y:ys) = if x < y then x:y:ys else y:myInsert x ys

Now, I have to use the above function myInsert and foldr to implement 
another function called insertionSort. I have been able to do it without 
using foldr as follows and it works just fine:

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = myInsert x (insertionSort xs)

I have worked for 2 days to use foldr without success, for example:

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = foldr (myInsert) x (insertionSort xs)

But it does not even compile, I get the following error which refers to 
last instruction at position "x" in "foldr (myInsert) x (insertionSort xs)":

Couldn't match expected type ‘[a]’ with actual type ‘a’

I will very much appreciate your feedback in order to solve my issue.

Best regards.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160929/a6420c41/attachment.html>

More information about the Haskell-Cafe mailing list