From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA20622; Sat, 12 Apr 2003 16:34:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA20636 for ; Sat, 12 Apr 2003 16:34:17 +0200 (MET DST) Received: from flamingo.mail.pas.earthlink.net (flamingo.mail.pas.earthlink.net [207.217.120.232]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h3CEYF922281 for ; Sat, 12 Apr 2003 16:34:16 +0200 (MET DST) Received: from user-0cev2t6.cable.mindspring.com ([24.239.139.166] helo=[192.168.0.3]) by flamingo.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 194M4w-00030l-00; Sat, 12 Apr 2003 07:34:02 -0700 Subject: Re: [Caml-list] [q] on implementing of "memoization" From: "Yaron M. Minsky" To: SooHyoung Oh Cc: Caml List In-Reply-To: <000e01c30091$b66bc580$fe00a8c0@hama> References: <000e01c30091$b66bc580$fe00a8c0@hama> Content-Type: text/plain Organization: Cornell University Message-Id: <1050158041.12890.48.camel@dragonfly.localdomain> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-5) Date: 12 Apr 2003 10:34:01 -0400 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; yaron:01 minsky:01 yminsky:01 cornell:01 caml-list:01 memoization:01 memoized:01 bounded:01 memo:01 memoize:01 rec':01 generic:01 bug:01 faq:01 beginner's:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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