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=none 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 52E2ABC68 for ; Sun, 1 Oct 2006 02:51:53 +0200 (CEST) Received: from out1.smtp.messagingengine.com (out1.smtp.messagingengine.com [66.111.4.25]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k910pq65023099 for ; Sun, 1 Oct 2006 02:51:53 +0200 Received: from frontend3.internal (frontend3.internal [10.202.2.152]) by frontend1.messagingengine.com (Postfix) with ESMTP id C6EB0DADE73; Sat, 30 Sep 2006 20:51:44 -0400 (EDT) Received: from heartbeat2.internal ([10.202.2.161]) by frontend3.internal (MEProxy); Sat, 30 Sep 2006 20:51:48 -0400 X-Sasl-enc: bvSbqh+oVNL2/hDHIKdaaKvPszfWVVA5gGU5gFToA7u8 1159663907 Received: from adsl-75-22-175-234.dsl.sndg02.sbcglobal.net (adsl-75-22-175-234.dsl.sndg02.sbcglobal.net [75.22.175.234]) by mail.messagingengine.com (Postfix) with ESMTP id 72ACD1A2; Sat, 30 Sep 2006 20:51:47 -0400 (EDT) Date: Sat, 30 Sep 2006 17:51:38 -0700 (PDT) From: Martin Jambon X-X-Sender: martin@droopy To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] More problems with memoization In-Reply-To: <200610010123.48846.jon@ffconsultancy.com> Message-ID: References: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> <200610010123.48846.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-j-chkmail-Score: MSGID : 451F1128.001 on discorde : j-chkmail score : X : 0/20 1 X-Miltered: at discorde with ID 451F1128.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; memoization:01 recursion:01 higher-order:01 fib:01 recursive:01 fib:01 val:01 recursive:01 1977:98 2006,:98 wrote:01 rec:01 rec:01 caml-list:01 int:01 On Sun, 1 Oct 2006, Jon Harrop wrote: > I believe you want to "untie the knot" of recursion, creating an higher-order, > auxiliary fibonacci function fib_aux that accepts the recursive call as an > argument: > > # let rec fib_aux fib = function > | 0 | 1 as n -> n > | n -> fib(n - 1) + fib(n - 2);; > val fib_aux : (int -> int) -> int -> int = Since the point is to make the function not recursive, I think you shouldn't use "let rec" :-) Martin -- Martin Jambon, PhD http://martin.jambon.free.fr