双功能实例定义中的类型特征不匹配

Question

我正在通过“Haskell编程从第一性原理，Allen & Moronuki”一书学习Haskell。

在关于Monad变形金刚、函子和应用组合一章的练习中，它要求读者为下列类型编写双函子实例

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=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

事实上，最后一个论点并没有得到不变的结果:它的类型发生了变化。输入是SemiDrei a x y，输出是SemiDrei a p q，其中f :: x -> p和g :: y -> q。

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

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

 bimap _ _ = coerce

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

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

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

在这里，您可以看到隐式类型参数发生了更改。当我们在K的定义中编写foo时，GHC会自动为我们推断这些类型参数。由于它们是隐式的，它们看起来好像是相同的Ks，但是它们不是类型检查器。

相反，当我们在x的定义中使用bar时，不存在可以推断的隐式类型参数。我们有那个x :: T a，仅此而已。我们不能使用x和声称有不同类型的T b。

最后，请注意，使用“安全矫顽力子”，我们可以执行直观正确的id类型，将一种K (一种类型)转换为另一种类型的另一种K：

import Data.Coerce

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

这是否更好是值得商榷的。对于简单的情况，模式匹配可能比coerce更容易理解，因为后者可以执行大量(安全的)矫顽器，可能让读者猜测类型级别上实际发生了什么。

Answer 3

这方面的关键是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函数是完全任意的，不仅在它们的实现中，而且在它们的输入和返回类型上。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本身是多态的，它可以是任何兼容的类型。这意味着，特别是在上面的SemiDrei a b c签名中，它可以同时充当bimap和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的调用方可以选择类型是什么--例如，他们可以很容易地选择函数f和g，其中b和c是不同的类型，然后id就无法将SemiDrei a b d带到SemiDrei a c e，因为它们是不同的类型。

在此阶段，您可能会反对SemiDrei a值可以是所有此类类型的值。这是完全正确的，但与类型推断无关-编译器只关心类型，而不关心它们中的值。它必须考虑到不同的类型有完全不同的，不相交的，价值。比如说，SemiDrei a Int String和SemiDrei a Bool Char实际上是不同的类型。同样，编译器不知道类型的任何值实际上都没有使用Int等。这就是为什么在实践中使用这种“幻影类型”(出现在类型定义中但没有出现在它们的任何数据构造函数中的类型)--允许编译器能够根据类型区分它们，即使运行时表示可能完全等价。

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

因此，重要的一点是，在类型检查阶段，编译器只关心类型--两种不同名称的类型被(而且必须)考虑完全不同，尽管两者都可以嵌入等效的值。