filter on map

[Christophe Raffalli <christophe.raffalli@univ-savoie.fr>]

Dear list members

I just write this piece of code because I wanted filter on map:

module Map_Label = struct
   module M =  Map.Make(Label)
   include M

   let filter f m =
     M.fold (fun k v m ->
       if f k then M.add k v m else m) m M.empty
end

But I am now wondering: this is O(n ln n), isn't there an O(n) implementation (or just a faster
implementation). This code insert the keys in increasing order which is the worst case for balancing 
? Just using a "random_fold" should make things better ...

What do you think ?

Cheers,
-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI