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]
where
myNub xs = nub' Set.empty xs
where
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.
Because:
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
-fallow-undecidable-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