Re: [Caml-list] How to compute variance of a type

[Andrej Bauer <Andrej.Bauer@fmf.uni-lj.si>]

There is nothing strange or complicated about variance. Whenever you
descend to the left of an arrow, you have to switch the variance.

I enclose a simple example of how to compute variance for simple types.

Andrej

P.S. Feel free to knock on my office door when you have such questions :-)

--------------------------------------------------------
type name = string

type ty =
  | Var of name      (* type variable *)
  | Prod of ty * ty  (* product *)
  | Arrow of ty * ty (* function type *)

type variance =
  | Variant
  | Covariant
  | Mixed

(** Join variances *)
let join u v =
  if u = v then v else Mixed

let opposite = function
  | Variant -> Covariant
  | Covariant -> Variant
  | Mixed -> Mixed

(** Add a type variable [x] with variance [v] to a given association
    list of variances. *)
let rec add x v = function
  | [] -> [(x,v)]
  | (y,u)::lst ->
      if x = y then
	(x, join u v) :: lst
      else
	(y,u) :: (add x v lst)

(** Compute variances of all type variables appearing
    in a type. Return an association list mapping type parameters
    to their variances.
 *)
let variance t =
  let rec var c lst = function
    | Var v -> add v c lst
    | Prod (t1, t2) -> var c (var c lst t1) t2
    | Arrow (t1, t2) -> var c (var (opposite c) lst t1) t2
  in
    var Variant [] t

(** Examples. *)

let t1 = Arrow (Arrow (Var "a", Var "b"), Var "c")
let v1 = variance t1

let t2 = Arrow (Var "a", Arrow (Var "b", Var "c"))
let v2 = variance t2

let t3 = Arrow (Prod (Var "a", Var "b"), Var "a")
let v3 = variance t3
---------------------------------------------------------