On Samstag, 24. November 2012, 22:04:15, Mark Wallace wrote:
I'm writing a merge sort function, but I get type error under such implementation:
mergesort :: (a -> a -> Ordering) -> [a] -> [a] mergesort cmp xs = mergeAll (map (\x -> [x]) xs) where mergeAll :: [[a]] -> [a] mergeAll [x] = x mergeAll xs = mergeAll (mergePairs xs)
mergePairs :: [[a]] -> [[a]] mergePairs (a:b:xs) = merge a b : mergePairs xs mergePairs xs = xs
merge :: [a] -> [a] -> [a] merge as@(a:as') bs@(b:bs')
| cmp a b == GT = b : merge as bs' | otherwise = a : merge as' bs
merge [] bs = bs merge as [] = as
And ghc says:
Couldn't match type `a1' with `a' `a1' is a rigid type variable bound by the type signature for merge :: [a1] -> [a1] -> [a1] at /home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:135:7 `a' is a rigid type variable bound by the type signature for mergesort :: (a -> a -> Ordering) -> [a] -> [a] at /home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:124:1 In the first argument of `cmp', namely `a' In the first argument of `(==)', namely `cmp a b' In the expression: cmp a b == GT
But if I comment all type signatures, ghc works fine on it. I would really appreciate it if you can point out what causes this question?
Type variables are implicitly for all-quantified. Thus the type variable a in the signatures of the local functions is a fresh type variable and has nothing to do with the a from the top-level signature. It is equivalent to you writing merge :: [b] -> [b] -> [b] except there it is obvious that the type signature is wrong.
And how to fix it without changing the structure of the program (i.e. not adding function `cmp' as a parameter of `merge' etc.).
1. Just omit the type signatures, they can be inferred. That's the portable way. 2. Bring the type variable a into scope {-# LANGUAGE ScopedTypeVariables #-} mergesort :: forall a. (a-> a-> Ordering) -> [a] -> [a] then an (unquantified) a in a local type signature refers to the type from the top-level signature. That's a GHC-only (as far as I know) way.