title: Pattern matching against value constructors in type variables / some sort of flexible function-polymorphism in Haskell
body: <p>Let’s say I have the algebraic data type of a binary tree defined as:</p>
  
  <pre class="lang-hs prettyprint-override"><code>data Tree a = Empty | Node a (Tree a) (Tree a)
  </code></pre>
  
  <p>To build trees, I now want to define a function <code>(-&lt;)</code> such that I can create trees like this:</p>
  
  <pre><code>1-&lt;(2,3)      1-&lt;(2-&lt;(3,4),5)      1-&lt;(Empty,2-&lt;(4,5))
    1                 1                        1
   / \               / \                        \
  2   3             2   5                        2
                   / \                          / \
                  3   4                        4   5
  </code></pre>
  
  <p>It seems it impossible! My reasoning is that it must have type signature <code>a -&gt; (a, a) -&gt; Tree a)</code>. I then thought that it might be possible to interpret something of type <code>a</code> either as <code>Tree b</code> for some other type <code>b</code> or, if that fails, plainly as <code>a</code>. In the same manner I tried to define</p>
  
  <pre class="lang-hs prettyprint-override"><code>f :: a -&gt; Int
  f (Just _) = 1
  f _ = 0
  </code></pre>
  
  <p>which would be a function that told me whether a value is of type <code>Maybe a</code> and constructed by <code>Just</code> or not. But this doesn’t work – ghc then wants the type signature to be <code>Maybe a -&gt; Int</code>.</p>
  
  <p>Unless I don’t know of any special feature in Haskell, what I want is impossible. My questions now are:</p>
  
  <ul>
  <li>Is it? Or do I miss something?</li>
  <li>What would be a good approximation to what I want? (I want to go for succintness, so e.g. writing <code>(Right 2 -&lt;(Right 3, Left (Right 4 -&lt;(Right 1, Right 5)))</code> is no solution.)</li>
  </ul>
  
  <p>P.S. I really don’t know how to title this question.</p>