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 6E4C5BC50 for ; Tue, 3 Oct 2006 01:00:23 +0200 (CEST) Received: from postar.fmf.uni-lj.si (vega.fmf.uni-lj.si [193.2.67.45]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k92N0NuR014403 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 3 Oct 2006 01:00:23 +0200 Received: from localhost (unknown [192.168.5.1]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id C7A93BB93C; Tue, 3 Oct 2006 01:00:20 +0200 (CEST) X-Virus-Scanned: amavisd-new at spam.fmf.uni-lj.si Received: from postar.fmf.uni-lj.si ([192.168.5.5]) by localhost (spam.fmf.uni-lj.si [192.168.5.1]) (amavisd-new, port 10024) with ESMTP id SrgAMmIYWszF; Tue, 3 Oct 2006 01:00:58 +0200 (CEST) Received: from [192.168.1.100] (BSN-77-186-71.dsl.siol.net [193.77.186.71]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id 05B8BBB6E9; Tue, 3 Oct 2006 01:00:19 +0200 (CEST) Message-ID: <45219A06.6080909@fmf.uni-lj.si> Date: Tue, 03 Oct 2006 01:00:22 +0200 From: Andrej Bauer Reply-To: Andrej.Bauer@andrej.com User-Agent: Thunderbird 1.5.0.5 (X11/20060812) MIME-Version: 1.0 To: Diego Olivier FERNANDEZ PONS , caml-list@inria.fr Subject: Re: [Caml-list] More problems with memoization References: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> <200610010123.48846.jon@ffconsultancy.com> <20061002172902.93z4c75nj4c8c884@webmail.etu.upmc.fr> In-Reply-To: <20061002172902.93z4c75nj4c8c884@webmail.etu.upmc.fr> Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 45219A07.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; andrej:01 andrej:01 memoization:01 pons:01 fib:01 fib:01 mli:01 val:01 val:01 memoized:01 locality:01 fib':01 fib':01 combinator:01 locality:01 Diego Olivier FERNANDEZ PONS wrote: > In my first example you keep the type of [fib] and add a second function > [fib_mem]. You can use anyone indifferently and hide the latter with the > .mli > val fib : int -> int = > val fib_mem : int -> int = If you want to keep the same type for fib, and have the memoized one, as well as to have locality you can do something like this: let make_memo f = ... let rec make_rec f x = f (make_rec f) x let fib, fib_mem = let fib' self = function | 0 -> 0 | 1 -> 1 | n -> self (n - 1) + self (n - 2) in make_rec fib', make_mem fib (You will notice that make_rec is just the Y combinator.) > When you compare your solution with what I am trying to do you see there > is a big difference in locality and transparency I fail to see this big difference, frankly, since all you're doing is just a beta-reduction of what Jon and I suggested. A recursive function _is_ the fixed point of a non-recursive one with an "extra" argument. You may hide this fact if you wish, but I think it's more honest to admit it to yourself. The "untied" version of fib has the advantage that you can do many cool things to it: memoizing is just one possibility. Andrej