title: How to create a cached recursive type?
body: <pre><code>open System
  open System.Collections.Generic
  
  type Node&lt;'a&gt;(expr:'a, symbol:int) = 
      member x.Expression = expr
      member x.Symbol = symbol
      override x.GetHashCode() = symbol
      override x.Equals(y) = 
          match y with 
          | :? Node&lt;'a&gt; as y -&gt; symbol = y.Symbol
          | _ -&gt; failwith "Invalid equality for Node."
  
      interface IComparable with
          member x.CompareTo(y) = 
              match y with
              | :? Node&lt;'a&gt; as y -&gt; compare symbol y.Symbol
              | _ -&gt; failwith "Invalid comparison for Node."
  
  type Ty =
      | Int
      | String
      | Tuple of Ty list
      | Rec of Node&lt;Ty&gt;
      | Union of Ty list
  
  type NodeDict&lt;'a&gt; = Dictionary&lt;'a,Node&lt;'a&gt;&gt;
  
  let get_nodify_tag =
      let mutable i = 0
      fun () -&gt; i &lt;- i+1; i
  
  let nodify (dict: NodeDict&lt;_&gt;) x =
      match dict.TryGetValue x with
      | true, x -&gt; x
      | false, _ -&gt;
          let x' = Node(x,get_nodify_tag())
          dict.[x] &lt;- x'
          x'
  
  let d = Dictionary(HashIdentity.Structural)
  let nodify_ty x = nodify d x
  
  let rec int_string_stream = 
      Union 
          [
          Tuple [Int; Rec (nodify_ty (int_string_stream))]
          Tuple [String; Rec (nodify_ty (int_string_stream))]
          ]
  </code></pre>
  
  <p>In the above example, the <code>int_string_stream</code> gives a type error, but it neatly illustrates what I want to do. Of course, I want both sides to get tagged with the same <code>symbol</code> in <code>nodify_ty</code>. When I tried changing the <code>Rec</code> type to <code>Node&lt;Lazy&lt;Ty&gt;&gt;</code> I've found that it does not compare them correctly and each sides gets a new symbol which is useless to me.</p>
  
  <p>I am working on a language, and the way I've dealt with storing recursive types up to now is by mapping <code>Rec</code> to an <code>int</code> and then substituting that with the related <code>Ty</code> in a dictionary whenever I need it. Currently, I am in the process of cleaning up the language, and would like to have the <code>Rec</code> case be <code>Node&lt;Ty&gt;</code> rather than an <code>int</code>.</p>
  
  <p>At this point though, I am not sure what else could I try here. Could this be done somehow?</p>