上下文中的约束如何改变 Haskell 中的实例解析

Question

我试图了解在 Haskell 中向实例上下文添加约束如何改变实例分辨率。在这个例子中：

class C a where
  f :: a -> [Char]

instance {-# OVERLAPPABLE #-} C a where
  f = const "thing"

instance C Int where
  f = const "int"

instance {-# OVERLAPPING #-} C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

main = do
  putStrLn $ f (1 :: Int)
  putStrLn $ f [(True :: Bool)]
  putStrLn $ f [(1 :: Int)]
  putStrLn $ f [[(1 :: Int)]]

输出为：

int
list of thing
list of thing
list of thing

最后两行不是我想要的。对于第 3 行，似乎编译器（或运行时？）在列表实例的运行 f 时不知道 a 是 Int 并且只是使用默认的 C a 实例。同样对于最后一行，它无法弄清楚 a 是另一个列表。但是，如果我向列表实例添加上下文：

instance {-# OVERLAPPING #-} (C a) => C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

输出变为：

int
list of thing
list of int
list of list of int

...这就是我想要的。有人可以帮助解释该约束如何更改此示例中的实例解析吗？有没有我可以看的一般规则？

Answer 1

本质上，实例选择仅在编译时执行。在运行时，周围没有类型信息，也没有存储在任何地方的实例列表来驱动实例选择。

那么，您的实例中发生了什么？考虑第一种情况：

instance {-# OVERLAPPING #-} C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

假设向 f 传递了一个 [a0] 类型的列表（为清楚起见，我们使用一个新的变量名）。然后我们需要在最后一行输入 check f x 。上面的变量x的类型是a0，所以GHC需要求解C a0。为此，GHC 必须选择一些实例。通常它会拒绝选择 instance C a 因为 instance C Int 也存在，而 GHC 不知道 a0 = Int 是否存在，所以没有一个实例可以被选为 "definitive" 只有手头的信息。

然而，"overlapping" pragma 指示 GHC 在那些足够通用的实例中选择单个最佳实例来解决约束。事实上，这是我们可以利用手头的信息做的最好的事情：唯一其他合理的选择是引发错误。

在这种情况下，要解决 C a0 我们需要从三个实例中选择一个，只有 instance C a 是通用的，足以匹配 C a0（毕竟，a0 可以是非 Int、非列表类型）。所以我们选择那个。

相反，使用

instance {-# OVERLAPPING #-} (C a) => C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

打开第四个选项来解决C a0，即使用可用的上下文C a0。当调用 f 时，它会被传递一个隐式参数，其中包含 C a0 的字典（即 a0 类型的 f）。

因此，现在 GHC 有两个可行的选择：使用 C a0 上下文（即使用隐式参数）解决 C a0，或求助于全局 instance C a。第一个更具体，因为它只适用于 a0 而不是任何类型 a，所以它被认为是 "best"，并被选中。

上下文中的约束如何改变 Haskell 中的实例解析

How constraints in the context change instance resolution in Haskell

haskell

typeclass