haskell - 上下文中的约束如何改变 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

最后两行不是我想要的。对于第三行，编译器(或运行时？)在为列表实例运行 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，所以没有单个仅凭手头的信息就可以将实例选为“最终”实例。

但是，“重叠”编译指示指示 GHC 在足以解决约束的通用实例中选择单个最佳实例。事实上，这是我们对手头信息所能做的最好的事情:唯一合理的选择就是提出错误。

在这种情况下，要解决 C a0 我们需要选择三个实例之一，并且只有 实例 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 问题，或者求助于全局 实例C a。第一个更具体，因为它仅适用于 a0 而不是任何类型 a，因此它被认为是“最佳”并被选择。