Re: More problems with memoization
 oleg@p...
[
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:  20061003 (05:10) 
From:  oleg@p... 
Subject:  Re: More problems with memoization 
Diego Olivier wrote: > When you compare your solution with what I am trying to do you see > there is a big difference in locality and transparency > > let rec fib = function >  0 > 0 >  1 > 1 >  n > fib (n  1) + fib (n  2) > > transformed into > > let rec fib = function >  0 > 0 >  1 > 1 >  n > fib_mem (n  1) + fib_mem (n  2) > and fib_mem = make_mem fib > > The latter could even be done automatically by a source to source > transformation (if it worked). But it almost does: let make_mem = fun table f > function n > try List.assoc n !table with Not_found > let f_n = f n in table := (n, f_n) :: !table; f_n ;; let rec fib = function  0 > 0  1 > 1  n > mem fib (n  1) + mem fib (n  2) and mem = make_mem (ref []) ;; fib 35;;  : int = 9227465 instantaneous. The biggest difference is replacing "fib_mem" in your code with "mem fib" in mine. The same number of characters in either case... And yes, this can be done via camlp4... OTH, with camlp4 it is quite trivial to convert a let rec expression to the one involving open recursion. So, we can write something like let fib n = funM MyModule n > let rec fib function 0 > 1 ... in fib n;; and, depending on what MyModule actually implements, obtain either the usual or the memoized Fibonacci (or even partially unrolled to any desired degree).