<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    I'm writing a merge sort function, but I get type error under such
    implementation:<br>
    <blockquote>mergesort :: (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt;
      [a]<br>
      mergesort cmp xs = mergeAll (map (\x -&gt; [x]) xs)<br>
      &nbsp;&nbsp;&nbsp; where<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergeAll :: [[a]] -&gt; [a]<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergeAll [x] = x<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergeAll xs = mergeAll (mergePairs xs)<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergePairs :: [[a]] -&gt; [[a]]<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergePairs (a:b:xs) = merge a b : mergePairs xs<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergePairs xs = xs<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; merge :: [a] -&gt; [a] -&gt; [a]<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; merge as@(a:as') bs@(b:bs')<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | cmp a b == GT = b : merge as bs'<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp; = a : merge as' bs<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; merge [] bs = bs<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; merge as [] = as<br>
    </blockquote>
    And ghc says:<br>
    <blockquote>&nbsp;&nbsp;&nbsp; Couldn't match type `a1' with `a'<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `a1' is a rigid type variable bound by<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; the type signature for merge :: [a1] -&gt; [a1] -&gt;
      [a1]<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; at
      /home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:135:7<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; `a' is a rigid type variable bound by<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; the type signature for<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mergesort :: (a -&gt; a -&gt; Ordering) -&gt; [a]
      -&gt; [a]<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; at
      /home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:124:1<br>
      &nbsp;&nbsp;&nbsp; In the first argument of `cmp', namely `a'<br>
      &nbsp;&nbsp;&nbsp; In the first argument of `(==)', namely `cmp a b'<br>
      &nbsp;&nbsp;&nbsp; In the expression: cmp a b == GT<br>
    </blockquote>
    But if I comment all type signatures, ghc works fine on it.<br>
    I would really appreciate it if you can point out what causes this
    question? And how<br>
    to fix it without changing the structure of the program (i.e. not
    adding function `cmp' as a parameter of `merge' etc.).<br>
    Thx.<br>
  </body>
</html>