#2643: Optimized IntMap / IntSet construction from sorted input
---------------------------------+------------------------------------------
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
---------------------------------+------------------------------------------
Currently the "fromAscList" functions for building `IntMap`s and `IntSet`s
are aliases for `fromList`. Building a trie in linear time from sorted
input is not magic, and results in a considerable performance increase.
See this post:
http://www.haskell.org/pipermail/libraries/2008-May/009685.html
My impression was that the list generally approved of the patch, but for
some reason its never been applied so I'm creating a ticket for it here.
Tests are included in the patch. Really it just modifies an existing test
(which was `fromAscList xs == fromList xs`) so that it's no longer
vacuous.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2643>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
