Insertion sort in Haskell

Question

I'm doing some exercises on Haskell. First I was asked to define a function insert :: Int -> [Int] -> [Int] so that insert x xs inserts x into the list xs in such a way that x is bigger than those elements before it and smaller than or equal to the element that follow it:

insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x (y:ys) = if x < y 
                 then x:y:ys 
         else y : insert x ys

Now I need to use insert to define a function insertionSort :: [Int] -> [Int]. Here's my attempt:

insertionSort :: [Int] -> [Int]
insertionSort [x] = [x]
insertionSort (x:xs) = insert x insertionSort xs

Error: Couldn't match expected type [Int] with actual type [Int] -> [Int]

Anyone know how I can fix this? Any insight is highly appreciated, thanks.

Solution 1

insert x insertionSort xs

is calling insert with three arguments (x,insertionSort,xs). Probably you want

insert x (insertionSort xs)

Solution 2

While learning some sorting algorithms myself, I'd like to give you a few suggestions/improvements to your solution:

• Avoid non-exhaustive pattern matching at any case: insertionSort [] = []
• Take advantage of instances of Ord over a fixed type
• Consider lambda lifting by integrating insert into a where statement in order to get rid of the high-level function and save the argument x
• Consider guards over if then else

Which will result in:

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = insert $ insertionSort xs
    where insert [] = [x]
          insert (y:ys)
              | x < y = x : y : ys
              | otherwise = y : insert ys