双向函数依赖

Question

我的类型 class 看起来有点像下面这样：

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

或者至少这些是对我的问题很重要的部分。 class 无法编译，这是有充分理由的。这个 class 的问题是我可以（如果我想的话）执行以下操作：

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

现在如果我调用 g True 会有两个单独的结果，每个实例一个。编译器发现了这种可能性并告诉我我的类型 class 不好。

我的问题是依赖性 | a -> b 与我的意思不完全相同。我不只是说你可以从 b 中找到 a，而且你可以从 a 中找到 b。也就是说，每种类型都只能是 Foo 的成员，并且具有另一种类型，因此我们可以给定一种类型来找到另一种类型。或者换句话说，依赖是双向的。这种功能依赖性会阻止我在两个单独的实例中出现 Bool，因为第一个参数可以从第二个参数派生，第二个参数可以从第一个参数派生。

但我不知道如何向编译器表达这个想法。

如何创建双向函数依赖？或者，更有可能的是，有没有一种方法可以重新表述我的类型 class 以获得可以替代双向函数依赖性的东西？

Answer 1

在a和b之间的双向依赖可以表示为两个函数依赖a -> b 和 b -> a，例如：

class Foo a b | a -> b<b>, b -> a</b> where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

所以这里 a 的功能依赖于 b 而 b 的功能依赖于 a.

对于您的 instances 然而这当然会引发错误，因为现在您为 b ~ Bool 定义了两个不同的 as。这将引发如下错误：

file.hs:6:10: error:
    <b>Functional dependencies conflict</b> between instance declarations:
      instance Foo () Bool -- Defined at file.hs:6:10
      instance Foo ((), ()) Bool -- Defined at file.hs:11:10
Failed, modules loaded: none.

由于函数依赖，b ~ Bool只能定义一个a。但这可能正是您正在寻找的：一种防止为相同的 a 或相同的 b 定义两次 Foo 的机制。

Answer 2

（这是评论而不是答案，因为它没有解决 OP 提出的确切问题。）

补充 Willem 的回答：现在我们有另一种方法让 GHC 接受这个 class。

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

正如 GHC 在其错误消息中所建议的那样，我们可以打开 AllowAmbiguousTypes。 OP 指出，如果我们评估 g False 之类的东西并且有两个匹配的实例，例如

，那么运行就会遇到麻烦

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

确实，在这种情况下 g False 变得模棱两可。那么我们有两个选择。

首先，我们可以通过向 class 添加函数依赖性 b -> a 来禁止同时拥有上述两个实例（正如 Willem 所建议的）。这使得 g False 变得明确（在这种情况下我们不需要扩展名）。

或者，我们可以在代码中保留这两个实例，并使用类型应用程序（另一个扩展）消除调用 g False 的歧义。例如，g @() False 选择第一个实例，而 g @((),()) False 选择第二个实例。

完整代码：

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
    FlexibleInstances, AllowAmbiguousTypes, TypeApplications #-}

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

main :: IO ()
main = print (g @() False, g @((),()) False)

Answer 3

几乎正是我想要的，但我意识到还有另一种方式可能值得一提。为了获得预期的行为，我们实际上可以将 class 拆分为多个 classes。有几种方法可以做到这一点，最好的选择可能取决于具体情况。但是，对于问题中的代码，您可以采用一种方法：

class Bar b where
  g :: b -> Bool

class (Bar b) => Foo a b | a -> b where
  f :: a -> Bool
  h :: a -> b -> Bool

现在我们仍然允许我们使用相同的 b 创建两个不同的 Foo 实例，但我们不再有歧义，因为 g 现在是 [= 的成员15=] 两者之间必须有一个实例。

这通常可以通过移动可能不明确的功能并将其移动到单独的类型来完成class。

我们可以使用额外的类型 classes 来创建第二个 class 来强制双向性。对于这个例子，它看起来像：

class Bar a b | b -> a

class (Bar a b) => Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

这里Bar是让b依赖于a的行为，防止我们产生歧义。因为 Foo 需要 Bar 而 Bar 允许 a 从 b 派生，所以 Foo 的任何实例都允许 a源自 b。这几乎是我最初想要的，但它只是 Willem Van Onsem 答案的稍微复杂的版本。

双向函数依赖

Bidirectional Functional Dependencies

haskell

typeclass

functional-dependencies

type-level-computation