[Haskell-cafe] type families and type signatures
Manuel M T Chakravarty
chak at cse.unsw.edu.au
Wed Apr 9 23:20:55 EDT 2008
> On Wed, Apr 9, 2008 at 8:53 AM, Martin Sulzmann <martin.sulzmann at gmail.com
> > wrote:
> Lennart, you said
> (It's also pretty easy to fix the problem.)
> What do you mean? Easy to fix the type checker, or easy to fix the
> program by inserting annotations
> to guide the type checker?
> I'm referring to the situation where the type inferred by the type
> checker is illegal for me to put into the program.
> In our example we can fix this in two ways, by making foo' illegal
> even when it has no signature, or making foo' legal even when it has
> a signature.
> To make it illegal: If foo' has no type signature, infer a type for
> foo', insert this type as a signature and type check again. If this
> fails, foo' is illegal.
That would be possible, but it means we have to do this for all
bindings in a program (also all lets bindings etc).
> To make it legal: If foo' with a type signature doesn't type check,
> try to infer a type without a signature. If this succeeds then
> check that the type that was inferred is alpha-convertible to the
> original signature. If it is, accept foo'; the signature doesn't
> add any information.
This harder, if not impossible. What does it mean for two signatures
to be "alpha-convertible"? I assume, you intend that given
type S a = Int
the five signatures
forall a. S a
forall b. S b
forall a b. S (a, b)
are all the "alpha-convertible". Now, given
type family F a b
type instance F Int c = Int
forall a. F a Int
forall a. F Int Int
forall a. F Int a
forall a b. (a ~ Int) => F a b
<and so on>
So, I guess, you don't really mean alpha-convertible in its original
syntactic sense. We should accept the definition if the inferred and
the given signature are in some sense "equivalent". For this
"equivalence" to be robust, I am sure we need to define it as follows,
where <= is standard type subsumption:
t1 "equivalent" t2 iff t1 <= t2 and t2 <= t1
However, the fact that we cannot decide type subsumption for ambiguous
types is exactly what led us to the original problem. So, nothing has
Trying to make those definitions that are currently only legal
*without* a signature also legal when the inferred signature is added
(foo' in Ganesh's example) doesn't seem workable. However, to
generally reject the same definitions, even if they are presented
without a signature, seems workable. It does require the compiler to
compute type annotations, and then, check that it can still accept the
annotated program. This makes the process of type checking together
with annotating the checked program idempotent, which is nice.
More information about the Haskell-Cafe