OCaml variance (+'a, -'a) and invariance
<p>After writing this piece of code</p>
<pre><code>module type TS = sig
  type +'a t
end
  
module T : TS = struct
  type 'a t = {info : 'a list}
end
</code></pre>
<p>I realised I needed <code>info</code> to be mutable.</p>
<p>I wrote, then :</p>
<pre><code>module type TS = sig
  type +'a t
end
  
module T : TS = struct
  type 'a t = {mutable info : 'a list}
end
</code></pre>
<p>But, surprise,</p>
<pre><code>Type declarations do not match:
  type 'a t = { mutable info : 'a list; }
is not included in
  type +'a t
Their variances do not agree.
</code></pre>
<p>Oh, I remember hearing about <em>variance</em>. It was something about <em>covariance</em> and <em>contravariance</em>. I'm a brave person, I'll find about my problem alone!</p>
<p>I found these two interesting articles (<a href="https://blogs.janestreet.com/a-and-a/" rel="noreferrer">here</a> and <a href="https://ocaml.org/meetings/ocaml/2013/proposals/injectivity.pdf" rel="noreferrer">here</a>) and I understood!</p>
<p>I can write</p>
<pre><code>module type TS = sig
  type (-'a, +'b) t
end
  
module T : TS = struct
  type ('a, 'b) t = 'a -&gt; 'b
end
</code></pre>
<p>But then I wondered. How come that <em>mutable</em> datatypes are invariant and not just covariant?</p>
<p>I mean, I understand that an <code>'A list</code> can be considered as a subtype of an <code>('A | 'B) list</code> because my list can't change. Same thing for a function, if I have a function of type <code>'A | 'B -&gt; 'C</code> it can be considered as a subtype of a function of type <code>'A -&gt; 'C | 'D</code> because if my function can handle <code>'A</code> and <code>'B</code>'s it can handle only <code>'A</code>'s and if I only return <code>'C</code>'s I can for sure expect <code>'C</code> or <code>'D</code>'s (but I'll only get <code>'C</code>'s).</p>
<p>But for an array? If I have an <code>'A array</code> I can't consider it as a an <code>('A | 'B) array</code> because if I modify an element in the array putting a <code>'B</code> then my array type is wrong because it truly is an <code>('A | 'B) array</code> and not an <code>'A array</code> anymore. But what about a <code>('A | 'B) array</code> as an <code>'A array</code>. Yes, it would be strange because my array can contain <code>'B</code> but strangely I thought it was the same as a function. Maybe, in the end, I didn't understand everything but I wanted to put my thoughts on it here because it took me long to understand it.</p>
<p><strong>TL;DR</strong> :</p>
<blockquote>
<p>persistent : <code>+'a</code></p>
<p>functions : <code>-'a</code></p>
<p>mutable : invariant (<code>'a</code>) ? Why can't I force it to be <code>-'a</code> ?</p>
</blockquote>