[Haskell-cafe] Re: Type constraints for class instances

[apfelmus]

Krzysztof Skrzętnicki wrote:
> class YOrd a where
>     ycmp :: a -> a -> (a,a)

> Unfortunately, the performance of ysort is rather low. I believe that
> it is impossible to create any sorting algorithm that uses ycmp
> instead of compare, that is faster than O(n^2).

It is possible, the following implementation of  mergesort  is O(n log n) :)

   ysort :: (YOrd a) => [a] -> [a]
   ysort = head . mergeAll . map (:[])
     where
     mergeAll (x:y:zs) = mergeAll $ merge x y : mergeAll zs
     mergeAll xs = xs

     merge []     ys = ys
     merge (x:xs) ys = merge3 x ys xs

     merge3 x []     xs = x  : xs
     merge3 x (y:ys) xs = x' : merge3 y' xs ys
         where (x',y') = x `ycmp` y


Mergesort works like a tournament and the idea is to introduce

   merge3 :: YOrd a => a -> [a] -> [a] -> [a]

to make the intermediate candidates explicit. In a call

   merge3 x ys zs

, the candidate  x  is pitted against the  head  of  ys . The winner is 
moved to the front and the loser is the new candidate ( ycmp  is enough 
to do that). Furthermore, there is the invariant that  x  became 
candidate by winning over all  xs  (formally:  x <= minimum xs), there 
is no need to pit  x  against them for a second time.


The whole thing is O(n log n) for the usual reasons, the important part 
being that  merge3  is  O(1 + length xs + length ys). The problem with 
your solution was that  merge [gt] (merge xs ys)  could be  O(2 * length 
ys) or something. Both solutions are almost the same because

   merge3 x ys xs  ~  merge [x] (merge xs ys)

, but  merge3  incorporates the additional insight that we don't need to 
pit  x  against the  xs  anymore.


Regards,
apfelmus