Haskell GHC: quelle est la complexité temporelle d'une correspondance de motif avec N constructeurs?

Question

Disons que nous avons les éléments suivants Haskell:

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

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

Quel algorithme est utilisé pour effectuer la mise en correspondance du modèle ici? Je vois deux options:

(1) la recherche Linéaire, quelque chose comme

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

(2) la recherche Binaire, ce qui serait raisonnable dans cette tâche spécifique: recherche d' t.tag dans l'ensemble {TO...T1023}. Toutefois, lorsque le pattern matching en général a de nombreuses autres fonctionnalités et des généralisations, ce ne peut pas être utilisé.

La compilation de GHC, quel algorithme est utilisé, et quel est le temps de la complexité en termes de N, pour un patron sur t en toInt?

Answer 1

Un saut de table est utilisé, ce qui rend le modèle de correspondre à une constante de temps de l'opération.

Malheureusement, je suis incapable de trouver un up-to-date de la citation pour ce, bien que cette page mentionne la mise en œuvre de la Cmm niveau switch états sauter les tables, et ce vieux balisage de document de conception utilise un case sur Bool comme un exemple, la production d'un saut de la table.