开放世界假设有什么好处？

Question

作为一个（有点人为的）例子，假设我想使用泛型来确定一个类型何时无人居住（通过非底值）。我可以顺利到达那里的大部分路段：

class Absurd a where
    absurd :: a -> b
    default absurd :: (Generic a, GAbsurd (Rep a)) => a -> b
    absurd = gabsurd . from
class GAbsurd f where
    gabsurd :: f p -> b
instance GAbsurd f => GAbsurd (M1 i c f) where
    gabsurd (M1 x) = gabsurd x
instance Absurd c => GAbsurd (K1 i c) where
    gabsurd (K1 x) = absurd x
instance GAbsurd V1 where
    gabsurd = \case
instance (GAbsurd a, GAbsurd b) => GAbsurd (a :+: b) where
    gabsurd (L1 x) = gabsurd x
    gabsurd (R1 x) = gabsurd x

当我需要为 :*: 定义一个实例时，问题就来了。实现 GAbsurd (a :*: b) 只需要 GAbsurd a 或 GAbsurd b 之一，但是我能做的最好的是两者都需要，这太强了。例如：

data Void
data X = X Char Void

显然 X 是一个“荒谬”类型，但这不能推断，因为虽然 Void 是荒谬的，但 Char 不是，所以约束 (Absurd Char, Absurd Void) 无法解决

我想做的是像这样使用某种“约束析取”：

instance (GAbsurd a || GAbsurd b) => GAbsurd (a :*: b) where
    gabsurd (x :*: y) = case eitherConstraint of
        LeftC  -> gabsurd x
        RightC -> gabsurd y

然而，在开放世界假设下，that's not possible。事实上，Data.Boring 中的代码（也包含 Absurd）完全忽略了这个问题：

There are two reasonable instances for GAbsurd (f :*: g), so we define neither

所以这让我想到了一个问题：为什么开放世界假设如此重要？我最好的猜测是它与孤儿实例有关，但即使那样也应该GHC 没有所有导入模块的列表吗？

Answer 1

我不确定关键问题是孤立实例和模块。

我认为主要问题是，面对约束分离，保持实例定义的一致性和编译效率出乎意料地困难。问题是您想象的语法中假设的 eitherConstraint 不能在编译时简单地在本地解决。例如，考虑函数：

foo :: (GAbsurd a) => GAbsurd (a :*: b)
foo = gabsurd

bar :: (GAbsurd b) => GAbsurd (a :*: b)
bar = gabsurd

这两个都是type-correct。在每种情况下，都需要一个 GAbsurd (a :*: b) 实例，并且可以通过 GAbsurd a 或 GAbsurd b 的析取来提供一个实例。但是，实际实现这些功能的明显 compile-time 本地解决方案，第一个使用 gabsurd (a :*: b) = gabsurd a，第二个使用 gabsurd (a :*: b) = gabsurd b，导致不连贯。对于这个特定的例子来说这不是问题，但是如果这些是 Ord 实例并且我们使用一个多态函数将对象插入 Set 和另一个多态函数在 Set 中查找对象]]，如果他们最终为同一类型使用两个不同的 Ord 实例，我们可能会遇到真正的问题。

为了保持连贯性，我们基本上必须携带大量额外的类型信息来解决选择实例时的分离问题。而且，我们可能不得不在传递该信息和在运行时评估它之间做出选择，或者为即使是非常微不足道的程序生成指数级数量的专用实例。

开放世界假设有什么好处？

What good is the open world assumption?

generics

haskell

constraints

ghc