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

[Evan Laforge]

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

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