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

Mark Wallace lotabout at gmail.com
Sat Nov 24 15:04:15 CET 2012


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? And how
to fix it without changing the structure of the program (i.e. not adding 
function `cmp' as a parameter of `merge' etc.).
Thx.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121124/804bde0d/attachment.htm>


More information about the Beginners mailing list