[Haskell-beginners] type signature error in a where clause

[Mark Wallace]

On 11/24/2012 11:07 PM, Daniel Fischer wrote:
> 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.
Thanks for answering so fast. And all of your answers are very helpful.
I've tested these two solutions, all works fine.
Now I understand how type signature works in such condition.

Somehow it might seem a bit easier to me to grasp the function of a 
function with the help of type signature.
I'll try just omitting the signatures, it's easier and more handy isn't it?