#4086: Data.List 'nub' function is O(n^2)
---------------------------------+------------------------------------------
Reporter: Pete | Owner:
Type: bug | Status: new
Priority: normal | Milestone: 6.14.1
Component: libraries/base | Version: 6.12.1
Keywords: | Difficulty: Easy (less than 1 hour)
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: Documentation bug
---------------------------------+------------------------------------------
Changes (by simonmar):
* difficulty: => Easy (less than 1 hour)
* milestone: => 6.14.1
* os: Linux => Unknown/Multiple
* architecture: x86 => Unknown/Multiple
* failure: Runtime performance bug => Documentation bug
Comment:
Given nub's type, the best complexity it can have is O(n^2). See #2717
for a proposal (currently abandoned) to add a different `nub` with O(n log
n) complexity to `Data.Set`.
You're quite right that the docs should be improved here, so I'll leave
the ticket open. If you want to consider adopting #2717, that would be a
worthwhile step I think.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4086#comment:1>
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
