[Haskell-cafe] Data.Map: Enumerating ordered subset of keys

Jared Updike jupdike at gmail.com
Mon Feb 9 01:57:23 EST 2009

I would like to enumerate a subset of keys in a Map satisfying \ key
>= key1 && key <= key2 but in the expected, reasonable amount of time
(e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset).
(Or key > key1 and/or key < key2 or some such combination).

Is there an appropriate idiom or combination of library functions to
accomplish this, short of digging into the code for Data.Map and
writing such a function for a forked version of Data.Map?

For example I could try something like a Set.split of a Set.split of
Map.keysSet of my original map, but will laziness magically do what I
really want? which is to walk down the tree to key1 (or the nearest
key > key1) and enumerate keys in order until key2 is reached?

Data.Map almost looks like what I need if I can do this.


More information about the Haskell-Cafe mailing list