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

I had a similar thought. That will probably do the trick. Jared. On 2/8/09, Svein Ove Aas wrote:

On Mon, Feb 9, 2009 at 8:02 AM, 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...?)

If your key is an instance of Enum, you can use succ/pred to work around that little problem.

On 2/8/09, Evan Laforge wrote:

I have a little util library with various map functions. 'within' is almost what you want, except it's half-open. You can make an inclusive one by pulling the lowest element off the above map.

I'm also curious if there's a better way to do this...

-- | Like Map.split, except include a matched key in the above map. split_map :: (Ord k) => k -> Map.Map k a -> (Map.Map k a, Map.Map k a) split_map k fm = (pre, post') where (pre, at, post) = Map.splitLookup k fm post' = maybe post (\v -> Map.insert k v post) at

-- | Split the map into the maps below, within, and above the given range. -- @low@ to @high@ is half-open, as usual. split3_map :: (Ord k) => k -> k -> Map.Map k a -> (Map.Map k a, Map.Map k a, Map.Map k a) split3_map low high fm = (below, within, way_above) where (below, above) = split_map low fm (within, way_above) = split_map high above

within low high fm = let (_, m, _) = split3_map low high fm in m

This looks right to me (correct time complexity). It should do what I need. I will test it and see what I discover. Thanks, Jared.