* AW: [Caml-list] Map.fold behavior changed
@ 2006-02-24 11:34 Bauer, Christoph
2006-02-24 11:39 ` Jean-Christophe Filliatre
0 siblings, 1 reply; 2+ messages in thread
From: Bauer, Christoph @ 2006-02-24 11:34 UTC (permalink / raw)
To: 'EEK Cooper', caml-list
Hi,
> My team just noticed that the behavior of Map.fold changed in OCaml
> version 3.08.4.
a program of mine suffers a lot from this change. In fact
my boss found today a remaining hidden bug related to this change :-(
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.
Christoph Bauer
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: AW: [Caml-list] Map.fold behavior changed
2006-02-24 11:34 AW: [Caml-list] Map.fold behavior changed Bauer, Christoph
@ 2006-02-24 11:39 ` Jean-Christophe Filliatre
0 siblings, 0 replies; 2+ messages in thread
From: Jean-Christophe Filliatre @ 2006-02-24 11:39 UTC (permalink / raw)
To: Bauer, Christoph; +Cc: 'EEK Cooper', caml-list
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)
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2006-02-24 11:39 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-02-24 11:34 AW: [Caml-list] Map.fold behavior changed Bauer, Christoph
2006-02-24 11:39 ` Jean-Christophe Filliatre
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).