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
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-09-30 (08:51)
From: Jan Kybic <kybic@f...>
Subject: Re: [Caml-list] Memoization
> While searching Google for info about memoization I found this

Hope this helps: A very simple memoization (not written by me) is 

   (* [memo f] creates a memoized version of a single parameter function [f]  *)
   val memo : ('a -> 'b) -> ('a -> 'b) 

   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 ) 

This can be extended to function of two parameters as follows:

   let memo2 f = curry ( memo ( uncurry f ) )                        

   let uncurry f (x,y) = f x y

   let curry f x y = f (x,y) 

I further implemented a memoization system for my application based on
hash tables which also allows selective forgetting of cached values if
the memory is short. Let me know if you need it.


Jan Kybic <kybic@fel.cvut.cz>                       tel. +420 2 2435 5721
http://cmp.felk.cvut.cz/~kybic                      ICQ 200569450