假设我们有以下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相关?