为什么实例只匹配它们的头部？

Question

我将从介绍一个具体问题开始（像这样的 Whosebug 人员）。假设你定义了一个简单的类型

data T a = T a

这个类型是Functor、Applicative和Monad。忽略自动推导，要获得这些实例，您必须编写每个实例，即使 Monad 意味着 Applicative，这意味着 Functor。不仅如此，我还可以像这样定义 class

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

因为出于某种原因，这意味着 "everything is a Monad (every f), only if it's a Wrapper"，而不是 "everything that's a Wrapper is a Monad"。

同样，您不能定义 Monad a => Applicative a 和 Applicative a => Functor a 实例。

你不能做的另一件事（这只是可能相关，我真的不知道）是让一个 class 成为另一个的超级class，并提供默认值subclass 的执行。当然，class Applicative a => Monad a 很棒，但我仍然必须先定义 Applicative 实例才能定义 Monad 实例，这就没那么好了。

这不是咆哮。我写了很多，否则这很快就会被标记为 "too broad" 或 "unclear"。问题归结为标题。我知道（至少我很确定）这有一些理论上的原因，所以我想知道这里的好处到底是什么。

作为一个子问题，我想问一下是否有可行的替代方案仍然保留所有（或大部分）这些优势，但允许我写的内容。

补充：我怀疑答案之一可能与 "What if my type is a Wrapper, but I don't want to use the Monad instance that that implies?" 类似。对此我要问，为什么编译器不能只选择最具体的一个？如果有 instance Monad MyType，肯定比 instance Wrapper a => Monad a.

更具体

Answer 1

这里有很多问题。但是让我们一次一个地接受它们。

首先：为什么编译器在选择要使用的实例时不查看实例上下文？这是为了保持实例搜索的效率。如果你要求编译器只考虑其实例头被满足的实例，你基本上最终要求你的编译器在所有可能的实例中进行回溯搜索，此时你已经实现了 90% 的 Prolog。另一方面，如果您采取的立场（如 Haskell 所做的那样）在选择要使用的实例时只查看实例头，然后简单地执行实例上下文，则没有回溯：在每时每刻，你只能做出一个选择。

下一步：为什么不能让一个 class 成为另一个的超级class，并提供子class 的默认实现？此限制没有根本原因，因此 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 子句并使其正常工作。我真的不知道为什么标准库中没有这样做。

最后：为什么编译器不能允许很多实例而只选择最具体的一个？这个问题的答案是前两个的混合：有很好的根本原因这不能很好地工作，但是 GHC 提供了一个扩展来做到这一点。这不能很好地工作的根本原因是在运行时之前无法知道给定值的最具体实例。 GHC 对此的回答是，对于多态值，选择与可用的完整多态性兼容的最具体的值。如果以后那个东西被单态化了，好吧，对你来说太糟糕了。这样做的结果是，某些函数可能会在一个实例中对某些数据进行操作，而其他函数可能会在另一个实例中对相同的数据进行操作；这可能会导致非常微妙的错误。如果在讨论之后你仍然认为这是个好主意，并且拒绝从别人的错误中吸取教训，你可以打开 IncoherentInstances。

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

Answer 2

一致性和单独编译。

如果我们有两个头部都匹配但有不同约束的实例，比如：

-- File: Foo.hs

instance Monad m => Applicative m
instance            Applicative Foo

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

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

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

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

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

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

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

为什么实例只匹配它们的头部？

Why are instances matched only by their heads?

haskell

monads

typeclass

functor

applicative