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 93ACDBC50 for ; Mon, 2 Oct 2006 17:29:26 +0200 (CEST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k92FTQvN005688 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 2 Oct 2006 17:29:26 +0200 Received: from courriel.upmc.fr (courriel3.reseau.jussieu.fr [134.157.0.194]) by shiva.jussieu.fr (8.13.7/jtpda-5.4) with ESMTP id k92FT78T033261 ; Mon, 2 Oct 2006 17:29:07 +0200 (CEST) X-Ids: 164 Received: from etu.upmc.fr (localhost [127.0.0.1]) by courriel.upmc.fr (8.13.6/jtpda-5.4) with ESMTP id k92FT24U047417 ; Mon, 2 Oct 2006 17:29:06 +0200 (CEST) Received: from out-of.ilog.fr (out-of.ilog.fr [81.80.159.49]) by webmail.etu.upmc.fr (Horde MIME library) with HTTP; Mon, 02 Oct 2006 17:29:02 +0200 Message-ID: <20061002172902.93z4c75nj4c8c884@webmail.etu.upmc.fr> Date: Mon, 02 Oct 2006 17:29:02 +0200 From: Diego Olivier FERNANDEZ PONS To: Jon Harrop Cc: caml-list@inria.fr Subject: Re: [Caml-list] More problems with memoization References: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> <200610010123.48846.jon@ffconsultancy.com> In-Reply-To: <200610010123.48846.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: quoted-printable User-Agent: Internet Messaging Program (IMP) H3 (4.1.3) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0.2 (shiva.jussieu.fr [134.157.0.164]); Mon, 02 Oct 2006 17:29:07 +0200 (CEST) X-Virus-Scanned: ClamAV 0.88.2/1971/Mon Oct 2 15:28:21 2006 on shiva.jussieu.fr X-Virus-Status: Clean X-Miltered: at discorde with ID 45213056.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 45213043.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 memoization:01 recursion:01 higher-order:01 fib:01 recursive:01 fib:01 val:01 combinator:01 higher-order:01 memoization:01 memoize:01 andrej:01 recursion:01 Bonjour, Quoting Jon Harrop : > I believe you want to "untie the knot" of recursion, creating an =20 > higher-order, auxiliary fibonacci function fib_aux that accepts the =20 > recursive call as an argument: > > # let rec fib_aux fib =3D function > | 0 | 1 as n -> n > | n -> fib(n - 1) + fib(n - 2);; > val fib_aux : (int -> int) -> int -> int =3D > [...] > You can recover the ordinary fibonacci function using the Y combinator: [...] > You can write a higher-order memoization function that accepts an argument > with the type of fib_aux: > # memoize fib_aux 35;; > - : int =3D 9227465 Your solution is similar to Andrej Brauer's one which is exactly what =20 I was trying to avoid because it is too much intrusive. When you break =20 the recursion in two functions you change the type of [fib] from [fib : int -> int] to [fib : (int -> int) -> int -> int)]. In my first example you keep the type of [fib] and add a second =20 function [fib_mem]. You can use anyone indifferently and hide the =20 latter with the .mli val fib : int -> int =3D val fib_mem : int -> int =3D When you compare your solution with what I am trying to do you see =20 there is a big difference in locality and transparency let rec fib =3D function | 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) transformed into let rec fib =3D function | 0 -> 0 | 1 -> 1 | n -> fib_mem (n - 1) + fib_mem (n - 2) and fib_mem =3D make_mem fib The latter could even be done automatically by a source to source =20 transformation (if it worked). Diego Olivier