# Mark Needham

Thoughts on Software Development

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.

Be Sociable, Share!

Written by Mark Needham

March 20th, 2012 at 11:55 pm