Choosing implementation depending on class instances using rewriting rules

[Milan Straka]

Hi,

I am interesting in writing a method nub in such a way, that it will
use O(N^2) trivial algorithm for types with equality only, and O(N log N)
algorithm for comparable types. I would like to say

  class Nub where nub :: [a] -> [a]
  instance Ord a => Nub a where nub = nubOrd
  instance Eq a => Nub a where nub = nubEq

which is of course not valid Haskell. I tried using GHC rewriting rules
to achieve this. My first try was

  {-# NOINLINE nub #-}
  nub :: Eq a => [a] -> [a]
  nub xs = ...

  nubOrd :: Ord a => [a] -> [a]
  nubOrd xs = ...

  {-# RULES "nub/nubOrd" nub = nubOrd #-}

which does not work either, because of missing an Ord a context. I was not
able to write the rule which would fire.

Is there a way to write such a rewriting rule or there is no way of acquiring
the Ord dictionary in rewrite rule? Or does anyone know any other way
of implementing such a nub without explicitly listing all Ord instances?

I wish you a nice day,
Milan Straka

PS: Listing {-# RULES "nub/nubOrd Int" nub = nubOrd :: [Int]->[Int] #-} for
all Ord instances would work, but ...