覆盖条件失败 [英] the Coverage Condition fails

问题描述

  { - ＃LANGUAGE 
 MultiParamTypeClasses，
 FunctionalDependencies，
 FlexibleInstances，
 FlexibleContexts 
＃ - } 
 
 class图表| g  - > n e其中
 nodes :: g  - > [n] 
 edge :: g  - > （n，n）→>也许e 
 
实例图g g e其中
节点g = [] 
 edge g（n1，n2）= Nothing 
  

我得到一个与覆盖条件相关的错误，其中一个函数依赖失败。我需要添加-XUndecidableInstances来允许这个吗？或者我如何解决这个问题？谢谢

解决方案

您的问题不是 Int ，而是ë。覆盖条件记录在 GHC手册 Sect。 7.6.3.2。放宽实例上下文的规则并说：

覆盖条件。对于类的每个函数依赖关系tvs _left - > tvs _right ，S（tvs _right ）中的每个类型变量必须出现在S （tvs _left ），其中S是将类声明中的每个类型变量映射到实例声明中相应类型的替换。

这在实践中意味着什么？在你的情况下，你的函数依赖表示 g - > ne ，这意味着对于每个实例，由 n 和 e 表示的类型是唯一的对于由 g 表示的类型。现在让我们假设你正在定义一个实例

 实例图SomeTypeG SomeTypeN SomeTypeE其中
 ... 
  

覆盖条件表示出现在 SomeTypeE 或 SomeTypeN 必须出现在 SomeTypeG 中。如果不满意会发生什么？假设类型变量 a 出现在 SomeTypeE 中，但不在 SomeTypeG 。然后，对于固定 SomeTypeG ，我们可以通过用 a 替换不同类型的可能实例。

您的情况

 实例图形g Int e其中
 .. 。
  

e 就是这样的一个类型变量，所以通过Coverage条件它必须出现在 g 中，这是不正确的。因为它没有出现，所以你的定义意味着 Graph g Int Int 是一个实例， Graph g Int（Maybe Char）是另一个实例等，与函数依赖相矛盾，要求只有一个实例。

如果您定义了像

  instance Graph g Int Char其中
  

然后就可以了，因为 Int 和 Char 中没有类型变量。另一个有效的实例可以是

 实例图（g2 e）其中
  

其中 g2 现在是 * - > * 。在这种情况下， e 出现在 g2 e 中，满足Coverage Condition，事实上 e 始终由 g2 e 确定。

I have a very simple piece of code as follow:

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

class Graph g n e | g -> n e where
    nodes           :: g -> [n]                             
    edge            :: g -> (n,n) -> Maybe e                

instance Graph g Int e where
    nodes g = []
    edge g (n1,n2) = Nothing

I got an error related to the Coverage Condition fails for one of the functional dependencies. Do I need to add -XUndecidableInstances to permit this? or how I can fix this problem? Thanks

解决方案

The problem in your case is not Int but e. The Coverage Condition is documented in GHC's manual Sect. 7.6.3.2. Relaxed rules for instance contexts and says:

The Coverage Condition. For each functional dependency, tvs_left -> tvs_right, of the class, every type variable in S(tvs_right) must appear in S(tvs_left), where S is the substitution mapping each type variable in the class declaration to the corresponding type in the instance declaration.

What does it mean in practise? In your case, your functional dependency says g -> n e, which means that for each instance the types denoted by n and e are unique for the type denoted by g. Now let's say you're defining an instance

instance Graph SomeTypeG SomeTypeN SomeTypeE where
    ...

The coverage condition says that any type variable appearing in SomeTypeE or SomeTypeN must appear in SomeTypeG. What happens if it's not satisfied? Let's suppose a type variable a appears in SomeTypeE but not in SomeTypeG. Then for fixed SomeTypeG we would have an infinite number of possible instances by substituting different types for a.

In your case

instance Graph g Int e where
    ...

e is such a type variable, so by the Coverage Condition it must appear in g, which is not true. Because it doesn't appear there, your definition would imply that Graph g Int Int is an instances, Graph g Int (Maybe Char) is another instance, etc., contradicting the functional dependency that requires that there is precisely one.

If you had defined something like

instance Graph g Int Char where

then it would be OK, as there are no type variables in Int and Char. Another valid instance could be

instance Graph (g2 e) Int e where

where g2 is now of kind * -> *. In this case, e appears in g2 e, which satisfies the Coverage Condition, and indeed, e is always uniquely determined from g2 e.

这篇关于覆盖条件失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！