From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 2320BBC2F for ; Thu, 25 Nov 2004 22:44:00 +0100 (CET) Received: from ptb-relay01.plus.net (ptb-relay01.plus.net [212.159.14.212]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id iAPLhxOf005468 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 25 Nov 2004 22:44:00 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay01.plus.net with esmtp (Exim) id 1CXRPD-0007xt-5y for caml-list@yquem.inria.fr; Thu, 25 Nov 2004 21:43:59 +0000 From: Jon Harrop To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Objective Caml release 3.08.2 Date: Thu, 25 Nov 2004 21:47:30 +0000 User-Agent: KMail/1.6.2 References: <75E02BC8-3EEA-11D9-A6E2-00039310CAE8@inria.fr> <1101398012.9291.48.camel@pelican.wigram> <008001c4d319$693f0f40$b18780d9@mshome.net> In-Reply-To: <008001c4d319$693f0f40$b18780d9@mshome.net> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <200411252147.31167.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 41A6521F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 gava:01 wrote:01 red-black:01 binary:01 cheers:01 ric:98 ...:98 assurances:98 abstract:01 functions:01 data:02 tree:02 caml:02 balanced:02 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: On Thursday 25 November 2004 18:05, Fr=C3=A9d=C3=A9ric Gava wrote: > > > Why an order for the fold operator ? > > Because Set.t is an ordered container, > > Ok, but it is an abstract type : you do not know (except when you used > ocamlbrowser) how it works... The ability to fold over the elements of a set in order can be very useful.= =20 Consequently, when implementing a set data structure, the mathematical noti= on=20 of a set is often supplemented with the added assurances that many function= s=20 over the set will operate in-order. This is typically achieved by=20 implementing the set as a red-black balanced binary tree. Other useful set implementations which do not present elements in-order are= =20 possible, most notably a hashed set because it has significantly better=20 average-case performance. Cheers, Jon.