Haskell – Insertion sort in Haskell

functional-programminghaskell

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.

Best Solution

insert x insertionSort xs

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

insert x (insertionSort xs)
Related Question