Version française
Home     About     Download     Resources     Contact us    
Browse thread
Memoization
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
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

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