13

为什么这会导致冲突？

class Foo a b | b -> a where
  foo :: a -> b -> Bool

instance Eq a => Foo a a where
  foo = (==)

instance Eq a => Foo a (a -> a) where
  foo x f = f x == x

请注意，如果我删除功能依赖，代码将编译。

我的印象是，函数依赖应该只禁止像下面这样的东西，而事实上，它可以编译！

class Foo a b | b -> a where
  foo :: a -> b -> Bool

instance Eq a => Foo a a where
  foo = (==)

instance Eq a => Foo Bool a where
  foo _ x = x == x

相同b的参数，但不同的a参数。不应该b -> a禁止这样做，因为这意味着a由b?

4

2 回答 2

15

您是否尝试过实际使用第二个版本？我猜当实例编译时，当你调用foo.

这里最大的绊脚石是fundeps不会像你期望的那样与类型变量交互——实例选择并不是真正寻找解决方案，它只是通过尝试统一来盲目匹配。具体来说，当您编写 时Foo a a，a是完全任意的，因此可以与类似 的类型统一b -> b。当第二个参数的形式为b -> b时，它因此匹配两个实例，但fundeps 说在一种情况下第一个参数应该是b -> b，但在另一种情况下它应该是b。因此冲突。

由于这显然使人们感到惊讶，因此如果您尝试使用第二个版本会发生以下情况：

  • bar = foo () ()结果是：

    Couldn't match type `Bool' with `()'
  When using functional dependencies to combine
    Foo Bool a,

    ...因为fundep通过第二个实例说，作为第二个参数的任何类型都唯一地确定Bool为第一个。所以第一个参数必须是Bool.

  • bar = foo True ()结果是：

    Couldn't match type `()' with `Bool'
  When using functional dependencies to combine
    Foo a a,

    ...因为fundep通过第一个实例说，作为第二个参数的任何类型都唯一地确定了第一个参数的相同类型。所以第一个参数必须是().

  • bar = foo () True由于这两种情况都会导致错误，因为这一次他们同意第一个参数应该是Bool.

  • bar = foo True True结果是：

    Overlapping instances for Foo Bool Bool
  arising from a use of `foo'

    ...因为两个实例都满足，因此重叠。

挺好玩的吧？

于 2011-09-15T19:25:41.023 回答
2

第一个实例说任何 a然后fundep给你一个a。这意味着它将排除几乎所有其他内容，因为其他任何内容都应与该自由变量统一，从而强制选择该实例。

编辑：最初我建议第二个例子有效。它在 ghc 7.0.4 上确实如此，但这样做没有任何意义，而且这个问题似乎已在较新的版本中得到解决。

于 2011-09-15T19:31:20.443 回答