#2645: fix type, performance of IntMap(Set).findMin(Max)
---------------------------------+------------------------------------------
Reporter: sedillard | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries (other)
Version: 6.8.3 | Severity: normal
Keywords: containers | Testcase:
Architecture: Unknown/Multiple | Os: Unknown/Multiple
---------------------------------+------------------------------------------
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
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2645>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs