As I mentioned in my last post I’ve spent a bit of this evening writing a merge sort function and one of the mistakes I made a few times was incorrectly passing arguments to the recursive calls of ‘merge’.

For example, this is one of the earlier versions of the function:

``````
middle :: [Int] -> Int
middle = floor . (\y -> y / 2) .  fromIntegral . length
msort :: [Int] -> [Int]
msort unsorted =
let n = middle unsorted
in
if n == 0 then unsorted
else
let (left, right) = splitAt n unsorted
in merge (msort left) (msort right)
where
merge [] right = right
merge left [] = left
merge left@(x:xs) right@(y:ys) = if x < y then x : merge(xs, right) else y : merge (left, ys)
``````

Which doesn’t actually compile:

``````
Couldn't match expected type `[a0]' with actual type `[a0] -> [a0]'
In the return type of a call of `merge'
In the second argument of `(:)', namely `merge (xs, right)'
In the expression: x : merge (xs, right)
``````

My defence for this mistake is that many of the other languages I’ve programmed in take function parameters separated by a comma but in this case I’ve actually only succeeded in currying the ‘merge’ function.

i.e. it thinks I only wanted to pass one value to it and return a function, hence the error message!

One correction would be to change the code to read like this so we can explicitly see that a function which takes 2 arguments can be called with each argument separately:

``````
msort :: [Int] -> [Int]
msort unsorted =
let n = middle unsorted
in
if n == 0 then unsorted
else
let (left, right) = splitAt n unsorted
in merge (msort left) (msort right)
where
merge [] right = right
merge left [] = left
merge left@(x:xs) right@(y:ys) = if x < y then x : merge(xs)(right) else y : merge (left)(ys)
``````

We can do exactly the same with the ‘/’ function to use a simpler example:

``````
-- a long way of dividing 2 by 3
> ((/) 2) 3
0.6666666666666666
``````

The type of ‘/’ is:

``````
> :t (/)
(/) :: Fractional a => a -> a -> a
``````

which means it takes in a ‘Fractional’ and then returns a function which takes in a ‘Fractional’ and returns a ‘Fractional’.

In Haskell function application is left associative which means that ‘f x y’ is the same as ‘(f x) y’ so we can omit the parentheses and pass both arguments together:

``````
> (/) 2 3
0.6666666666666666
``````

And we can do the same thing in the merge sort of course:

``````
msort :: [Int] -> [Int]
msort unsorted =
let n = middle unsorted
in
if n == 0 then unsorted
else
let (left, right) = splitAt n unsorted
in merge (msort left) (msort right)
where
merge [] right = right
merge left [] = left
merge left@(x:xs) right@(y:ys) = if x < y then x : merge xs right else y : merge left ys
``````

A fairly simple mistake to make but it had me confused for a while!

Updated the explanation around how we can pass arguments to ‘/’ after my colleague Gavri pointed out that the initial explanation was incorrect.