Version franēaise
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Map.fold behavior changed
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-02-24 (16:20)
From: Jean-Christophe Filliatre <filliatr@l...>
Subject: Re: [Caml-list] Map.fold behavior changed

Brian Hurt writes:
 > 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.

For  information, I  wrote an  implementation of  Set  using red-black
trees a long time ago. It is available here:

Note:  this  code was  even  formally  proved  correct using  a  proof
assistant. Getting Map from Set is rather straightforward.

I also did some benchmarks  to compare red-black trees, patricia trees
and  Ocaml AVLs  and, as  time is  concerned, the  AVLs  were (almost)
always the most efficient.

Jean-Christophe Filliātre (