From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 30965BBAF for ; Wed, 17 Feb 2010 19:00:05 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmMEAOe9e0tQDPJlXWdsb2JhbACDBYwmi1cLFwkMBRADBSCuTY9wgTCCUVwEhn8 X-IronPort-AV: E=Sophos;i="4.49,492,1262559600"; d="scan'208";a="57192185" Received: from smtp28.orange.fr ([80.12.242.101]) by mail4-smtp-sop.national.inria.fr with ESMTP; 17 Feb 2010 19:00:04 +0100 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2818.orange.fr (SMTP Server) with ESMTP id 1C687800631D; Wed, 17 Feb 2010 19:00:04 +0100 (CET) Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2818.orange.fr (SMTP Server) with ESMTP id E693180002BF; Wed, 17 Feb 2010 19:00:03 +0100 (CET) Received: from Lenovo-R60 (Mix-Lyon-303-2-42.w193-248.abo.wanadoo.fr [193.248.44.42]) by mwinf2818.orange.fr (SMTP Server) with ESMTP id A12468006417; Wed, 17 Feb 2010 19:00:02 +0100 (CET) X-ME-UUID: 20100217180002660.A12468006417@mwinf2818.orange.fr X-ME-User-Auth: alphablock From: "Damien Guichard" Subject: Re: [Caml-list] type generalization of recursive calls To: =?utf-8?B?U3TDqXBoYW5l?= Gimenez Cc: "The Caml Mailing List" Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Date: Wed, 17 Feb 2010 18:59:58 +0100 Message-ID: <557690804087658719@orange.fr> X-Mailer: EssentialPIM v. 3.12 X-Spam: no; 0.00; damien:01 guichard:01 recursive:01 syntax:01 recursion:01 ocaml:01 ocaml:01 damien:01 gimenez:01 gimenez:01 recursive:01 syntactical:01 checker:01 pointers:01 cheers:01 Hello, First, you really need strong tyupe checking because your definition is actually incorrect. Second, see polymorphic-recursion : http://alaska-kamtchatka.blogspot.com/2009/05/polymorphic-recursion.html Be sure to read the comments by bluestorm. There is also pa_polyrec, a syntax extension for polymorphic recursion in OCaml : http://www.mail-archive.com/caml-list@yquem.inria.fr/msg04795.html Finally, here is your (corrected) code using vanilla ocaml : type map = { map : 'a 'b. ('a -> 'b) -> 'a t -> 'b t } let map = let rec map = { map = fun f -> function | E -> E | D (t1, t2) -> D (map.map f t1, map.map f t2) | O a -> O (f a) | I tt -> I (map.map (map.map f) tt) } in map.map - damien Le 17/02/2010 à 17:34:24, "Stéphane Gimenez" à écrit : > >Hi, > >I just realized that ocaml generalizes the type of a recursively >defined function *only* for calls which are outside it's own >definition. Recursive calls cannot use a generalized type. > >In fact, I'm tring to work with such a data type: > >type 'a t = > | E > | D of 'a t * 'a t > | O of 'a > | I of 'a t t > >And, I'm forced to use some dark magic to define simple operations on >it: > >let rec map (f : 'a -> 'b) : 'a t -> 'b t = > begin function > | E -> E > | D (t1, t2) -> D (map f t1, map f t2) > | O a -> O (f a) > | I tt -> > I ((Obj.magic map : ('a t -> 'b t) -> 'a t t -> 'b t t) (map f) tt) > end > >Questions: > - Is it theoreticaly safe to generalize recursive calls ? > - Is there a syntactical trick to use generalized recursive calls ? > - Could such a generalization be added to the type checker ? > - Performance issues ? > - More obfusctated type checking errors ? > >In a related disscution I found, one asked about generalization >between mutualy recursive definitions (same problem). No answers, but >maybe I just lack pointers. > >Cheers, >Stéphane > >_______________________________________________ >Caml-list mailing list. Subscription management: >http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list >Archives: http://caml.inria.fr >Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >Bug reports: http://caml.inria.fr/bin/caml-bugs > -- Mail created using EssentialPIM Free - www.essentialpim.com