Friends
I've realised that GHC's -XIncoherentInstances flag is, I think,
over-conservative. I propose to liberalise it a bit. This email describes the
issue. Please yell if you think this is a bad idea.
Simon
Suppose we have
class C a where { op :: a -> String }
instance C [a] where ...
instance C [Char] where ...
f :: [b] -> String
f xs = "Result:" ++ op xs
With -XOverlappingInstances, but without -XIncoherentInstances, f won't
compile. Reason: if we call 'f' at Char (e.g. f "foo") then you might think
we should use instance C [Char]. For example, if we inlined 'f' at the call
site, to get ("Result:" ++ op "foo"), we certainly then would use the C [Char]
instance, giving perhaps different results. If we accept the program as-is,
we'll permanently commit 'f' to using the C [a] instance.
The -XIncoherentInstances flag says "Go ahead and use an instance, even if
another instance might become relevant if you were to specialise or inline the
enclosing function." The GHC user manual gives a more precise spec [1].
Now consider this
class D a b where { opD :: a -> b -> String }
instance D Int b where ...
instance D a Int where ...
g (x::Int) = opD x x
Here 'g' gives rise to a constraint (D Int Int), and that matches two instance
declarations. So this is rejected regardless of flags. We can fix it up by
adding
instance D Int Int where ...
but this is pretty tiresome in cases where it really doesn't matter which
instance you choose. (And I have a use-case where it's more than tiresome [2].)
The underlying issue is similar to the previous example. Before, there was
*potentially* more than one way to generate evidence for (C [b]); here there is
*actually* more than one instance. In both cases the dynamic semantics of the
language are potentially affected by the choice -- but -XIncoherentInstnaces
says "I don't care".
So the change I propose to make IncoherentInstances to pick arbitrarily among
instances that match. More precisely, when trying to find an instance matching
a target constraint (C tys),
a) Find all instances matching (C tys); these are the candidates
b) Eliminate any candidate X for which another candidate Y is
strictly more specific (ie Y is a substitution instance of X),
if either X or Y was complied with -XOverlappingInstances
c) Check that any non-candidate instances that *unify* with (C tys)
were compiled with -XIncoherentInstances
d) If only one candidate remains, pick it.
Otherwise if all remaining candidates were compiled with
-XInccoherentInstances, pick an arbitrary candidate
All of this is precisely as now, except for the "Otherwise" part of (d). One
could imagine different flags for the test in (c) and (d) but I really don't
think it's worth it.
Incidentally, I think it'd be an improvement to localise the
Overlapping/Incoherent flags to particular instance declarations, via pragmas,
something like
instance C [a] where
{-# ALLOW_OVERLAP #-}
op x = ....
Similarly {-# ALLOW_INCOHERENT #-}. Having -XOverlappingInstances for the
whole module is a bit crude., and might be missed when looking at an instance.
How valuable would this be?
[1]
http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap
[2] http://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
