From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA25535; Sun, 23 Jun 2002 23:18:43 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA25151 for <caml-list@pauillac.inria.fr>; Sun, 23 Jun 2002 23:18:42 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g5NLIVj07296;
	Sun, 23 Jun 2002 23:18:31 +0200 (MET DST)
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA25411; Sun, 23 Jun 2002 23:18:30 +0200 (MET DST)
From: Pierre Weis <pierre.weis@inria.fr>
Message-Id: <200206232118.XAA25411@pauillac.inria.fr>
Subject: Re: [Caml-list] Memoizing (was: static variables...)
In-Reply-To: <3D10986D.2060801@ozemail.com.au> from John Max Skaller at "Jun 20, 102 00:42:53 am"
To: skaller@ozemail.com.au (John Max Skaller)
Date: Sun, 23 Jun 2002 23:18:30 +0200 (MET DST)
Cc: wlovas@stwing.upenn.edu, caml-list@inria.fr
X-Mailer: ELM [version 2.4ME+ PL28 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

> let fib = ref (function | _ -> 1);;
> fib := function  | 0 | 1 -> 1 | n-> !fib (n-1) + !fib (n-2) ;;
> let memo h f x = (if not (Hashtbl.mem h x) then Hashtbl.add h  x (f x); 
> Hashtbl.find h x);;
> let h = Hashtbl.create 97;;
> fib := memo h !fib;;
>
> John Max Skaller, mailto:skaller@ozemail.com.au

A slightly more functional way of defining a memo function (i.e. with
no ref to define the memoized function):

let memo f =
  let h = Hashtbl.create 11 in
  fun x ->
    try Hashtbl.find h x with
    | Not_found ->
        let r = f x in
        Hashtbl.add h x r;
        r;;

open Lazy;;

let fib =
  let rec f =
    lazy (memo (
    function
    | 0 | 1 -> 1
    | n -> force f (n - 1) + force f (n - 2))) in
  force f;;

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners