Haskell: Newbie currying mistake
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.
