Choosing implementation depending on class instances using rewriting rules
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 ...
Hi Milan,
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?
Have a look at http://okmij.org/ftp/Haskell/types.html#class-based-dispatch Cheers, /Niklas
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@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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
On Wed, Jun 3, 2009 at 7:43 PM, Daniel Peebles <pumpkingod@gmail.com> wrote:
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.
No. You just need to keep anything seen so far in a container with O( log n ) insert/lookup times.
The original n^2 nub also returns the elements in the order of their first appearance rather than sorted order.
Where exactly did sorted order come in? D
participants (4)
-
Daniel Peebles -
Dinko Tenev -
Milan Straka -
Niklas Broberg