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=1.1 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 026F2BC6E for ; Tue, 3 Apr 2007 19:35:06 +0200 (CEST) Received: from nz-out-0506.google.com (nz-out-0506.google.com [64.233.162.231]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l33HZ4NY017496 for ; Tue, 3 Apr 2007 19:35:05 +0200 Received: by nz-out-0506.google.com with SMTP id r28so1148213nza for ; Tue, 03 Apr 2007 10:35:03 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=EnkqDVFG6c/yxQoOSuB5kBO21WvksWqret3vxzbm4/6RGPH/XN+vg7jenjaz3ZuOScWzU3XiN4YH5pEGwGXa6rlf/l212ISwE2jhv3XU4TYHT4VQSdWw3xeWLzoSCXtnxA8lxQGBsSRcW6whAn5EW/XFSSLmrlRrlREzmNVaWsg= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=JFkySwww8W4RO5VFSYiERLu0/BhXKNhNGXU+mBOxUneVVwJqzAL2Jj9DUbD839RDqcH8AmYQ4rE4Eaq6XYyCMscQCRCpGgZTL3sRNrSj1UIFYzt7g63TUW6IV5tDMmwTYUNUMBh3TNLI4LOtfXVH9sJ2ZxJcSTSo2QnoCUm1SWo= Received: by 10.65.191.7 with SMTP id t7mr12770280qbp.1175621703381; Tue, 03 Apr 2007 10:35:03 -0700 (PDT) Received: by 10.65.98.10 with HTTP; Tue, 3 Apr 2007 10:35:03 -0700 (PDT) Message-ID: <9d3ec8300704031035g5a69d98dx7f7e8e5b2f7037f3@mail.gmail.com> Date: Tue, 3 Apr 2007 19:35:03 +0200 From: "Till Varoquaux" To: "Loup Vaillant" Subject: Re: [Caml-list] Polymorphic recursion Cc: caml-list@yquem.inria.fr In-Reply-To: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <6f9f8f4a0704030959l8ebb155g8532e3ee6d31c66d@mail.gmail.com> X-j-chkmail-Score: MSGID : 46129048.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 46129048.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursion:01 recursion:01 inference:01 undecidable:01 typechecker:01 annotations:01 ocaml:01 recursive:01 seq:01 seq:01 cheers:01 okasaki's:01 functionnal:01 ocaml:01 recursive:01 There is indeed an issue with polymorphic recursion. It has been shown that allowing polymorphic recursion in an ML like language would make the type inference undecidable. One workaround would be for the typechecker to use type annotations in some given cases. This is however not the case in Ocaml: type information are either required or only useful to debug/document some code/"restrict" the type of a given variable. Therefor, if you wish to use polymorphic recursion (yep you can) you might want to use something where you have to specify the type; this includes records, objects and recursive modules. So this type 'a seq = Unit | Seq of ('a * ('a * 'a)seq) type szRec={f:'a.'a seq -> int};; let size= let rec s = {f=function | Unit -> 0 | Seq(_, b) -> 1 + 2 * s.f b} in s.f might be what you where yearning for. Cheers, Till On 4/3/07, Loup Vaillant wrote: > I was reading Okasaki's book, "Purely functionnal data structures", > and discovered that ML (and Ocaml) doesn't support non uniforms > function definitions. > > So, even if: > > (**) > type 'a seq = Unit | Seq of ('a * ('a * 'a)seq);; > (**) > > is correct, > > (**) > let rec size = fun > | Unit -> 0 > | Seq(_, b) -> 1 + 2 * size b;; > (**) > > is not. Here is the error: > # > | Seq(_, b) -> 1 + 2 * size b;; > This expression (the last 'b') has type seq ('a * 'a) but is here used > with type seq 'a > # > > Why? > Can't we design a type system which allow this "size" function? > Can't we implement non uniform recursive function (efficiently, or at all)?. > > I suppose the problem is somewhat difficult, but I can't see where. > > Regards, > Loup Vaillant > > _______________________________________________ > 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 >