title: Pattern matching on algebraic data types
body: <p>This is an open question but I never managed to find a solution that pleases me.</p>
  
  <p>Let's say I have this algebraic data type :</p>
  
  <pre><code>type t = A of int | B of float | C of string
  </code></pre>
  
  <p>Now, let's say I want to write a <code>compare</code> function - because I want to put my values in a <code>Map</code>, for example - I'd write it like this :</p>
  
  <pre><code>let compare t1 t2 =
    match t1, t2 with
      | A x, A y -&gt; compare x y
      | A _, _ -&gt; -1
      | _, A _ -&gt; 1
      | B x, B y -&gt; compare x y
      | B _, _ -&gt; -1
      | _, B _ -&gt; 1
      | C x, C y (* or _ *) -&gt; compare x y
  </code></pre>
  
  <p>Or I could write it like this :</p>
  
  <pre><code>let compare t1 t2 = 
    match t1, t2 with
      | A x, A y -&gt; compare x y
      | B y, B x -&gt; compare x y
      | C x, C y -&gt; compare x y
      | A _, _
      | B _, C _ -&gt; -1
      | _ -&gt; 1
  </code></pre>
  
  <p>If I'm not wrong, saying that <code>n</code> is the number of constructors, the first <code>compare</code> will have <code>3 * (n - 1) + 1</code> cases and the second one will have <code>n + ((n - 2) * (n - 1)) / 2 + 2</code> cases.</p>
  
  <p>This is pretty unsatisfying since :</p>
  
  <ul>
  <li><code>n = 3</code> (our case) : 7 or 6 cases</li>
  <li><code>n = 4</code> : 10 or 8 cases</li>
  <li><code>n = 5</code> : 13 or 13 cases</li>
  </ul>
  
  <p>It grows pretty fast.</p>
  
  <p>So, I was wondering, do you do it like I do or do you use another method ?</p>
  
  <p>Or, even better, is there the possibility of doing something like</p>
  
  <pre><code>let compare t1 t2 =
    match t1, t2 with
      | c1 x, c2 y -&gt; 
        let c = compare c1 c2 in
        if c = 0 then compare x y else c
  </code></pre>
  
  <p>Or,</p>
  
  <pre><code>let compare (c1 x) (c2 y) = 
    let c = compare c1 c2 in
    if c = 0 then compare x y else c
  </code></pre>
  
  <p>Edit : added a compare if the two constructors are equal for señor Drup (<a href="https://www.youtube.com/watch?v=193RrdkZsjs" rel="nofollow noreferrer">from Guadalup</a> ;-P)</p>