GHC: Ticket #6134: Incorrect ambiguity error with functional dependencies
http://ghc.haskell.org/trac/ghc/ticket/6134
<p>
GHC reject a program as ambiguous when it is not. Consider the following example:
</p>
<pre class="wiki">{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleContexts #-}
class C a b | a -> b where
f :: a -> b
test :: (Show a, C Int a) => Bool
test = show (f (1 :: Int)) == "1"
</pre><p>
GHC rejects the program with the following error:
</p>
<pre class="wiki"> Ambiguous constraint `C Int a'
At least one of the forall'd type variables mentioned by the constraint
must be reachable from the type after the '=>'
In the type signature for `test': test :: (Show a, C Int a) => Bool
</pre><p>
The only variable, <tt>a</tt>, is fully determined by the type <tt>Int</tt> via the functional dependency on class <tt>C</tt> so there is no ambiguity.
</p>
<p>
These sort of errors crop up when we desugar implicit parameters into uses of the <tt>IP</tt> class (which has a functional dependency).
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/6134
Trac 1.0.9simonpjTue, 05 Jun 2012 21:59:38 GMTdifficulty set
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:1
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:1
<ul>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
</ul>
<p>
Right. This check, on user type signatures, is <em>purely</em> there to report types that cannot possibly be used. So for example we want to reject:
</p>
<pre class="wiki">f :: C [a] => Int
</pre><p>
The idea is there can be no legal calls to <tt>f</tt> because every call will give rise to an ambiguous constraint. We could soundly omit the ambiguity check on type signatures entirely, at the expense of delaying ambiguity errors to call sites.
</p>
<p>
But is every call to <tt>f</tt> ambiguous? After all, we might have
</p>
<pre class="wiki">intance C [a] where ...
</pre><p>
at the call site. So maybe that type is ok! What about the quintessentially ambiguous type
</p>
<pre class="wiki">f :: C a => Int
</pre><p>
Well, with <tt>UndecidableInstances</tt> we could have
</p>
<pre class="wiki">instance C a where ...
</pre><p>
and now a call could be legal after all! (But only with <tt>UndecidableInstances</tt>.
</p>
<p>
So it's clear that the present check is too conservative (rejects perfectly ok programs). Using the visible fundeps is also too conservative. Consider
</p>
<pre class="wiki">class C a b where ...
class D a b | a -> b where ...
instance D a b => C [a] b where...
f :: C a b => a -> a
</pre><p>
Here <tt>f</tt>'s type looks ambiguous in <tt>b</tt>, but here's a legal call:
</p>
<pre class="wiki">...(f [True])...
</pre><p>
That gives rise to a <tt>(C [Bool] beta)</tt> constraint, and using the instance means we need <tt>(D Bool beta)</tt> and that fixes <tt>beta</tt> via <tt>D</tt>'s fundep!
</p>
<p>
So I think the only types we can reject as definitely ambiguous are ones like this
</p>
<pre class="wiki"> f :: (Cambig, Cnonambig) => tau
</pre><p>
where
</p>
<ul><li><tt>Cambig</tt>, <tt>Cnonambig</tt> are each a set of constraints.
</li><li><tt>fv(Cambig)</tt> does not intersect <tt>fv( Cnonambig => tau )</tt>
</li><li>The constraints in <tt>Cambig</tt> are all of form <tt>(C a b c)</tt> where a,b,c are type variables
</li><li><tt>Cambig</tt> is non-empty
</li><li><tt>-XUndecidableInstances</tt> is not on.
</li></ul><p>
That narrows the scope of the test considerably. Make sense?
</p>
<p>
Simon
</p>
<p>
</p>
Ticketsimonpj@…Fri, 08 Jun 2012 08:47:33 GMT
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:2
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:2
<p>
commit <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/dc0ef28faa47edc41681494b8d5210213e866740/ghc" title="Make the ambiguity check more conservative so that it does not reject ...">dc0ef28faa47edc41681494b8d5210213e866740</a>
</p>
<pre class="wiki">Author: Simon Peyton Jones <simonpj@microsoft.com>
Date: Fri Jun 8 09:43:12 2012 +0100
Make the ambiguity check more conservative so that it does not reject valid programs
See Note [The ambiguity check for type signatures] in TcMType,
and Trac #6134, which this change fixes.
A bit of refactoring as usual.
compiler/typecheck/TcMType.lhs | 248 ++++++++++++++++++++++------------------
1 files changed, 135 insertions(+), 113 deletions(-)
</pre>
TicketsimonpjFri, 08 Jun 2012 08:50:51 GMTstatus changed; testcase, resolution set
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:3
http://ghc.haskell.org/trac/ghc/ticket/6134#comment:3
<ul>
<li><strong>testcase</strong>
set to <em>typecheck/should_compile/T6134</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
Ticket