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屋！