English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
AW: [Caml-list] 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 (11:39)
From: Jean-Christophe Filliatre <filliatr@l...>
Subject: Re: AW: [Caml-list] Map.fold behavior changed

Bauer, Christoph writes:
 > What about to provide a "fold_left" (= new version) and "fold_right" 
 > (= old version)? Fixing old programs would be simple. Combined with 
 > exceptions there would be a fast solution (O(1) instead of O(n)) 
 > to find a minimum and maximum key from a large map.

It would  be O(log(n)), not O(1),  since you still need  to descend to
the leftmost (resp. rightmost) element in a binary search tree to find
the minimum (resp. maximum) element.

Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)