From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 371F8BB81 for ; Fri, 24 Feb 2006 16:43:39 +0100 (CET) Received: from cenn.mc.mpls.visi.com (cenn.mc.mpls.visi.com [208.42.156.9]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k1OFhcqx028712 for ; Fri, 24 Feb 2006 16:43:38 +0100 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by cenn.mc.mpls.visi.com (Postfix) with ESMTP id 1851682E5; Fri, 24 Feb 2006 09:43:38 -0600 (CST) Date: Fri, 24 Feb 2006 09:43:43 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Damien Doligez Cc: caml-list Subject: Re: [Caml-list] Map.fold behavior changed In-Reply-To: <1AEDE2F4-2D83-416F-AFDC-7ECAF892BFBD@inria.fr> Message-ID: References: <20060224112209.51szurk2dc00oggg@www.sms.ed.ac.uk> <17406.61821.450737.625981@gargle.gargle.HOWL> <20060224132950.7l49sm2akg0sskkw@www.sms.ed.ac.uk> <1AEDE2F4-2D83-416F-AFDC-7ECAF892BFBD@inria.fr> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at concorde with ID 43FF29AA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 damien:01 unspecified:01 rec:01 node:01 rec:01 node:01 red-black:01 red-black:01 wrote:01 wrote:01 doligez:01 compile:01 functions:01 defined:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Fri, 24 Feb 2006, Damien Doligez wrote: > On Feb 24, 2006, at 14:29, EEK Cooper wrote: > >> Since the behavior was NOT unspecified, it was reasonable to assume that >> the >> documentation suffered from a simple typo, and to expect the behavior not >> to >> change. > > "It is documented to do something else, so we will assume that it's intended > to do what it does, instead of what the documentation says." > > I don't think this is very reasonable. OK, My stupid question was already answered. There are times, however, when a specified traversal ordering is required. Since a map is defined as an ordered tree, having a fold_left and fold_right functions would not be hard to do: let rec fold_left f init = function | Empty -> init | Node(l, v, d, r, _) -> fold_left f (f (fold_left f init l) v d) r let rec fold_right f node init = match node with | Empty -> init | Node(l, v, d, r, _) -> fold_right f l (f v d (fold_right f r init)) These aren't checked to see if they even compile, but they're close. I may take this opportunity to offer a red-black tree implementation of Map as a replacement, if people are interested. The advantage a red-black tree is that it uses one less word of memory per element in a map. Brian