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

On 2/8/09, Anish Muttreja wrote:

Maybe you wantData.Map.partition (\key -> key >= key1 && key <= key2) map

This will return what I want, but partition is O(n) and touches all the keys, so if I had a million keys and only 2 of them matched the key1..key2 range, it would still visit all of them before it enumerated the ones that satisify the predicate. I don't believe laziness would help here.

HTH, Anish

On Sun, 08 Feb 2009 23:02:37 -0800, Jared Updike wrote:

...

It looks like two "Map.split"s will do what I need except for allowing more exact testing of <= vs. < (since == elements are left out of both maps...?)

Jared.

On 2/8/09, Jared Updike wrote:

...

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.

Jared.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe