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.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE autolearn=disabled version=3.1.3 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 40324BC69 for ; Fri, 23 Nov 2007 14:44:16 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAP5nRkfZDAtgn2dsb2JhbACPNAEBAQEHBAYJCBg X-IronPort-AV: E=Sophos;i="4.21,456,1188770400"; d="scan'208";a="6111094" Received: from smtp007.mail.ukl.yahoo.com ([217.12.11.96]) by mail3-smtp-sop.national.inria.fr with SMTP; 23 Nov 2007 14:44:15 +0100 Received: (qmail 92116 invoked from network); 23 Nov 2007 13:44:07 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.fr; h=Received:X-YMail-OSG:In-Reply-To:References:Mime-Version:Content-Type:Message-Id:Cc:Content-Transfer-Encoding:From:Subject:Date:To:X-Mailer; b=PGl4214m1/Arc7wAzlNEh/Ob7ZtyZM1k5Lxdgtfia1kdlZqf1EIOXU/6S3yH7KmiBPRW97Xix/oFjwpTjTJM7vK+9HFWzhg9Hd20lkPOysNZbPTARavUQVYFHbm1w7U2V3XvmaSCbSfssWjpmNwe6bgTkhjefZmFA7BsmxHh+8E= ; Received: from unknown (HELO ?192.168.0.12?) (vincent.aravantinos@82.229.199.66 with plain) by smtp007.mail.ukl.yahoo.com with SMTP; 23 Nov 2007 13:44:07 -0000 X-YMail-OSG: RNj2OBcVM1kEgrVY_uGDDLiR488tDxLIGrJeX_PZ6MZu.6Wlie.rNZjM7XpQB6XV2oiAmFm_RA-- In-Reply-To: <4746D7BA.6060508@lix.polytechnique.fr> References: <2921298.1195790493072.JavaMail.jtbryant@valdosta.edu> <47469A02.6010503@frisch.fr> <4746D7BA.6060508@lix.polytechnique.fr> Mime-Version: 1.0 (Apple Message framework v752.2) Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: <27F8BDCA-043D-48EA-9CB6-5EBC65E9829F@yahoo.fr> Cc: Alain Frisch , Jonathan T Bryant , caml-list@yquem.inria.fr Content-Transfer-Encoding: quoted-printable From: Vincent Aravantinos Subject: Re: [Caml-list] Type issue Date: Fri, 23 Nov 2007 14:44:05 +0100 To: Arnaud Spiwack X-Mailer: Apple Mail (2.752.2) X-Spam: no; 0.00; frisch:01 bool:01 bool:01 val:01 recursion:01 recursive:01 occurences:01 recursive:01 val:01 semantics:01 hen:98 polymorphic:01 wrote:01 arnaud:01 rec:01 Le 23 nov. 07 =E0 14:38, Arnaud Spiwack a =E9crit : > Alain Frisch a =E9crit : >> Jonathan T Bryant wrote: >>> List, >>> >>> I don't understand the following typing: >>> >>> # type 'a t =3D Cond of bool t * 'a t * 'a t | Value of 'a;; >>> type 'a t =3D Cond of bool t * 'a t * 'a t | Value of 'a >>> >>> # let rec f t =3D match t with >>> Cond (c,t,e) -> if f c then f t else f e >>> | Value x -> x >>> ;; >>> val f : bool t -> bool =3D >> >> The type system does not infer polymorphic recursion: the type of =20 >> a recursive function cannot be more general than any of its =20 >> occurences within its body. >> >> You can get around this limitation in various ways. E.g., with =20 >> recursive modules: > My personal favorite, without modules : > > # type 'a t =3D Cond of bool t * 'a t * 'a t | Value of 'a;; > > let f_gen branch next t =3D match t with > Cond (c,t,e) -> if branch c then next t else next e > | Value x -> x > ;; > > let rec f_deep t =3D f_gen f_deep f_deep t;; > > let rec f t =3D f_gen f_deep f t;; > > > type 'a t =3D Cond of bool t * 'a t * 'a t | Value of 'a > val f_gen : (bool t -> bool) -> ('a t -> 'a) -> 'a t -> 'a =3D > val f_deep : bool t -> bool =3D > val f : 'a t -> 'a =3D > > The pattern is rather generic (here we can do a bit better by =20 > replacing "next" by a recursive call to f_gen actually) : > - you first write a generic version of your function where =20 > "recursive calls" are taken as arguments > - you write a certain number of type-specialized function which are =20= > intended to be used as initial "recursive calls". > They are themselves really recursive > - you write your final function by using the type-specialized ones =20 > as "recursive calls" > > Notice that the use of "recursive calls" in the above is justified =20 > since all these functions have precisely the same semantics (and =20 > almost the same behaviour once compiled). But if someone has a =20 > better vocabulary to describe this practice, I'd gladly adopt it, =20 > as I'm not really satisfied with it. (I use "continuations" as =20 > well, but it still not quite what we intend). This is just wonderful ! Thanks, V.=