title: Compute type fixed point
body: <p>Suppose we have some type-function <code>F&lt;T&gt;</code>, and we want to compute its fixed point <code>type X = F&lt;X&gt;</code>. While this might work with types that are objects</p>
  <pre class="lang-js prettyprint-override"><code>interface Tree1&lt;T&gt; { left: T; right: T }
  interface Tree extends Tree1&lt;Tree&gt; {}
  declare const t: Tree;
  const r = t.left.right; // OK
  </code></pre>
  <p>for more generic type-functions it doesn't:</p>
  <pre class="lang-js prettyprint-override"><code>type Tree1&lt;T&gt; = null | { left: T; right: T }
  interface Tree extends Tree1&lt;Tree&gt; {} // can't extend not-object
  </code></pre>
  <p>Without a deferred type-level computation given by <code>interface</code>, it's hard to avoid infinite instantiation. The best I could do is just delay it:</p>
  <pre class="lang-js prettyprint-override"><code>interface Tree1&lt;T&gt; { left: T; right: T }
  type Temp1&lt;T&gt; = { a: null | [T[keyof T], T[keyof T]] }
  interface Temp2 extends Temp1&lt;Temp2&gt; {}
  declare const t: Temp2;
  const r = t.a; // Type instantiation is excessively deep
  </code></pre>
  <p>Also it is possible to fix it by introducing extraneous nodes into the tree, but that's not what I'm after.</p>
  <pre class="lang-js prettyprint-override"><code>type Tree1&lt;T&gt; = null | { left: T; right: T }
  type Tree = Tree1&lt;{ref: Tree}&gt; // OK
  </code></pre>
  <p>Neither is directly defining <code>Tree</code>.</p>
  <pre class="lang-js prettyprint-override"><code>type Tree = null | { left: Tree, right: Tree }
  </code></pre>
  <p><strong>How to compute that elusive fixed point?</strong></p>
  <pre class="lang-js prettyprint-override"><code>type Tree1&lt;T&gt; = null | { left: T; right: T }
  type Tree = ???
  const t: Tree = {left: null, right: {left: null, right: null}};
  </code></pre>