possible OI extension
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 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.
| -----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]
| 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
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users