GHC在多个范围内选择哪个词典？

Question

请考虑以下示例:

import Data.Constraint

class Bar a where
  bar :: a -> a

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

在选择Bar实例时,GHC有两种选择foo:字典可以使用Bar a约束中的字典foo,或者它可以使用运行时Dict来获取字典.有关字典对应不同实例的示例,请参阅此问题.

GHC使用哪种词典,为什么它是"正确的"选择？

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编译得很好,甚至可以运行.它True使用GHC 7.10.1在我的机器上打印,但这不是一个稳定的结果.把它变成一个崩溃留给读者.

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碰巧使用了被引入范围的"最后"字典.不过,我不会依赖于此.

如果你只限于重叠实例,那么你将无法为同一类型引入两个不同的词典(据我所知),一切都应该没问题,因为词典的选择变得无关紧要.

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

简而言之,语无伦次的实例是邪恶的.

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

Answer 3

GHC选择一个,这是正确的选择.相同约束的任何两个字典应该是相等的.

重叠实体和非相干实体在破坏力方面基本相同; 它们都会因设计而失去实例连贯性(程序中任何两个相同的约束都被同一个字典所满足).OverlappingInstances为您提供了更多的能力,可以根据具体情况确定哪些实例将被使用,但是当您将Dicts作为第一类值传递时,这并不是很有用.我只考虑使用OverlappingInstances,当我认为重叠实例在扩展上是等价的(例如,对于像Int这样的特定类型的更高效但是相同的实现),但即便如此,如果我足够关注性能来编写该专用实现,那么如果它没有被使用,它是一个性能错误？

简而言之,如果您使用OverlappingInstances,则放弃向此处询问将选择哪个字典的权利.

现在你可以在不使用OverlappingInstances的情况下破坏实例一致性.实际上你可以在没有孤儿的情况下完成它,除了灵活实例之外没有任何扩展(可以说,当启用FlexibleInstances时,"孤儿"的定义是错误的).这是一个非常长期存在的GHC错误,部分原因尚未解决,因为(a)它实际上不会直接导致任何人似乎知道的崩溃,并且(b)可能有很多程序实际上,它依赖于在程序的不同部分中为同一约束设置多个实例,这可能很难避免.

回到主题,原则上重要的是GHC可以选择它可用于满足约束的任何字典,因为即使它们应该是相等的,GHC可能比其他字段有更多关于其中一些的静态信息.你的例子有点过于简单而无法说明,但想象你通过了一个论证bar; 一般情况下,GHC对通过的字典没有任何了解,Dict所以它必须将其视为对未知函数的调用,但是你调用foo了一个特定的类型T,其Bar T范围内有一个实例,那么GHC会知道bar从Bar a约束字典是T的bar,可能产生一个已知函数的调用,并有可能内联T的bar,做更多的优化结果.

在实践中,GHC目前并不聪明,它只使用最里面的字典.总是使用最外层的字典可能已经更好了.但是这样的情况下,有多个词典可供使用并不常见,所以我们没有很好的基准测试.