From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id E883BBC6B for ; Sun, 6 Jan 2008 16:30:09 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAABOCgEfAXQInh2dsb2JhbACQGwEBAQgKKZcN X-IronPort-AV: E=Sophos;i="4.24,250,1196636400"; d="scan'208";a="5763193" Received: from concorde.inria.fr ([192.93.2.39]) by mail2-smtp-roc.national.inria.fr with ESMTP; 06 Jan 2008 16:30:09 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m06FU7e3026619 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sun, 6 Jan 2008 16:30:09 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAABOCgEfBAkMth2dsb2JhbACQGwEBAQgKKZcN X-IronPort-AV: E=Sophos;i="4.24,250,1196636400"; d="scan'208";a="6328538" Received: from vega.fmf.uni-lj.si (HELO postar.fmf.uni-lj.si) ([193.2.67.45]) by mail1-smtp-roc.national.inria.fr with ESMTP; 06 Jan 2008 16:30:07 +0100 Received: from localhost (unknown [192.168.5.1]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id 5BE9B28EFCF; Sun, 6 Jan 2008 16:30:06 +0100 (CET) X-Virus-Scanned: amavisd-new at spam.fmf.uni-lj.si Received: from postar.fmf.uni-lj.si ([192.168.5.5]) by localhost (spam.fmf.uni-lj.si [192.168.5.1]) (amavisd-new, port 10024) with ESMTP id L1tawaSiEyP0; Sun, 6 Jan 2008 16:30:06 +0100 (CET) Received: from [192.168.1.109] (BSN-77-148-136.static.dsl.siol.net [193.77.148.136]) (Authenticated sender: bauer) by postar.fmf.uni-lj.si (Postfix) with ESMTP id E076A28E774; Sun, 6 Jan 2008 16:30:05 +0100 (CET) Message-ID: <4780F434.8000604@fmf.uni-lj.si> Date: Sun, 06 Jan 2008 16:31:00 +0100 From: Andrej Bauer Reply-To: Andrej.Bauer@andrej.com User-Agent: Thunderbird 1.5.0.14pre (X11/20071023) MIME-Version: 1.0 To: caml-list Cc: =?UTF-8?B?VG9tIFByaW1vxb5pxI0=?= Subject: Re: [Caml-list] How to compute variance of a type References: In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4780F3FF.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; andrej:01 andrej:01 rec:01 rec:01 caml-list:01 variant:02 variant:02 covariant:02 covariant:02 variables:02 string:02 parameters:03 let:03 let:03 types:05 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 ---------------------------------------------------------