GHC的自动派生的‘Is’实例真的*O(N)*吗？

Question

我只是注意到，在尝试学习读取GHC核心时，枚举样式数据类型的自动派生Eq实例，如

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

在查看GHC的核心表示时，似乎将其转换为O(N)-like查找：

$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的第一个case子句不像其他子句那样使用__DEFAULT？

更新：

根据Simon的建议，我添加了第9个构造函数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中实现了对9个构造函数使用dataToTag#的特殊切断。

Answer 1

EType的相等比较是O(1)，因为case构造是O(1)。

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

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