Ticket #2645 (closed proposal: fixed)
fix type, performance of IntMap(Set).findMin(Max)
|Reported by:||sedillard||Owned by:||igloo|
|Type of failure:||Difficulty:||Unknown|
|Test Case:||Blocked By:|
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