Haskell GHC：N個のコンストラクタによるパターン一致の時間複雑度はどのくらいですか？

Question

のは、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）バイナリサーチのようなもの、：：私は2つのオプションが表示さ集合{TOにt.tag探しを... T1023}。しかし、パターンマッチングには他の多くの機能や一般化がありますが、これは使用できません。

のパターンマッチングのために、GHCでコンパイルするアルゴリズムと使用するアルゴリズムはどれくらいありますかtoInt？

Answer 1

ジャンプテーブルが使用され、パターン一致が一定の時間動作になります。 this pageは、ジャンプテーブルとしてswitch文のCmmレベルの実装に言及し、this old tagging design documentは生産、一例としてBoolにcaseを使用しているが

は、残念ながら、私は、このための最新の引用を見つけることができませんよジャンプテーブル。