Opened 12 years ago

Closed 9 years ago

Last modified 9 years ago

#720 closed feature request (wontfix)

Map/Set range function

Reported by: jpbernardy Owned by:
Priority: normal Milestone: Not GHC
Component: libraries/base Version: 6.4.1
Keywords: collections Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: N/A
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by jpbernardy)

Data.Map seems to lack a way to perform range queries like "fetch all elements between keys low and high". The naive implementation is easy:

range :: Ord k => k -> k -> Map.Map k v -> [(k,v)]
range low high = toList . fst . split high . snd . split low

But this is not very fast for larger maps. Maybe this operation could be provided in Data.Map?

Change History (7)

comment:1 Changed 12 years ago by jpbernardy

Description: modified (diff)

comment:2 Changed 11 years ago by igloo

Milestone: 6.8
Test Case: N/A

comment:3 Changed 11 years ago by dylan@…

More efficient versions of the related functions to find the values left or right of a key would be nice, too:

findMinBnd, findMaxBnd :: Ord k => k -> Map k v -> (k,v)
findMinBnd low = findMin . snd . split low
findMaxBnd high = findMax . fst . split high

comment:4 Changed 10 years ago by jpbernardy

Milestone: 6.8Not GHC

comment:5 Changed 9 years ago by igloo

Resolution: wontfix
Status: newclosed

Please follow the library submissions process if you'd like to propose these changes:

comment:6 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:7 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple
Note: See TracTickets for help on using tickets.