为什么实例仅与头部相匹配？

Question

我将首先介绍一个具体的问题(StackOverflow这样的人).假设您定义一个简单类型

data T a = T a

这种类型是Functor,Applicative和Monad.忽略自动派生,要获得那些实例,你必须编写它们中的每一个,即使Monad暗示Applicative,这意味着Functor.更重要的是,我可以定义一个这样的类

class Wrapper f where
    wrap   :: a -> f a
    unwrap :: f a -> a

这是一个非常强大的条件,它绝对暗示Monad,但我不能写

instance Wrapper f => Monad f where
    return = wrap
    fa >>= f = f $ unwrap fa

因为出于某种原因,这意味着"一切都是Monad(每一个f),只有它是一个Wrapper",而不是"一切Wrapper都是一个Monad".

同样,您无法定义Monad a => Applicative a和Applicative a => Functor a实例.

你不能做的另一件事(它可能只是相关的,我真的不知道)是有一个类是另一个类的超类,并提供子类的默认实现.当然,它很棒class Applicative a => Monad a,但是Applicative在我定义实例之前我仍然需要定义实例并不是很好Monad.

这不是咆哮.我写了很多,因为否则这很快会被标记为"过于宽泛"或"不清楚".问题归结为标题.我知道(至少我很确定)这有一些理论上的原因,所以我想知道这里有什么好处.

作为一个子问题,我想问一下是否有可行的替代方案仍能保留所有(或大部分)优势,但允许我写的内容.

另外:我怀疑其中一个答案可能是"如果我的类型是a Wrapper,但我不想使用Monad那个暗示的实例怎么办？".对此我要问,为什么编译器不能选择最具体的一个？如果有instance Monad MyType,肯定比它更具体instance Wrapper a => Monad a.

Answer 1

这里有很多问题.但是,让我们一次拿一个.

第一:为什么编译器在选择使用哪个实例时不会查看实例上下文？这是为了保持实例搜索的有效性.如果您要求编译器仅考虑其实例头满足的实例,那么您最终需要编译器在所有可能的实例中进行反向跟踪搜索,此时您已实现了90%的Prolog.另一方面,如果您采取立场(如Haskell所做的那样),在选择要使用的实例时只查看实例头,然后简单地强制实例上下文,则没有回溯:每时每刻都只有你可以做出的一个选择.

下一篇:为什么不能让一个类成为另一个类的超类,并提供子类的默认实现？这种限制没有根本原因,因此GHC提供此功能作为扩展.你可以写这样的东西:

{-# LANGUAGE DefaultSignatures #-}
class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

    default pure :: Monad f => a -> f a
    default (<*>) :: Monad f => f (a -> b) -> f a -> f b
    pure = return
    (<*>) = ap

然后,一旦你提供了一个instance Monad M where ...,你可以简单地写一个instance Applicative M没有where条款,并让它Just Work.我真的不知道为什么在标准库中没有这样做.

最后:为什么编译器不能允许多个实例,只选择最具体的实例？这个问题的答案有点是前两个问题的结合:有很好的基本原因,这个问题不能很好地运作,但是GHC提供了一个扩展功能.这种方法效果不佳的根本原因是,在运行时之前无法知道给定值的最具体的实例.GHC对此的回答是,对于多态值,选择与可用的完整多态性兼容的最具特异性的值.如果以后那件事情变得单一,那么,对你来说太糟糕了.其结果是一些函数可能对一个实例的某些数据进行操作,而其他函数可能对另一个实例的相同数据进行操作; 这可能导致非常微妙的错误.如果经过所有这些讨论,你仍然认为这是一个好主意,并且拒绝从别人的错误中吸取教训,你就可以开启IncoherentInstances.

我认为这涵盖了所有问题.

Answer 2

一致性和单独编译。

如果我们有两个实例，它们的头都匹配，但具有不同的约束，请说：

-- File: Foo.hs

instance Monad m => Applicative m
instance            Applicative Foo

那么，这要么是为 生成Applicative实例的有效代码，要么是为 生成两个不同实例的Foo错误。是哪一个取决于 是否存在 monad 实例。这是一个问题，因为很难保证了解是否ApplicativeFooFooMonad Foo编译器在编译此模块时能够了解有关是否成立的知识。

不同的模块（例如Bar.hs）可能会生成Monad的实例Foo。如果Foo.hs不导入该模块（即使是间接导入），那么编译器如何知道？更糟糕的是，我们可以通过更改稍后是否包含来更改这是错误还是有效定义Bar.hs稍后是否包含在最终程序中

为此，我们需要知道最终编译的程序中存在的所有实例在每个模块中都是可见的，这得出的结论是每个模块都是每个其他模块的依赖项，无论该模块是否实际导入其他。您必须在要求整个程序分析的道路上走很远才能支持这样的系统，这使得分发预编译库变得困难甚至不可能。

避免这种情况的唯一方法是永远不要让 GHC 根据负面信息做出决策。您不能根据非实例来选择实例另一个实例

这意味着实例解析时必须忽略实例上的约束。无论约束是否成立，都需要选择一个实例；如果这留下了多个可能适用的实例，那么您将需要负面信息（即除其中一个之外的所有实例都需要不成立的约束）才能接受代码有效。

如果您只有一个实例，甚至是候选实例，并且看不到其约束的证明，则只需将约束传递到使用该实例的位置即可接受代码（我们可以依靠将此信息传递给其他实例）模块，因为他们必须导入这个模块，即使只是间接导入）；如果这些位置也看不到所需的实例，那么它们将生成有关不满足约束的适当错误。

因此，通过忽略约束，我们确保编译器即使只知道它导入的其他模块（传递性地）也可以对实例做出正确的决策；它不必了解每个其他模块中定义的所有内容才能知道哪些约束不成立。