Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Memoizing (was: static variables...)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-06-18 (19:05)
From: Jacek Chrzaszcz <chrzaszc@m...>
Subject: Re: [Caml-list] Memoizing (was: static variables...)
> Unfortunately, this is not a very general solution.  I suspect a
> general solution, like for example Mark-Jason Dominus's Perl module 
>, 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

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


PS. In caml you can write anything ;)
To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: