To keep sharing, every instance of a node will be kept in a table, and the mark of the old node will be equal (modulo a translation) to the index of the corresponding node in the table. Since we do not know at the beginning the size of the table. we write a library of extensible arrays.

module Iarray = struct type 'a t = { mutable t : 'a array; v : 'a } let create k v = { t = Array.create (max k 3) v; v = v } let get a i = if Array.length a.t > i then a.t.(i) else a.v let set a i v = let n = Array.length a.t in if n > i then a.t.(i) <- v else begin let t = Array.create (2 * n) a.v in Array.blit a.t 0 t 0 n; a.t <- t; t.(i) <- v; end end;;

Now, we can define the instance function. The polymorphic variables are created first. Then, when we meet variables that have not been created, we know that they should be shared rather than duplicated.

let type_instance (q, t) = let table = Iarray.create 7 (tvar()) in let poly = marker() in let copy_var t = let t' = tvar() in let p = marker() in t.mark <- p; Iarray.set table (p - poly) t'; t' in let q' = copy_var q in let rec visit t = let t = repr t in if t.mark > poly then Iarray.get table (t.mark -poly) else begin match desc t with | Tvar _ | Tcon (_, []) -> t | Tcon (g, l) -> let t' = copy_var t in t'.texp <- Desc (Tcon (g, visit l)); t' end in visit t;;