fix type, performance of IntMap(Set).findMin(Max)
The findMin / findMax functions for Data.IntMap currently return only the bound value, not the key, as is the case for Data.Map.findMin.
These read-only queries are implemented using maxView
which modifies the tree along the path from the root to the leaf, burning heap unnecessarily. I've provided a patch to implement these as simple recursive loops, as is done with Data.Map.
Both of these issues impact the performance and usability of IntMaps when employed as purely functional arrays, maps from arbitrary ints to values. In this use case, I need to know what the range of used "addresses" is, so I can assign new ones for quickly appending items onto the front or back of the array, or offsetting the keys of one array before unioning it with another.
See list post : http://www.haskell.org/pipermail/libraries/2008-May/009687.html
Trac metadata
Trac field | Value |
---|---|
Version | 6.8.3 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries (other) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |