Re: [Caml-list] Memoizing (was: static variables...)

[Jacek Chrzaszcz <chrzaszc@mimuw.edu.pl>]

> 
> 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