[GHC] #2629: Data.List: Replace nub; add nubOrd, nubInt, nubWith

[GHC]

#2629: Data.List: Replace nub; add nubOrd, nubInt, nubWith
----------------------------+-----------------------------------------------
    Reporter:  Bart Massey  |       Owner:                
        Type:  proposal     |      Status:  new           
    Priority:  normal       |   Component:  libraries/base
     Version:               |    Severity:  minor         
    Keywords:               |    Testcase:                
Architecture:  Multiple     |          Os:  Multiple      
----------------------------+-----------------------------------------------
 Everyone always complains about nub, but nobody ever does anything about
 it except (map head . group . sort), which isn't lazy and isn't always
 faster. :-)

 I've implemented a new function nubWith that takes a "stop list" as an
 argument and filters its target list against the stop list.  I've then re-
 implemented nub and implemented nubOrd and nubInt in terms of nubWith: the
 stop list is a typeclass, so these implementations are trivial and new
 implementations are easily added.  nubBy is left alone, since there's
 nothing obvious to be done about it. All of the nubs are still fully lazy.

 Basic !QuickCheck tests are provided, and pass.

 Performance benchmarking code is provided.  The performance of my nub
 implementation is quite comparable to that of the standard one.  My nubOrd
 and nubInt implementations are dramatically faster, since they use a Set
 and !IntSet respectively for the stop list.  In particular, they are
 performant on long lists with long nubs, unlike the basic nub.

 My implementation is available via git at
   git://svcs.cs.pdx.edu/git/nub.git
 or can be browsed at
   http://svcs.cs.pdx.edu/gitweb?p=nub.git;a=tree and has a maybe-outdated
 tarball at
   http://svcs.cs.pdx.edu/haskell/nub.tar.gz
 The Nub.hs file itself is attached to this proposal. If the proposal is
 accepted, I will prepare a patch against current GHC library top-of-tree,
 but for now it seems easier for everyone to just look at the bits in their
 current natural habitat.

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