Haskell GHC : what is the time complexity of a pattern match with N constructors?

Question

假设我们有以下 Haskell:

data T = T0 | T1 | T2 | ... | TN

toInt :: T -> Int
toInt t = case t of
  T0 -> 0
  T1 -> 1
  T2 -> 2
  ...
  TN -> N

这里使用什么算法来执行模式匹配？我看到两个选项:

(1) 线性搜索，类似

if      (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...

(2) 二分搜索，这在这个特定任务中是明智的:搜索 t.tag在集合中 { TO ... T1023 }。但是，如果模式匹配通常具有许多其他功能和概括，则可能不会使用它。

使用 GHC 编译，使用什么算法，时间复杂度是多少，以 N 表示，用于 t 上的模式匹配在 toInt ?

Answer 1

使用跳转表，使模式匹配成为恒定时间操作。

不幸的是，我无法找到最新的引用，尽管 this page提到Cmm级别的实现switch作为跳转表的语句和 this old tagging design document使用 case在 Bool例如，生成一个跳转表。