possible OI extension

Serge D. Mechveliani mechvel at botik.ru
Fri Jun 27 06:55:45 EDT 2008

Hello, people,

This is about possible extension in treating of  overlapping instances.
Here is a simple example.

import qualified Data.Set as Set (empty, member, insert)
import List (nub)

class Nub a where myNub :: a -> a

instance Eq a => Nub [a] where  myNub = nub

instance Ord a => Nub [a] 
  myNub xs = nub' Set.empty xs
             nub' _   []      = []
             nub' set (x: xs) = if  Set.member x set  then  nub' set xs
                                else     x: (nub' (Set.insert x set) xs)

The idea is that it is good to replace  nub  of the Haskell-98 library
with  myNub. 
for  Eq a,   myNub  costs  O(n^2),
for  Ord a,  myNub  costs  O(n*(log n)),
and it is good to denote this operation with the same name.

Compiling this by GHC under 
          -fglasgow-exts -fallow-overlapping-instances

yields the error report:

  Duplicate instance declarations:
      instance [overlap ok] (Eq a) => Nub [a]
        -- Defined at IOverlap2.hs:8:0-43
      instance [overlap ok] (Ord a) => Nub [a]
        -- Defined at IOverlap2.hs:(9,0)-(15,71)

Probably, as the context of  Ord a  is stronger than  Eq a,
then on the instance overlap, the compiler could choose the 
instance with the stronger context.

Can there be a reasonably implemented extension of this kind?

Thank you in advance for your comments,

Serge Mechveliani
mechvel at botik.ru

More information about the Glasgow-haskell-users mailing list