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
filter on map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-06-07 (08:27)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: filter on map
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

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 ?

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