title: Haskell GHC: what is the time complexity of a pattern match with N constructors?
body: <p>Let's say we have the following Haskell:</p>
  
  <pre><code>data T = T0 | T1 | T2 | ... | TN
  
  toInt :: T -&gt; Int
  toInt t = case t of
    T0 -&gt; 0
    T1 -&gt; 1
    T2 -&gt; 2
    ...
    TN -&gt; N
  </code></pre>
  
  <p>What algorithm is used to perform the pattern match here?  I see two options:</p>
  
  <p>(1) Linear search, something like</p>
  
  <pre><code>if      (t.tag == T0) { ... }
  else if (t.tag == T1) { ... }
  else ...
  </code></pre>
  
  <p>(2) Binary search, which would be sensible in this specific task: searching for <code>t.tag</code> in the set {<code>TO</code>...<code>T1023</code>}.  However, where pattern matching in general has many other capabilities and generalizations, this may not be used.</p>
  
  <p>Compiling with GHC, what algorithm is used, and what is the time complexity in terms of N, for pattern matching on <code>t</code> in <code>toInt</code>?</p>