Haskell功能依赖冲突 [英] Haskell functional dependency conflict

问题描述

为什么会导致冲突?

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

请注意，如果删除功能依赖项，则代码将编译.

Note that the code will compile if I remove the functional dependecy.

我的印象是，功能依赖项仅应禁止以下内容，而实际上它们可以编译！

I was under the impression that functional dependencies should only disallow stuff like the following, when in fact, it compiles!

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

Same b parameter, yet different a parameters. Shouldn't b -> a disallow this, as this means a is uniquely determined by b?

推荐答案

您是否尝试过使用 第二版?我猜想在实例编译时，调用 foo 时，您将开始变得模棱两可并出现重叠错误.

Have you tried actually using the second version? I'm guessing that while the instances compile, you'll start getting ambiguity and overlap errors when you call foo.

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

The biggest stumbling block here is that fundeps don't interact with type variables the way you might expect them to--instance selection doesn't really look for solutions, it just blindly matches by attempting unification. Specifically, when you write Foo a a, the a is completely arbitrary, and can thus unify with a type like b -> b. When the second parameter has the form b -> b, it therefore matches both instances, but the fundeps say that in one case the first parameter should be b -> b, but in the other that it should be b. Hence the conflict.

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

Since this apparently surprises people, here's what happens if you try to use the second version:

• bar = foo()()结果为:

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

...因为在第二个实例中，fundep表示任何类型作为第二个参数都将 Bool 唯一地确定为第一个.因此，第一个参数必须是 Bool .

...because the fundep says, via the second instance, that any type as the second parameter uniquely determines Bool as the first. So the first parameter must be Bool.

bar = foo True()结果为:

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

...因为资金支持者通过 first 实例说，任何类型作为第二个参数都唯一地确定第一个参数的 same 类型.因此，第一个参数必须为().

...because the fundep says, via the first instance, that any type as the second parameter uniquely determines the same type for the first. So the first parameter must be ().

bar = foo()True 会由于 both 实例而导致错误，因为这一次他们同意第一个参数应为 Bool .

bar = foo () True results in errors due to both instances, since this time they agree that the first parameter should be Bool.

bar = foo True True 结果为:

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

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

...because both instances are satisfied, and therefore overlap.

好玩吧?

这篇关于Haskell功能依赖冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！