Bifunctor 实例定义上的类型签名不匹配

Question

我正在通过阅读 Haskell Programming from First Principles, Allen & Moronuki 这本书来了解 Haskell。

在关于 Monad T运行sformers、Functor 和 Applicative 组合的章节的练习中，它要求 reader 为以下类型编写 Bifunctor 实例

data SemiDrei a b c = SemiDrei a

我的第一次尝试（编译）是

instance Bifunctor (SemiDrei a) where
    bimap f g (SemiDrei a) = SemiDrei a

但是，看着它，在我看来，我应该可以写 bimap f g = id 因为最后一个参数没有改变或写 bimap f g x = x。两者都给了我编译错误，我希望有人能向我解释为什么我不能用这些较短的替代方案来表达 bimap，即为什么我必须指定 (SemiDrei a).

我运行在 Haskell 8.6.5（如果相关）

尝试：id

instance Bifunctor (SemiDrei a) where
    bimap f g = id

-- compile error message:
• Couldn't match type ‘a1’ with ‘b’
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  ‘b’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  Expected type: SemiDrei a a1 c -> SemiDrei a b d
    Actual type: SemiDrei a b d -> SemiDrei a b d
• In the expression: id
  In an equation for ‘bimap’: bimap f g = id
  In the instance declaration for ‘Bifunctor (SemiDrei a)’
• Relevant bindings include
    f :: a1 -> b (bound at src/Main.hs:69:11)
    bimap :: (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
      (bound at src/Main.hs:69:5)
   |
69 |     bimap f g = id
   |                 ^^

尝试：f g x = x

instance Bifunctor (SemiDrei a) where
    bimap f g x = x

-- compile error message:
• Couldn't match type ‘a1’ with ‘b’
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  ‘b’ is a rigid type variable bound by
    the type signature for:
      bimap :: forall a1 b c d.
               (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
    at src/Main.hs:69:5-9
  Expected type: SemiDrei a b d
    Actual type: SemiDrei a a1 c
• In the expression: x
  In an equation for ‘bimap’: bimap f g x = x
  In the instance declaration for ‘Bifunctor (SemiDrei a)’
• Relevant bindings include
    x :: SemiDrei a a1 c (bound at src/Main.hs:69:15)
    f :: a1 -> b (bound at src/Main.hs:69:11)
    bimap :: (a1 -> b) -> (c -> d) -> SemiDrei a a1 c -> SemiDrei a b d
      (bound at src/Main.hs:69:5)
   |
69 |     bimap f g x = x
   |                   ^

Answer 1

关键在于 bimap 的类型签名：

bimap :: Bifunctor p => (a -> b) -> (c -> d) -> p a c -> p b d

在这种特殊情况下，如果我们将 p 专门化为 SemiDrei a 并重命名类型变量以避免与 a 混淆，我们得到：

bimap :: (b -> c) -> (d -> e) -> SemiDrei a b d -> SemiDrei a c e

因此，当您尝试执行此操作时：

bimap f g = ...

函数 f 和 g 是完全任意的，不仅在它们的实现上，而且在它们的输入和 return 类型上也是如此。 f 的类型为 b -> c，其中 b 和 c 可以是任何类型——与 g 类似。您给出的定义必须绝对适用于调用者提供的任何类型和函数 - 这就是（参数）多态的含义。

如果我们现在用这些术语查看您的三个定义，我们就可以解开明显的谜团：

第一个：

bimap f g (SemiDrei a) = SemiDrei a

如您所见，这完全没问题。 SemiDrei a 的类型为 SemiDrei a b c，其中仅指定了 a。这意味着它可以采用任何类型，例如 SemiDrei a Int String、SemiDrei [Bool] (Char, [Double]) 或其他任何类型。 SemiDrei a 本身是多态的，它可以是任何兼容的类型。这意味着它可以作为上述 bimap.

签名中的 SemiDrei a b c 和 SemiDrei a c e

与您的其他尝试对比：

bimap f g = id

这里的问题是，id 虽然是多态的，但多态性不足以 用于此目的。它的类型是 a -> a（对于任何 a），特别是可以特化到 SemiDrei a b c -> SemiDrei a b c。但它不可能根据需要专门化为类型 SemiDrei a b d -> SemiDrei a c e，因为 b、c、d 和 e 通常是完全不同的类型.回想一下，bimap 的 caller 可以选择类型 - 他们可以轻松选择函数 f 和 g，其中 b例如，c 和 c 是不同的类型，因此 id 无法将 SemiDrei a b d 转换为 SemiDrei a c e，因为它们是不同的类型。

在这个阶段，您可能会反对值 SemiDrei a 可以是所有此类类型的值。这是完全正确的，但它与类型推断无关——编译器只关心类型，而不关心它们中可能包含什么值。它必须考虑到不同的类型具有完全不同的、不相交的值。而且，比方说，SemiDrei a Int String 和 SemiDrei a Bool Char 实际上是不同的类型。同样，编译器不知道 Int 等实际上没有被该类型的任何值使用。这确实正是为什么在实践中使用这种 "phantom types"（出现在类型定义中但不出现在它们的任何数据构造函数中的类型）的原因 - 允许编译器能够按类型区分它们，即使运行-时间表示可能完全等价。

至于您的第三次尝试，bimap f g x = x，这与上一次完全相同 - 它限制 bimap f g 使其输出类型与其输入相同。（实际上它完全等同于 bimap f g = id。）

所以重要的一点是，在类型检查阶段，编译器只关心类型 - 具有不同名称的两种类型被（并且必须）认为是完全不同的，即使它们可能是等价的值可以嵌入到两者中。

Answer 2

这在一个更简单的案例中显示了相同的问题：

data T a = K

foo :: T a -> T b
foo K = K  -- type checks

bar :: T a -> T b
bar x = x  -- type error

-- bar = id would also be a type error, for the same reason

这里的问题是 foo 值中的两个 K 隐藏了它们的类型参数。更准确的定义是

-- pseudo code
foo (K @a) = K @b

在这里你可以看到隐式类型参数发生了变化。当我们在 foo 的定义中写入 K 时，GHC 会自动为我们推断这些类型参数。因为它们是隐式的，所以它们 看起来 就好像它们是相同的 K，但对于类型检查器来说它们不是。

相反，当我们在 bar 的定义中使用 x 时，没有要推断的隐式类型参数。我们有 x :: T a，仅此而已。我们不能使用 x 并声称具有不同的类型 T b.

最后，请注意，使用 "safe coercions" 我们可以执行直觉上正确的类型 id，将一个 K（在一种类型中）转换为另一种 K 其他类型：

import Data.Coerce

baz :: T a -> T b
baz = coerce

这是否更好是有争议的。对于简单的情况，模式匹配比 coerce 更容易理解，因为后者可以执行大量（安全的）强制转换，可能让 reader 猜测类型级别实际发生的事情.

Answer 3

事实上，最后一个参数并没有改变：它的类型发生了变化。输入为 SemiDrei a x y，输出为 SemiDrei a p q，其中 f :: x -> p 和 g :: y -> q。

这意味着你必须解构原始类型的值并重建新类型的值，这就是你在原始实现中所做的。

但您的直觉是正确的：这两个值在内存中的表示确实相同。而GHC可以推断出这个事实，当它这样做时，它会自动为你解决一个Coercible约束，这意味着你可以使用coerce函数将一个转换为另一个：

 bimap _ _ = coerce

Bifunctor 实例定义上的类型签名不匹配

Type Signature Mismatch on Bifunctor instance definition

haskell

types

bifunctor