Version française
Home     About     Download     Resources     Contact us    
Browse thread
Objective Caml release 3.08.2
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jon Harrop <jon@j...>
Subject: Re: [Caml-list] Objective Caml release 3.08.2
On Thursday 25 November 2004 18:05, Frédéric 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. 
Consequently, when implementing a set data structure, the mathematical notion 
of a set is often supplemented with the added assurances that many functions 
over the set will operate in-order. This is typically achieved by 
implementing the set as a red-black balanced binary tree.

Other useful set implementations which do not present elements in-order are 
possible, most notably a hashed set because it has significantly better 
average-case performance.

Cheers,
Jon.