为什么GHC认为这种类型的变量不是单射的?

I have this piece of code:

我有这段代码:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, KindSignatures, GADTs, FlexibleInstances, FlexibleContexts #-}

class Monad m => Effect p e r m | p e m -> r where
  fin :: p e m -> e -> m r

data ErrorEff :: * -> (* -> *) -> * where 
  CatchError :: (e -> m a) -> ErrorEff ((e -> m a) -> m a) m

instance Monad m => Effect ErrorEff ((e -> m a) -> m a) a m where
  fin (CatchError h) = \f -> f h

This doesn't compile, with this type error in the last line:

这个没有编译，在最后一行中有这个类型的错误:

Could not deduce (a1 ~ a)
from the context (Monad m)
[...]
or from (((e -> m a) -> m a) ~ ((e1 -> m a1) -> m a1))
[...]

If I change m to [] it compiles fine, so apparently GHC thinks that m is not injective. (Although it doesn't warn about injectivity like it does with type families.)

如果我将m改为[]，它编译得很好，显然GHC认为m不是单射的。(尽管它不像对类型家族那样警告注入性。)

My version of GHC is 7.2.1.

我的GHC版本是7.2.1。

Edit: If I change (e -> m a) to e it works, if I change it to m a it doesn't, and neither for (m a -> e).

编辑:如果我改变(e -> m a)到e的工作，如果我把它改成m a，它不会，也不是(m a -> e)。

2 个解决方案

#1

It's not exactly a bug, but it is a long story...

这并不是一个错误，但这是一个很长的故事。

The Story

In 7.0 there used to be a coercion constructor called right which worked like this:

在7.0中曾经有一个叫做right的强制构造函数，它是这样工作的:

g : f a ~ f b
---------------
right g : a ~ b

That is, if g is a coercion between f a and f b, then right g is a coercion between a and b. This is only sound if f is guaranteed to be injective: otherwise we might legitimately have, say, f Int ~ f Char and then we would be able to conclude Int ~ Char, which would be Bad.

如果g f和f b之间的强制,然后对g是a和b之间的胁迫。这只是声音如果f是保证单射:否则我们可能合法,说,Int ~ f Char然后我们能够得出结论Int ~ Char,这将是坏的。

But of course, type synonyms and type families are not necessarily injective; for example:

但是当然，类型同义词和类型族不一定是单射的;例如:

type T a = Int

type family F a :: *
type instance F Int  = Bool
type instance F Char = Bool 

So how is this guarantee possible? Well, this is precisely the reason why partial applications of type synonyms and type families are not allowed. Partial applications of type synonyms and type families may not be injective, but saturated applications (even ones which result in a higher kind) always are.

那么，这种保证是如何实现的呢?好吧，这正是为什么不允许部分应用类型同义词和类型族的原因。类型同义词和类型族的部分应用可能不是单射的，但是饱和应用(即使是导致更高类型的应用)总是存在的。

Of course, the restriction on partial applications is annoying. So in 7.2, in an attempt to move in the direction of allowing partial application (and because it simplifies the theory and implementation of the coercion language), the right constructor was replaced by a constructor nth, with the accompanying rule

当然，对部分应用程序的限制是恼人的。因此，在7.2中，为了向允许部分应用的方向发展(并且由于它简化了强制语言的理论和实现)，正确的构造函数被第n个构造函数替换，并附带了规则

g : T a1 .. an ~ T b1 .. bn
---------------------------
nth i g : ai ~ bi

That is, nth only applies to a coercion g which is between two types which are known to be saturated applications of a type constructor T. In theory, this allows for partial applications of type synonyms and families, because we cannot decompose equalities until we know that they are between applications of a (necessarily injective) type constructor. In particular, nth does not apply to a coercion f a ~ f b because f is a type variable, not a type constructor.

即n只适用于一个强制g两种类型之间,饱和的应用类型构造函数t .理论上,这允许部分同义词和家庭类型的应用程序,因为我们不能分解应用程序之间的平等,直到我们知道他们是(一定是内射)类型的构造函数。特别是，nth不适用于强制f a ~ f b，因为f是类型变量，而不是类型构造函数。

It was thought at the time of the change that no one would really notice, but obviously this was wrong!

人们认为在变革的时候没有人会真正注意到，但显然这是错误的!

Interestingly, the Olegian trick outlined in the haskell-cafe message from Daniel Schüssler shows that the implementation of type families was not changed accordingly! The problem is that a definition like

有趣的是，在haskell-cafe中，Daniel Schussler提出的奥氏骗局表明类型族的实现并没有相应的改变!问题是这样的定义

type family Arg fa
type instance Arg (f a) = a

should not be allowed if f could be non-injective; in that case the definition does not even make sense.

如果f可以是非单射的，就不允许;在这种情况下，定义甚至没有意义。

Next Steps

I think the right thing to do is to reinstate right (or something equivalent), since people clearly want it! Hopefully this will be done soon.

我认为正确的做法是恢复正确的(或类似的东西)，因为人们显然想要它!希望这能很快完成。

In the meantime, it would still be really cool to allow partially applied type synonyms and families. It seems the Right Way (tm) to do that would be to track injectivity in the kind system: that is, each arrow kind would be annotated with its injectivity. This way when encountering an equality f a ~ f b we could look at the kind of f to determine whether it is safe to decompose it into the equality a ~ b. Not coincidentally, I am currently trying to work out the design of such a system. =)

同时，允许部分应用类型同义词和族仍然是很酷的。似乎正确的方法(tm)应该是跟踪类系统中的注入性:也就是说，每个箭头类都会用它的注入性进行注释。这样，当遇到f a ~ f b的等式时，我们可以考虑f的类型，以确定将其分解为a ~ b的等式是否安全。=)

#2

I'm not sure about the cause, but I reduced your testcase to:

我不确定是什么原因，但我把你的测试案例简化为:

{-# LANGUAGE GADTs #-}

data ErrorEff x where
  CatchError :: m a -> ErrorEff (m a)

fin :: ErrorEff (m a) -> m a
fin (CatchError h) = h

which compiles in GHC 7.0.3 but not 7.3.20111021.

在GHC 7.0.3而不是7.3.20111021中编译。

This is definitely a compiler bug.

这绝对是一个编译错误。

It compiles after changing:

它编译后改变:

data ErrorEff x where
  CatchError :: x -> ErrorEff x

And the function "fin" can be recovered with record syntax:

函数“fin”可以通过记录语法恢复:

data ErrorEff x where
  CatchError :: { fin :: m a } -> ErrorEff (m a)