interval :: k -> k -> Map k v -> Map k v
(k -> Ordering) -> Map k v -> Map k v
Yes. But I think what you need to efficiently implement this is some sort of implicit cut, of the form (k -> Something) -> Map k v -> (Map k v, Map k v).
The reason you might not be able to provide the keys yourself is that you can't (efficiently or at all) decide the exact right cutoff value, but you can provide a function that tells whether a key is too high, or too low, or in-range? That makes sense to me. I've even had cases where I wished there was a lookup that didn't require me to convert the key I was trying to look up, into the same type. I guess it would be unsafe though, since then the Map can't guarantee that it's a monotonic function relative to the (compare :: k -> k -> Ordering) that it typically uses -Isaac