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的建议,我添加了第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#,以及为什么dataToTag#在GHC中实施了9个使用构造函数的特定截止.

Answer 1

等式比较EType为O(1),因为case构造是O(1).

构造函数可能有也可能没有整数标记.有几种低级别的表示选择,因此Core生成的所有内容都适用.也就是说,你总是可以为构造函数创建一个整数标记,这就是我编写Haskell编译器时通常实现派生比较的方式.

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