Varianza OCaml(+ ''a,-''a) e invariancia

covariance contravariance

Question

Después de escribir este pedazo de código

module type TS = sig
  type +''a t
end

module T : TS = struct
  type ''a t = {info : ''a list}
end

Me di cuenta de que necesitaba info para ser mutable.

Yo escribí, entonces:

module type TS = sig
  type +''a t
end

module T : TS = struct
  type ''a t = {mutable info : ''a list}
end

Pero, sorpresa,

Type declarations do not match:
  type ''a t = { mutable info : ''a list; }
is not included in
  type +''a t
Their variances do not agree.

Oh, recuerdo haber oído hablar de la varianza . Era algo sobre covarianza y contravarianza . Soy una persona valiente, encontraré mi problema solo!

¡Encontré estos dos artículos interesantes ( here y here ) y entendí!

puedo escribir

module type TS = sig
  type (-''a, +''b) t
end

module T : TS = struct
  type (''a, ''b) t = ''a -> ''b
end

Pero entonces me preguntaba. ¿Cómo es que los tipos de datos mutables son invariantes y no solo covariantes?

Quiero decir, entiendo que una ''A list puede considerarse como un subtipo de una lista (''A | ''B) list porque mi lista no puede cambiar. Lo mismo para una función, si tengo una función de tipo ''A | ''B -> ''C ''A | ''B -> ''C puede considerarse como un subtipo de una función de tipo ''A -> ''C | ''D ''A -> ''C | ''D porque si mi función puede manejar ''A y ''B '' s, puede manejar solo ''A '' s y si solo devuelvo ''C '' s puedo esperar ''C ''D o ''D '' s (pero yo solo obtener ''C '' s).

¿Pero para una matriz? Si tengo una ''A array no puedo considerarla como una ''A array (''A | ''B) array porque si modifico un elemento en la matriz poniendo una ''B , mi tipo de matriz es incorrecto porque realmente es una (''A | ''B) array y ya no un ''A array . Pero ¿qué pasa con una (''A | ''B) array como una ''A array ? Sí, sería extraño porque mi matriz puede contener ''B pero, extrañamente, pensé que era lo mismo que una función. Tal vez, al final, no entendí todo, pero quería poner mis pensamientos al respecto aquí porque me tomó mucho tiempo entenderlo.

TL; DR :

persistente: +''a

funciones: -''a

mutable: invariante ( ''a )? ¿Por qué no puedo forzar que sea -''a ?

Answer 1

Creo que la explicación más sencilla es que un valor mutable tiene dos operaciones intrínsecas: captador y definidor, que se expresan mediante acceso de campo y sintaxis de conjunto de campos:

type ''a t = {mutable data : ''a}

let x = {data = 42}

(* getter *)
x.data

(* setter *)
x.data <- 56

Getter tiene un tipo ''at -> ''a , donde ''a variable de tipo aparece en el lado derecho (por lo que impone una restricción de covarianza), y el establecedor tiene el tipo ''at -> ''a -> unit donde la variable de tipo Ocurre a la izquierda de la flecha, que impone una restricción contravariante. Entonces, tenemos un tipo que es tanto covariante como contravariante, lo que significa que el tipo variable ''a es invariante.

Answer 2

Su tipo t básicamente permite dos operaciones: obtener y configurar. Informalmente, get tiene el tipo ''at -> ''a list y la configuración tiene el tipo ''at -> ''a list -> unit . Combinado, ''a ocurre tanto en una posición positiva como en una negativa.

[EDITAR: La siguiente es una (con suerte) una versión más clara de lo que escribí en primer lugar. Lo considero superior, así que borré la versión anterior.]

Intentaré hacerlo más explícito. Supongamos que sub es un subtipo adecuado de super y witness es algún valor de tipo super que no es un valor de tipo sub . Ahora sea f : sub -> unit una función que falla en el valor witness . La seguridad de tipo está ahí para garantizar que el witness nunca pase a f . Mostraré con el ejemplo que la seguridad de tipos falla si se permite que uno trate a un subtipo como un subtipo de super t , o al revés.

let v_super = ({ info = [witness]; } : super t) in
let v_sub = ( v_super : sub t ) in   (* Suppose this was allowed. *)
List.map f v_sub.info   (* Equivalent to f witness. Woops. *)

Por lo tanto, no se puede permitir tratar el super t como un subtipo de sub t . Esto muestra la covarianza, que ya sabías. Ahora por contravarianza.

let v_sub = ({ info = []; } : sub t) in
let v_super = ( v_sub : super t ) in  (* Suppose this was allowed. *)
v_super.info <- [witness];
   (* As v_sub and v_super are the same thing,
      we have v_sub.info=[witness] once more. *)
List.map f v_sub.info   (* Woops again. *)

Por lo tanto, tratar el sub t como un subtipo de super t tampoco se puede permitir, lo que demuestra la contravarianza. Juntos, ''at es invariante.