GHC 的自动派生"Eq"实例真的是 *O(N)* 吗？

Question

我刚刚在学习阅读GHC Core时注意到枚举样式数据类型（如）的自动派生Eq实例

data EType = ETypeA | ETypeB | ETypeC | ETypeD
           | ETypeE | ETypeF | ETypeG | ETypeH
           deriving (Eq)

当查看GHC的核心表示：时，似乎转化为类似O（N）的查找

$fEqEType_$c== =
   (a_ahZ :: EType) (b_ai0 :: EType) ->
    case a_ahZ of _ {
      ETypeA ->
        case b_ai0 of _ {
          ETypeA -> True;
          ETypeB -> False;
          ETypeC -> False;
          ETypeD -> False;
          ETypeE -> False;
          ETypeF -> False;
          ETypeG -> False;
          ETypeH -> False
        };
      ETypeB -> case b_ai0 of _ {__DEFAULT -> False; ETypeB -> True};
      ETypeC -> case b_ai0 of _ {__DEFAULT -> False; ETypeC -> True};
      ETypeD -> case b_ai0 of _ {__DEFAULT -> False; ETypeD -> True};
      ETypeE -> case b_ai0 of _ {__DEFAULT -> False; ETypeE -> True};
      ETypeF -> case b_ai0 of _ {__DEFAULT -> False; ETypeF -> True};
      ETypeG -> case b_ai0 of _ {__DEFAULT -> False; ETypeG -> True};
      ETypeH -> case b_ai0 of _ {__DEFAULT -> False; ETypeH -> True}
    }

我是否误解了GHC核心输出？代数数据类型不应该为每个构造函数提供一个整数id吗？然后可以在O（1）中直接进行比较？同样，为什么ETypeA的第一个大小写子句不像其他子句那样使用__DEFAULT？

更新：

根据Simon Marlow的建议，我添加了第九个构造函数ETypeI，然后GHC切换到使用dataToOtag#:

$fEqEType_$c/= =
   (a_ahS :: EType) (b_ahT :: EType) ->
    case dataToTag# @ EType a_ahS of a#_ahQ {
      __DEFAULT ->
        case dataToTag# @ EType b_ahT of b#_ahR {
          __DEFAULT ->
            case ==# a#_ahQ b#_ahR of _ {
              False -> True; True -> False
            }
        }
    }

对我来说，这增加了一个问题，即GHC核心的case和使用dataToTag#之间的权衡是什么，以及为什么在GHC中实现了使用dataToTag#的9个构造函数的特定截止。

Answer 1

EType的相等比较是O（1），因为case构造是O（2）。

构造函数可能有整数标记，也可能没有。有几个低级别的表示选项，因此Core生成的适用于所有这些选项。也就是说，您总是可以为构造函数创建一个整数标记，这就是我在编写Haskell编译器时通常实现派生比较的方式。

我不知道为什么ETypeA会得到不同的治疗。看起来像虫子。