On 2/8/09, Anish Muttreja <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 > > [email protected] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > > > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
