title: Why is this expression a function instead of a bool?
body: <p>Why is <code>is_empty kv</code> considered of type <code>('a,'b) trie -&gt; bool</code>, when <code>kv</code> is supplied (of what I believe should be type <code>('k, 'v) -- a Trie)</code>? After all, the function is defined as recursive, and the other return values are of type <code>bool</code>.</p>
  
  <p>As written here, the code snippet is not supposed to be correct, but just works as an example of my confusion about the type system.</p>
  
  <p>in a separate signature file:</p>
  
  <pre><code>type ('k, 'v) trie 
  val empty : ('k, 'v) trie
  val is_empty : ('k, 'v) trie -&gt; bool
  </code></pre>
  
  <p>in the implementation file:</p>
  
  <pre><code>type ('k, 'v) trie = Trie of 'v option * (('k * ('k, 'v) trie) list)
  
  let empty = Trie (None, [])
  
  let rec is_empty t = function
  |Trie (None, []) -&gt; true
  |Trie (Some x, _) -&gt; false
  |Trie (None, (k,kv)::tail) -&gt; is_empty kv
  </code></pre>
  
  <p>the error:</p>
  
  <pre><code>File "trie.ml", line 11, characters 34-45:
  Error: This expression has type ('a, 'b) trie -&gt; bool
     but an expression was expected of type bool
  </code></pre>