On Mon, Feb 9, 2009 at 2:57 PM, Jared Updike
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?
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