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进行编译,使用什么算法,对于模式匹配,使用N的时间复杂度t是toInt多少？

Answer 1

使用跳转表,使模式匹配为恒定时间操作.

不幸的是,我无法找到了最新的引用这一点,虽然此页提到的CMM-一级执行switch语句跳转表,和这个老标签设计文档使用case上Bool作为一个例子,产生跳转表.