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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 7C850BC68 for ; Sat, 30 Sep 2006 20:21:04 +0200 (CEST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k8UIL3Nc009051 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 30 Sep 2006 20:21:04 +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 k8UI1PiW060019 for ; Sat, 30 Sep 2006 20:01:25 +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 k8UI1Plo016403 for ; Sat, 30 Sep 2006 20:01:25 +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; Sat, 30 Sep 2006 20:01:25 +0200 Message-ID: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> Date: Sat, 30 Sep 2006 20:01:25 +0200 From: Diego Olivier FERNANDEZ PONS To: caml-list@inria.fr Subject: More problems with memoization 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]); Sat, 30 Sep 2006 20:01:25 +0200 (CEST) X-Virus-Scanned: ClamAV 0.88.2/1952/Sat Sep 30 16:35:55 2006 on shiva.jussieu.fr X-Virus-Status: Clean X-Miltered: at concorde with ID 451EB590.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 451EB0F5.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 memoization:01 memoized:01 fib:01 fib:01 val:01 val:01 andrej:01 rec':01 computed:01 computations:01 memoization:01 wrote:01 rec:01 Bonjour, I wrote the following (classical) memoized code for the fibonacci =20 function and I have been unsuccessfully trying to generalize it with a =20 higher order function. let rec fib =3D function | 0 -> 0 | 1 -> 1 | n -> fib_mem (n - 1) + fib_mem (n - 2) and fib_mem =3D let table =3D ref [] in function n -> try =09List.assoc n !table with Not_found -> =09let f_n =3D fib n in =09 table :=3D (n, f_n) :: !table; =09 f_n # val fib : int -> int =3D # val fib_mem : int -> int =3D It works: fib 35 answers instantaneously. Now I want to achieve the same result with a higher order function =20 [make_memo] and apply it to fib let make_mem =3D function f -> let table =3D ref [] in function n -> try =09List.assoc n !table with Not_found -> =09let f_n =3D f n in =09 table :=3D (n, f_n) :: !table; =09 f_n #val make_mem : ('a -> 'b) -> 'a -> 'b Very well. Notice that it has one less parameter than the code posted =20 by Andrej Bauer which has type memo_rec : (('a -> 'b) -> 'a -> 'b) -> =20 'a -> 'b. The only difference is the line let f_n =3D f n in ... with respect to let f_n =3D f g n in ... where g is the anonymous function itself in the same way Bauer's [fib_memo] uses an extra parameter [self] let fib_memo =3D let rec fib self =3D function | 0 -> 1 | 1 -> 1 | n -> self (n - 1) + self (n - 2) in memo_rec fib Now I try to apply make_mem to but it does not work 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 # This kind of expression is not allowed as right-hand side of `let rec' Ok... usually one only need to expand to avoid the problem let rec fib =3D function | 0 -> 0 | 1 -> 1 | n -> fib_mem (n - 1) + fib_mem (n - 2) and fib_mem =3D function n -> let f =3D make_mem fib in f n # val fib : int -> int =3D # val fib_mem : int -> int =3D But know fib 35 takes several minutes to be computed ! I believe I understand why: I am computing a different fib_mem for =20 each value of n and applying it just after, while I wanted a single =20 fib_mem to be used for all computations. In the process, the =20 tabulation vanishes. The only work around I found is to lift the table argument in [make_mem] let make_mem =3D fun table f -> function n -> try List.assoc n !table with Not_found -> let f_n =3D f n in =09table :=3D (n, f_n) :: !table; =09f_n # val make_mem : ('a * 'b) list ref -> ('a -> 'b) -> 'a -> 'b =3D And build fib in the following way let fib_mem =3D function n -> let table =3D ref [] and fib =3D function =09| 0 -> 0 =09| 1 -> 1 =09| n -> fib_mem (n - 1) + fib_mem (n - 2) in make_mem table fib n # fib_mem 35: instantaneous The problem is that the memoization is much more intrusive, which is =20 what I was trying to avoid. Diego Olivier