possible OI extension
Simon PeytonJones
simonpj at microsoft.com
Fri Jun 27 10:01:00 EDT 2008
Yes, the idea of some kind of backtracking solution of class constraints (multiple instance declarations, choose the one whose context is indeed soluble) has often been suggested, and is quite attractive. But it raises a bunch of new complications. And your proposal does so even more, because it involves a notion of when one context is "stronger" than another. (What exactly does "stronger" mean.)
Just for example, what's the inferred type of
f x = nub (nub [x])
It could be
f :: Eq a => a > [a]
or f :: Ord a => a > [a]
So far as the implementation is concerned, "improvement" currently happens by inplace unification, which is hard to undo when you need backtracking, so there's a practical problem there. That'll be ameliorated as we move towards type functions.
So I can see the attraction, but I doubt I'll implement it anytime soon.
Simon
 Original Message
 From: glasgowhaskellusersbounces at haskell.org [mailto:glasgowhaskell
 usersbounces at haskell.org] On Behalf Of Serge D. Mechveliani
 Sent: 27 June 2008 11:56
 To: glasgowhaskellusers at haskell.org
 Subject: possible OI extension

 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 Haskell98 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
 fglasgowexts fallowoverlappinginstances
 fallowundecidableinstances

 yields the error report:

 Duplicate instance declarations:
 instance [overlap ok] (Eq a) => Nub [a]
  Defined at IOverlap2.hs:8:043
 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

 _______________________________________________
 Glasgowhaskellusers mailing list
 Glasgowhaskellusers at haskell.org
 http://www.haskell.org/mailman/listinfo/glasgowhaskellusers
More information about the Glasgowhaskellusers
mailing list