possible OI extension

[Simon Peyton-Jones]

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 in-place 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: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-
| users-bounces at haskell.org] On Behalf Of Serge D. Mechveliani
| Sent: 27 June 2008 11:56
| To: glasgow-haskell-users 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 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
|
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users