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=none autolearn=disabled version=3.1.3 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id D4D69BC6B for ; Thu, 29 Nov 2007 09:37:36 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADYJTkfAXQInh2dsb2JhbACPRQEBAQgKKQ X-IronPort-AV: E=Sophos;i="4.23,228,1194217200"; d="scan'208";a="6299541" Received: from concorde.inria.fr ([192.93.2.39]) by mail3-smtp-sop.national.inria.fr with ESMTP; 29 Nov 2007 09:37:36 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id lAT8bZ83018407 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Thu, 29 Nov 2007 09:37:36 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADYJTkeBrw8Edmdsb2JhbACPRQEK X-IronPort-AV: E=Sophos;i="4.23,228,1194217200"; d="scan'208";a="4723831" Received: from ext.lri.fr ([129.175.15.4]) by mail2-smtp-roc.national.inria.fr with ESMTP; 29 Nov 2007 09:37:35 +0100 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id D01B1A485D; Thu, 29 Nov 2007 09:37:35 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at lri.fr Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UCAhOaHE7pJI; Thu, 29 Nov 2007 09:37:35 +0100 (CET) Received: from [129.175.4.117] (lri4-117 [129.175.4.117]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ext.lri.fr (Postfix) with ESMTP id B6056A4634; Thu, 29 Nov 2007 09:37:35 +0100 (CET) Message-ID: <474E7CA3.2050008@lri.fr> Date: Thu, 29 Nov 2007 09:47:31 +0100 From: =?UTF-8?B?SmVhbi1DaHJpc3RvcGhlIEZpbGxpw6J0cmU=?= User-Agent: Thunderbird 1.5.0.14pre (X11/20071023) MIME-Version: 1.0 To: Evan Klitzke Cc: peng.zang@gmail.com, caml-list@inria.fr Subject: Re: [Caml-list] Help with simple ocaml memoization problem References: <200711290053.15443.peng.zang@gmail.com> In-Reply-To: X-Enigmail-Version: 0.94.2.0 OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 474E7A50.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; filliatre:01 lri:01 ocaml:01 memoization:01 hashtbl:01 hashtbl:01 implements:01 inserting:01 implements:01 hash:01 backtracking:01 hash:01 logarithmic:01 lri:01 filliatr:01 Evan Klitzke wrote: > One question that I have is what is the difference > between the Map and Hashtbl modules? From the documentation they look > very similar -- why did you use Hashtbl here rather than Map? Hashtbl implements an imperative data structure i.e. association tables which are modified in-place when inserting, removing, etc. On the contrary, Map implements a persistent data structure i.e. tables which are not modified when you perform operations; instead, new tables are returned, the previous ones being unchanged. (This can be seen in the types Hashtbl.add : ('a, 'b) Hashtbl.t -> 'a -> 'b -> unit SomeMap.add : key -> 'a -> 'a t -> 'a t Here you can see the return type unit for hash tables, and the return type 'a t for the maps.) There are many cases where persistence can help improving your code: backtracking, sharing between several data structures, clarity and correctness of the code, etc. In the case of this particular example, however, the use of a hash table is perfectly fine, as demonstrated by Peng. With a good hash function, insertion in a hash table typically runs in constant time, while insertion in a map has logarithmic cost. But don't be misleaded by this performance comparison: persistence has so many advantages that it is often the case that you want to pay this extra cost. -- Jean-Christophe Filliâtre http://www.lri.fr/~filliatr/