Choosing implementation depending on class instances using rewriting rules

[Daniel Peebles]

This isn't necessarily correct, is it? An equality-based (n^2) nub
works "fine" on infinite lists, whereas any O(n log n) sort-based nub
must necessarily evaluate the entire list before being able to return
the value. The original n^2 nub also returns the elements in the order
of their first appearance rather than sorted order.

Of course, you may not care about this and just be experimenting with
rewrite rules, in which case I can't help you :)

Dan

On Wed, Jun 3, 2009 at 5:58 AM, Milan Straka <fox at ucw.cz> wrote:
> 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 ...
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>