title: OCaml Self-Referential Map
body: <p>I'm looking to add a cache to a simple compiler in OCaml. I have created a simpler version of the code that I had that reproduces the same issue. What I need for the cache is to be able to create a Map with A's as keys, so I can lookup the compile output. Here is the code:</p>
  
  <pre><code>module A
  = struct
  
    type ineq =
    | LT
    | EQ
    | GT
  
    type t =
    ...
  
    module ACacheMapKey
    = struct
  
      type t = t
  
      let compare a b =
        match cmp a b with
        | LT -&gt; -1
        | EQ -&gt; 0
        | GT -&gt; 1
  
    end
  
    module CMap = Map.Make(ACacheMapKey)
    let cache_map = CMap.empty
  
    let cmp a b =
      ...
  
  end
  </code></pre>
  
  <p>In module A, <code>type t</code> is a recursive AST-like type. <code>cmp a b</code> returns a <code>ineq</code>. The compile function was left out for brevity, but it just uses the cache before running through a computationally expensive process. In order to create a cache map in A, I need a compatible key module. My attempt at that is <code>ACacheMapKey</code>, but the <code>type t = t</code> doesn't refer to the parent. The error it gives is <code>Error: The type abbreviation t is cyclic</code>. So, is there a better way to make a cache over A? Or is there an easy way to reference the parent and make my current structure work?</p>