[Haskellcafe] A type signature inferred by GHCi that is
rejected when written explicitly
Simon PeytonJones
simonpj at microsoft.com
Wed Jul 16 15:51:59 EDT 2008
 > I myselft don't understand why GHCi doesn't accept the type it
 > infered as an explicit signature ...
I've known about this confusing behavior for some time, and the design goal that the compiler should not infer a type that it can't check seems Clearly Right. Stupidly, though, I had not previously realized that it's all a consequence of GHC's rather relaxed approach to ambiguity. Here's a little section from a some notes I'm working on that may clarify. Bottom line: I intend to change GHC (I hope for 6.10) so that if a definition gets an inferred type that could not appear as a type signature, the definition will be rejected as ambiguous.
Comments welcome. (Do cc me since I no longer guarantee to read all of the wisdom of Haskell Café.)
Simon
Consider this
\begin{code}
class C a b where
op :: b > a > a
instance C [a] b
op _ x = x
instance Ord b => C (Maybe a) b
op _ x = x
f x = op undefined x
\end{code}
GHC currently infers the type
\begin{code}
f :: C a b => a > a
\end{code}
Despite the fact that @b@ is not mentioned after the @=>@, nor is
there a functional dependency, @f@ can be called unambiguously, thus
\begin{code}
f [True]
\end{code}
This call gives rise to the constraint @(C [Bool] b)@, for some undetermined
type @b@, and the instance declaration fires happily. However, the call
@(f Nothing)@ will give the constraint @(Ord b)@, which cannot be discharged
without knowing @b at . Some calls are ambiguous and some are not. GHC
defers this choice to the caller, unless it can readily see that every
call will be ambiguous.
However, this relaxed approach has a big disadvantage: \emph{you cannot
write a type signature for @f@!}:
\begin{code}
f :: C a c => a > a
f x = op undefined x
\end{code}
Now GHC has no way to prove that the given constraint @(C a c)@
proves the wanted constraint @(C a b)@, using plain syntactic matching.
So we propose the following:
\begin{itemize}
\item Every inferred type (and every type written by the programmer)
must be unambiguous.
\item A type $\forall \overline{a}.C \Rightarrow \rho$ is unambiguous iff
from $C$ we can deduce $C[\overline{b'/b}]$ where $\overline{b} = \overline{a} \setminus fv(\rho)$,
and $\overline{b'}$ are fresh. That is, freshen the variables in $C$ that
are not mentioned in the type $\rho$, and check that you can can deduce
the freshened $C'$ from $C$.
\end{itemize}
This would reject the definition @f@, either with or without a type
signature.
 Original Message
 From: haskellcafebounces at haskell.org [mailto:haskellcafe
 bounces at haskell.org] On Behalf Of Pablo Nogueira
 Sent: 08 July 2008 09:03
 To: Alfonso Acosta
 Cc: HaskellCafe
 Subject: Re: [Haskellcafe] A type signature inferred by GHCi that is
 rejected when written explicitly

 > I myselft don't understand why GHCi doesn't accept the type it
 > infered as an explicit signature ...

 I think it has to do with the following:

 Looking at the type errors, they seem to indicate that the type
 checker is being general and does not assume the From and To
 "relations" are between
 a type t and (s (t x) x) but, in general, between t and s (t' x) x.

 Given that

 from :: (From a1 c1 x) => a1 x > c1 x
 to :: (To a2 c2 y) => c2 y > a2 y
 bimap :: Bifunctor s => (t1 > t3) > (t2 > t4) > s t1 t2 > s t3 t4

 During type checking the following equations spring up:

 c2 y = s t3 t4
 c1 x = s t1 t2
 t2 = x
 t4 = y
 t1 = a1 x
 t3 = a2 y

 That'd give the same type as that inferred, but somehow new variables
 a11 and a12 appear.

 > caused by a lack of functional dependencies.
 > class From a c x  a > c where
 > class To a c y  c > a where
 > ... hushes GHCi. The question now is, of course, if the new
 > dependencies are too restrictive for your problem.

 They are of little avail given the instances I define:

 instance Bifunctor s => From (Fix s) (s (Fix s x)) x where
 from = out

 instance Bifunctor s => To (Fix s) (s (Fix s y)) y where
 to = In
 _______________________________________________
 HaskellCafe mailing list
 HaskellCafe at haskell.org
 http://www.haskell.org/mailman/listinfo/haskellcafe
More information about the HaskellCafe
mailing list