Re: [Caml-list] [q] on implementing of "memoization"

["Yaron M. Minsky" <yminsky@CS.Cornell.EDU>]

One thing you might want to try to keep track of is exceptions.  That
way, if a given memoized function throws an exception the first time, it
will keep on throwing that exception.

Another aproach I've found useful is cached memoization. Ttahat is, you
maintain an LRU cache of bounded size for the memoization.    You can
have the memoization function return both a ref to the maximum cache
size (so you can change it later) and the actual memoized function.

y

On Fri, 2003-04-11 at 21:20, SooHyoung Oh wrote:
> In testing "memoization" of fib function, it is OK on
>     let rec fib = ... and memo_fib n = memoize fib n;;
> but it makes the ERROR on
>     let rec fib = ... and memo_fib = memoize fib;;
> 
> The error message is
>       This kind of expression is not allowed as right-hand side of `let rec'
> 
> Why does this error occur?
> I can't find good description on ocaml manual.
> 
> One more thing:
> Do you have any idea about ** generic ** and good implementation of
> memoization?
> 
> The source is
> ----------------------------------
> let lookup key table = List.assoc key !table;;
> let insert key value table = table := (key, value) :: !table;;
> 
> let table = ref [];;
> let memoize f n =
>     try
>         lookup n table
>     with
>     | Not_found ->
>         let result = f n in
>         insert n result table;
>         result
> ;;
> 
> let rec fib = function
>     | 0 -> 0
>     | 1 -> 1
>     | n -> memo_fib (n-1) + memo_fib (n-2)
> and memo_fib n = memoize fib n
> ;;
> ----------------------
> 
> Thanks a lot!
> 
> ---
> SooHyoung Oh
> 
> -------------------
> 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
-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



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