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'
  

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

很有趣,是吧？