Haskell GHC：具有 N 个构造函数的模式匹配的时间复杂度是多少？

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编译，在

t

中对

toInt

进行模式匹配，使用什么算法，时间复杂度是多少（N）？

Answer 1

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

不幸的是，我无法找到最新的引用，尽管本页提到了Cmm级

switch

语句作为跳转表的实现，并且这个旧的标记设计文档使用了

case 

以

Bool

为例，生成跳转表。