Haskell GHC:与 N 个构造函数匹配的模式的时间复杂度是多少? [英] Haskell GHC: what is the time complexity of a pattern match with N constructors?

问题描述

假设我们有以下 Haskell:

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) 线性搜索，类似

(1) Linear search, something like

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

(2) 二进制搜索，这在这个特定任务中是明智的:在集合 {TO...T1023<中搜索 t.tag/代码>}.但是，如果模式匹配通常具有许多其他功能和概括，则可能无法使用.

(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.

toInt中t的模式匹配，用GHC编译，使用什么算法，用N表示的时间复杂度是多少?

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.

不幸的是，我无法找到对此的最新引用，尽管 this页面提到了Cmm级switch语句作为跳转表的实现，以及这个旧的标签设计文档以Bool上的case为例，生成了一个跳转表.

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