From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=UNPARSEABLE_RELAY autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 755ACBC68 for ; Sat, 30 Sep 2006 10:51:24 +0200 (CEST) Received: from relay.felk.cvut.cz (relay.felk.cvut.cz [147.32.80.7]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k8U8pH0T016674 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 30 Sep 2006 10:51:24 +0200 Received: from k333.felk.cvut.cz (k333.felk.cvut.cz [147.32.87.5]) by relay.felk.cvut.cz (8.13.8/8.13.8) with ESMTP id k8U8oi8r073748; Sat, 30 Sep 2006 10:50:55 +0200 (CEST) (envelope-from kybic@fel.cvut.cz) Received: from K333/SpoolDir by k333.felk.cvut.cz (Mercury 1.48); 30 Sep 06 10:50:57 +0100 Received: from SpoolDir by K333 (Mercury 1.48); 30 Sep 06 10:50:40 +0100 Received: from localhost (147.32.84.19) by k333.felk.cvut.cz (Mercury 1.48) with ESMTP; 30 Sep 06 10:50:34 +0100 To: Erik de Castro Lopo Cc: caml-list@inria.fr Subject: Re: [Caml-list] Memoization References: <20060909103332.0397efea.mle+ocaml@mega-nerd.com> Reply-To: Jan Kybic From: Jan Kybic In-Reply-To: <20060909103332.0397efea.mle+ocaml@mega-nerd.com> Date: 30 Sep 2006 10:49:55 +0200 Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-FELK-MailScanner-Information: X-FELK-MailScanner: Found to be clean X-FELK-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-2.598, required 5, autolearn=not spam, BAYES_00 -2.60, UNPARSEABLE_RELAY 0.00) X-FELK-MailScanner-From: kybic@fel.cvut.cz X-Miltered: at discorde with ID 451E3005.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; memoization:01 memoization:01 memoized:01 val:01 hashtbl:01 hashtbl:01 hash:01 cached:01 caml-list:01 short:01 parameter:02 implemented:02 parameters:02 let:03 let:03 > 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 tel. +420 2 2435 5721 http://cmp.felk.cvut.cz/~kybic ICQ 200569450