[GHC] #1218: Add sortNub and sortNubBy to Data.List

[GHC]

#1218: Add sortNub and sortNubBy to Data.List
----------------------------+-----------------------------------------------
 Reporter:  neil            |          Owner:         
     Type:  proposal        |         Status:  closed 
 Priority:  normal          |      Milestone:  Not GHC
Component:  libraries/base  |        Version:  6.8.2  
 Severity:  normal          |     Resolution:  wontfix
 Keywords:                  |     Difficulty:  Unknown
 Testcase:                  |   Architecture:  Unknown
       Os:  Linux           |  
----------------------------+-----------------------------------------------
Changes (by guest):

 * cc: gwern0 at gmail.com (added)
  * version:  => 6.8.2
  * os:  Unknown => Linux

Comment:

 This may be abandoned, but I'm curious. Is this actually an optimization?
 I've been trying out some toy examples, and the 'map head . group . sort'
 version seems to perform absolutely terribly compared to just 'sort .
 nub', at least on my sample.

 Example:

 ----

 gwern at craft:15969~>cat tmp2.hs
 [ 9:58AM]
 import Data.List

 main = print $ uniq $ take 1000000000 $ cycle [1]

 uniq = sort . nub%
 gwern at craft:15970~>time runhaskell tmp2.hs
 [ 9:58AM]
 [1]
 runhaskell tmp2.hs  45.90s user 0.23s system 66% cpu 1:09.24 total
 gwern at craft:15971~>cat tmp4.hs
 [ 9:59AM]
 import Data.Set

 main = print $ uniq $ take  1000000000 $ cycle [1]

 uniq = toList . fromList
 gwern at craft:15974~>time runhaskell tmp4.hs
 [10:00AM]
 [1]
 runhaskell tmp4.hs  38.14s user 0.14s system 96% cpu 39.743 total
 gwern at craft:15975~>cat tmp3.hs
 [10:02AM]
 import Data.List

 main = print $ uniq $ take  1000000000 $ cycle [1]

 uniq = map head . group . sort
 gwern at craft:15976~>

 ----

 You'll understand if I don't provide timings for tmp3.hs (the map head
 implementation) since it takes vastly longer than 30 seconds and eats so
 much RAM and CPU time that it locks my system overnight.

 Admittedly, perhaps a list of repeated items is not the best usecase, but
 shouldn't optimizations - particularly optimizations in the base library
 be a win in all cases? (and particularly not huge pessimizations in some
 cases)?

 --
 gwern

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1218#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler