当范围内有多个字典时，GHC 选择哪本字典？

Question

考虑以下示例：

import Data.Constraint

class Bar a where
  bar :: a -> a

foo :: (Bar a) => Dict (Bar a) -> a -> a
foo Dict = bar

在 foo 中选择 Bar 实例时，GHC 有两种选择要使用的字典：它可以使用来自 foo 上的 Bar a 约束的字典，或者它可以使用运行时 Dict 来获取字典。有关字典对应于不同个实例的示例，请参见。

GHC 使用哪个字典，为什么 "correct" 选择它？

Answer 1

它只是选择了一个。这不是正确的选择；这是一个非常有名的疣。您可能会以这种方式导致崩溃，因此这是一种非常糟糕的情况。这是一个仅使用 GADTs 的简短示例，它演示了可以在范围内同时拥有两个 不同的 实例：

-- file Class.hs
{-# LANGUAGE GADTs #-}
module Class where

data Dict a where
  Dict :: C a => Dict a

class C a where
  test :: a -> Bool

-- file A.hs
module A where

import Class

instance C Int where
  test _ = True

v :: Dict Int
v = Dict

-- file B.hs
module B where

import Class

instance C Int where
  test _ = False

f :: Dict Int -> Bool
f Dict = test (0 :: Int)

-- file Main.hs
import TestA
import TestB

main = print (f v)

你会发现 Main.hs 编译得很好，甚至可以运行。它使用 GHC 7.10.1 在我的机器上打印 True，但这不是一个稳定的结果。将其变成崩溃留给 reader.

Answer 2

这是一个测试：

{-# LANGUAGE FlexibleInstances, OverlappingInstances, IncoherentInstances #-}
import Data.Constraint

class    C a    where foo :: a -> String
instance C [a]  where foo _ = "[a]"
instance C [()] where foo _ = "[()]"

aDict :: Dict (C [a])
aDict = Dict

bDict :: Dict (C [()])
bDict = Dict

bar1 :: String
bar1 = case (bDict, aDict :: Dict (C [()])) of
         (Dict,Dict) -> foo [()]              -- output: "[a]"

bar2 :: String
bar2 = case (aDict :: Dict (C [()]), bDict) of
         (Dict,Dict) -> foo [()]              -- output: "[()]"

上面的 GHC 碰巧使用了 "last" 字典，它被引入了范围。不过我不会依赖这个。

如果您仅限于重叠实例，那么您将无法将同一类型的两个不同词典纳入范围（据我所知), 一切都应该没问题，因为字典的选择变得无关紧要了。

但是，不连贯的实例 是另一种野兽，因为它们允许您提交一个通用实例，然后在具有更具体实例的类型中使用它。这使得很难理解将使用哪个实例。

简而言之，不连贯的实例是邪恶的。

更新：我运行做了一些进一步的测试。在单独的模块中仅使用重叠实例和孤立实例，您仍然可以获得相同类型的两个不同字典。所以，我们需要更多的警告。 :-(

Answer 3

GHC随便选了一个，这个是正确的选择。相同约束的任何两个字典都应该是相等的。

OverlappingInstances和IncoherentInstances的破坏力基本相当；它们都在设计上失去了实例一致性（你的程序中的任何两个相等的约束都被同一个字典满足）。 OverlappingInstances 使您能够根据具体情况确定将使用哪些实例，但是当您到达将 Dicts 作为第一个 class 值传递的地步时，这就没那么有用了，很快。当我认为重叠实例在扩展上等效时（例如，对于像 Int 这样的特定类型更有效但其他方面相同的实现），我只会考虑使用 OverlappingInstances，但即便如此，如果我足够关心性能来编写专门的实现，是吗？如果它在可以使用的时候没有被使用，这不是性能错误吗？

简而言之，如果您使用 OverlappingInstances，您将放弃在此处询问select编辑哪个字典的权利。

现在确实可以在没有 OverlappingInstances 的情况下打破实例一致性。事实上，除了 FlexibleInstances 之外，你可以在没有孤儿和没有任何扩展的情况下做到这一点（可以说问题是 "orphan" 的定义在启用 FlexibleInstances 时是错误的）。这是一个长期存在的 GHC 错误，尚未修复，部分原因是 (a) 据任何人所知，它实际上不会直接导致崩溃，并且 (b) 可能有很多程序实际上依赖于在程序的不同部分为同一约束设置多个实例，这可能很难避免。

回到主题，原则上 GHC 可以 select 任何它可用的字典来满足约束是很重要的，因为即使它们应该是相等的，GHC 可能有更多的静态有关其中一些的信息比其他人更多。你的例子有点太简单了，无法说明，但想象一下你传递了一个参数给 bar;一般来说，GHC 对通过 Dict 传入的字典一无所知，因此它必须将此视为对未知函数的调用，但你在特定类型 T 中调用了 foo在范围内有一个 Bar T 实例，那么 GHC 会知道 Bar a 约束字典中的 bar 是 T 的 bar 并且可以生成调用已知函数，并可能内联 T 的 bar 并因此进行更多优化。

实际上，GHC 目前并没有这么聪明，它只是使用可用的最里面的字典。始终使用最外层的字典可能已经更好了。但是像这样有多个可用词典的情况并不常见，所以我们没有好的基准测试。

当范围内有多个字典时，GHC 选择哪本字典？

Which dictionary does GHC choose when more than one is in scope?

haskell

ghc