Consider adding a range function for Sets and Maps

[w9]

Maybe it's my ignorance, but currently I don't know if there's an succinct way to extract a range of elements from a set (in O(Log n) time). I know I can use split to achieve the effect:

import qualified Data.Set as S

-- The lower bound is inclusive and the upper bound is exclusive.
range' :: Ord a => (a, a) -> S.Set a -> S.Set a
range' (lower, upper) s = 
    let (_, e, right) = S.splitMember lower s
        (left, _)     = S.split upper right
    in  if e
          then S.union (S.singleton lower) left
          else left

main :: IO ()
main = do
    print $ range' (0, 3) (S.fromList [-1,2,0,1,5,6,3,7])
    return ()

-- output:
--   fromList [0,1,2]

But since this is a very common operation, can you add this function to the library? (For both Set and Map)

[foxik]

Hi,

I think using split is the only way to achieve what you want in logarithmic time.

As for adding a range function, containers API changes are usually discussed at the [email protected] mailing list. The reason is that containers API is already quite wide (and people frequently suggest functions to add), so we are careful about adding functions, and often choose not to add a function which can be easily composed. Nevertheless, I think range has a reasonable chance of being added.

If you are interested in this, please follow https://wiki.haskell.org/Library_submissions#Guide_to_proposers and start the discussion at [email protected].

Cheers,
Milan

[sjakobi]

Since there hasn't been any activity here for such a long time, and since the desired function seems fairly easy to implement with spanAntitone, I'll tentatively close this.

Please do reopen this issue if there's more to do here!

[sjakobi]

the desired function seems fairly easy to implement with spanAntitone,

Actually takeWhileAntitone and dropWhileAntitone might be more relevant.

[sjakobi]

#803 is related.