Haskell GHC: qual è la complessità temporale di un pattern che corrisponde a N costruttori?

Question

Diciamo che abbiamo la seguente Haskell:

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

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

Che algoritmo viene utilizzato per eseguire il pattern match qui? Vedo due opzioni:

(1) ricerca lineare, qualcosa come

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

(2) La ricerca binaria, che sarebbe ragionevole in questo specifico compito: cercare t.tag nel set {TO ... T1023}. Tuttavia, laddove la corrispondenza del modello in generale ha molte altre capacità e generalizzazioni, questa non può essere utilizzata.

Compilando con GHC, quale algoritmo viene utilizzato e qual è la complessità temporale in termini di N, per la corrispondenza del modello su t in toInt?

Answer 1

Viene utilizzata una tabella di salto che fa corrispondere il modello a un'operazione a tempo costante.

Purtroppo non riesco a trovare una citazione up-to-date per questo, anche se this page menzioni l'attuazione di Cmm livello switch affermazioni come tabelle di salto, e this old tagging design document utilizza un case su un Bool come esempio, la produzione di un Salta la tabella.