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 VAA31938; Tue, 18 Jun 2002 21:05:01 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA31949 for caml-list@pauillac.inria.fr; Tue, 18 Jun 2002 21:05:00 +0200 (MET DST)
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 LAA16555 for <caml-list@pauillac.inria.fr>; Tue, 18 Jun 2002 11:16:32 +0200 (MET DST)
Received: from absurd.mimuw.edu.pl (fw-gw-atm.mimuw.edu.pl [193.0.96.15])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g5I9GUP01682
	for <caml-list@inria.fr>; Tue, 18 Jun 2002 11:16:30 +0200 (MET DST)
Received: (from chrzaszc@localhost)
	by absurd.mimuw.edu.pl (8.11.6/8.11.6) id g5I9GEN32462;
	Tue, 18 Jun 2002 11:16:14 +0200
Date: Tue, 18 Jun 2002 11:16:13 +0200
From: Jacek Chrzaszcz <chrzaszc@mimuw.edu.pl>
To: William Lovas <wlovas@stwing.upenn.edu>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Memoizing (was: static variables...)
Message-ID: <20020618111613.A30795@absurd.mimuw.edu.pl>
References: <87k7oyreva.dlv@wanadoo.fr> <200206171356.g5HDu5u19866@n05.sp.go.dlr.de> <20020618084006.GA8596@force.stwing.upenn.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.5.1i
In-Reply-To: <20020618084006.GA8596@force.stwing.upenn.edu>; from wlovas@stwing.upenn.edu on Tue, Jun 18, 2002 at 04:40:07AM -0400
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

> 
> Unfortunately, this is not a very general solution.  I suspect a
> general solution, like for example Mark-Jason Dominus's Perl module 
> Memoize.pm, requires a stateful environment (i think the Perl version
> uses code references).  The problem with an elegant O'Caml solution, i
> think, is that the inner recursive calls are part of the definition
> environment of the recursive function (i.e. part of the closure), and 
> there's no way to change them without writing a new function (and thus
> creating a new closure).
> 
> Does anyone have any thoughts on this?  Am i missing something obvious?
> 
> William

If you write it like this, it works:

let memoize f = 
  let hash = Hashtbl.create 20 in
  let rec f' a = 
    try Hashtbl.find hash a 
    with Not_found ->
      let b = f f' a in
	Hashtbl.add hash a b; b
  in
    f';;


let recfib recfib = function
  | 0 | 1 -> 1
  | n -> recfib (n-1) + recfib (n-2);;                                      

let fib = memoize recfib;;


Now fib 30 is instantaneous! The clue is to contruct a new
hash and a new recursive function once for each application of
memoize.

Jacek

PS. In caml you can write anything ;)
-------------------
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