Opened 11 years ago

Closed 8 years ago

Last modified 8 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: 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 11 years ago by jpbernardy

  • Description modified (diff)

comment:2 Changed 10 years ago by igloo

  • Milestone set to 6.8
  • Test Case set to N/A

comment:3 Changed 10 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 9 years ago by jpbernardy

  • Milestone changed from 6.8 to Not GHC

comment:5 Changed 8 years ago by igloo

  • Resolution set to wontfix
  • Status changed from new to closed

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

comment:6 Changed 8 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:7 Changed 8 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple
Note: See TracTickets for help on using tickets.