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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id E09F8BB83 for ; Sat, 9 Sep 2006 06:10:34 +0200 (CEST) Received: from postar.fmf.uni-lj.si (vega.fmf.uni-lj.si [193.2.67.45]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k894AYb8011478 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 9 Sep 2006 06:10:34 +0200 Received: from localhost (unknown [192.168.5.1]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id 793FAA0176; Sat, 9 Sep 2006 05:38:09 +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 jT8Rr9Kim2Uo; Fri, 1 Dec 2006 21:21:14 +0000 (UTC) Received: from haka.fmf.uni-lj.si (haka.fmf.uni-lj.si [193.2.67.18]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id D7B111F6AF; Sat, 9 Sep 2006 05:38:07 +0200 (CEST) Received: from bsn-77-186-71.dsl.siol.net ([193.77.186.71] helo=[192.168.1.99]) by haka.fmf.uni-lj.si with esmtpa (Exim 4.50) id 1GLthI-0007KR-1h; Sat, 09 Sep 2006 05:40:04 +0200 Message-ID: <45023723.2050708@andrej.com> Date: Sat, 09 Sep 2006 05:38:11 +0200 From: Andrej Bauer User-Agent: Thunderbird 1.5.0.2 (X11/20060516) MIME-Version: 1.0 To: caml-list@inria.fr Cc: Erik de Castro Lopo References: <20060909103332.0397efea.mle+ocaml@mega-nerd.com> In-Reply-To: <20060909103332.0397efea.mle+ocaml@mega-nerd.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-SA-Exim-Connect-IP: 193.77.186.71 X-SA-Exim-Mail-From: Andrej.Bauer@andrej.com Subject: Re: [Caml-list] Memoization X-SA-Exim-Version: 4.2 (built Thu, 03 Mar 2005 10:44:12 +0100) X-SA-Exim-Scanned: Yes (on haka.fmf.uni-lj.si) X-Miltered: at nez-perce with ID 45023EBA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; andrej:01 andrej:01 memoization:01 higher-order:01 memoized:01 recursive:01 memoized:01 ocaml:01 recursive:01 recomputed:01 compares:01 fib:01 fib:01 wrote:01 polymorphic:01 Erik de Castro Lopo wrote: > > Unfortunately, the URL is dead. Does anybody have another link for > that code or some other polymorphic memoizer? > I use the code below to show my students what can be done with higher-order functions. For a real implementation, we would have to use something more efficient than association lists (but then you might end up writing a polymorphic version of the Map module). Improvements are welcome. -------------------- (** [memo f] is a memoized version of function [f]. If [f] makes recursive calls, those are not memoized. In this example we use simple asociation lists. It would be better to use efficietn search trees. Alas, ocaml Map module is not polymorphic (for a good reason?). *) let memo f = let m = ref [] in fun x -> try List.assoc x !m with Not_found -> let y = f x in m := (x, y) :: !m ; y (** [memo_rec f] is a memoized version of a recursive function [f]. The recursive function must not make calls to itself directly, but rather via an extra "self" parameter, see example below. *) let memo_rec f = let m = ref [] in let rec g x = try List.assoc x !m with Not_found -> let y = f g x in m := (x, y) :: !m ; y in g (** [memo_test f stamp renew] is a memoized version of function [f], where [stamp] and [renew] are used to invalidate memoized values and force them being recomputed. For example, [f] could be a function which reads the contents of a file, [stamp] the function which returns the file's modification time, and [renew] the function which compares two modification times. Note that we keep storing new values in an association list without removing old ones, so this creates a memory leak. An intelligent implementation would, again, use efficient search trees. *) let memo_test f stamp renew = let m = ref [] in fun x -> try let y, s = List.assoc x !m in let t = stamp x in if renew s t then let y = f x in m := (x, (y, t)) :: !m ; y else y with Not_found -> let y = f x in let s = stamp x in m := (x, (y, s)) :: !m; y (** Example: the Fibonacci sequence, unmemoized, very inefficient. *) let rec fib_slow = function 0 -> 1 | 1 -> 1 | n -> fib_slow (n - 1) + fib_slow (n - 2) (** Example: a memoized version of the Fibonacci sequence. *) let fib_memo = let rec fib self = function 0 -> 1 | 1 -> 1 | n -> self (n - 1) + self (n - 2) in memo_rec fib --------------------