Version franēaise
Home     About     Download     Resources     Contact us    
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: -- (:)
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)