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

[Daniel Fischer]

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.