English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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

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