More problems with memoization
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Jon Harrop <jon@f...> 
Subject:  Re: [Camllist] More problems with memoization 
On Saturday 30 September 2006 19:01, Diego Olivier FERNANDEZ PONS wrote: > I wrote the following (classical) memoized code for the fibonacci > function and I have been unsuccessfully trying to generalize it with a > higher order function. > > let rec fib = function > >  0 > 0 >  1 > 1 >  n > fib_mem (n  1) + fib_mem (n  2) > > and fib_mem = > let table = ref [] in > function n > > try > List.assoc n !table > with Not_found > > let f_n = fib n in > table := (n, f_n) :: !table; > f_n > > # val fib : int > int = <fun> > # val fib_mem : int > int = <fun> > > It works: fib 35 answers instantaneously. > > Now I want to achieve the same result with a higher order function > [make_memo] and apply it to fib I believe you want to "untie the knot" of recursion, creating an higherorder, auxiliary fibonacci function fib_aux that accepts the recursive call as an argument: # let rec fib_aux fib = function  0  1 as n > n  n > fib(n  1) + fib(n  2);; val fib_aux : (int > int) > int > int = <fun> You can recover the ordinary fibonacci function using the Y combinator: # let rec fib n = fib_aux fib n;; val fib : int > int = <fun> You can write a higherorder memoization function that accepts an argument with the type of fib_aux: # let memoize f = let m = Hashtbl.create 0 in let rec f' n = try Hashtbl.find m n with Not_found > let x = f f' n in Hashtbl.replace m n x; x in f';; val memoize : (('a > 'b) > 'a > 'b) > 'a > 'b = <fun> Now you can memoize recursive functions easily: # memoize fib_aux 35;;  : int = 9227465  Dr Jon D Harrop, Flying Frog Consultancy Ltd. Objective CAML for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists