Haskell GHC:与N个构造函数匹配的模式的时间复杂度是多少? [英] Haskell GHC: what is the time complexity of a pattern match with N constructors?
问题描述
假设我们有以下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
}中的code>
使用GHC编译,使用什么算法,以及什么是时间复杂度对于 t
在 toInt
?
使用跳转表,使模式匹配成为恒定时间操作。
为此找到最新的引用,但此网页提及实施的Cmm级开关
语句作为跳转表,以及这个旧的标记设计文档在 Bool
上使用 case
作为示例,生成跳转表。 p>
Let's say we have the following Haskell:
data T = T0 | T1 | T2 | ... | TN
toInt :: T -> Int
toInt t = case t of
T0 -> 0
T1 -> 1
T2 -> 2
...
TN -> N
What algorithm is used to perform the pattern match here? I see two options:
(1) Linear search, something like
if (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...
(2) Binary search, which would be sensible in this specific task: searching for t.tag
in the set {TO
...T1023
}. However, where pattern matching in general has many other capabilities and generalizations, this may not be used.
Compiling with GHC, what algorithm is used, and what is the time complexity in terms of N, for pattern matching on t
in toInt
?
A jump table is used, making the pattern-match a constant time operation.
Unfortunately I'm unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch
statements as jump tables, and this old tagging design document uses a case
on a Bool
as an example, producing a jump table.
这篇关于Haskell GHC:与N个构造函数匹配的模式的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!