Haskell 函数依赖冲突

Question

为什么这会导致冲突？

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 唯一确定?

Answer 1

您是否尝试过实际使用第二个版本？我猜当实例编译时，当你调用 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'

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

挺好玩的吧？