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

Question

36

假设我们有以下Haskell代码：

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

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

这里用了什么算法来进行模式匹配？我看到有两种选择：

（1）线性搜索，类似如下代码： ```` for i in range(len(string)): if string[i:i+len(pattern)] == pattern: return i ````

（2）使用KMP算法。

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

(2) 二分查找，在这个特定的任务中是明智的选择：在集合{TO...T1023}中搜索t.tag。然而，一般情况下，模式匹配具有许多其他功能和推广，可能不会使用此方法。

使用GHC编译时，在toInt中对t进行模式匹配所使用的算法是什么？其时间复杂度如何与N相关？

- jameshfisher

2

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ehird · Accepted Answer

使用跳转表格（jump table），使模式匹配成为一个常数时间操作。

不幸的是，我无法找到最新的引用，尽管这个页面提到了在Cmm级别的switch语句实现中使用了跳转表格，而这个旧的标记设计文档使用了对Bool类型进行case操作的例子，生成了一个跳转表格。