[trac@galois.com: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List]

[Duncan Coutts]

On Wed, 2007-03-21 at 14:06 -0700, John Meacham wrote:
> On Mon, Mar 19, 2007 at 11:22:47AM +1100, Duncan Coutts wrote:

> note, this is most likely not what you want at all:
> 
> > >  {-# RULES
> > >  "sort/nub" sort . nub = map head . group . sort
> > >    #-}            
> 
> desugars to 
> > >  {-# RULES
> > >  "sort/nub" (.) sort nub = map head . group . sort
> > >    #-}            
> 
> meaning you are actually adding a RULE to (.), not sort or nub. this
> hasa couple of unfortunate consequences.

Yes, I know. I just wrote it that way for clarity.

> that said, I do not believe this is an appropriate use of rules to begin
> with, it changes the asymptotic complexity, so should be available as an
> explicit option, and is just a generally useful routine. not that rules
> can't also exist, but attached to the right thing.
> 
> (sort (nub xs)) = nubSort xs
> (nub (sort xs)) = nubSort xs

Though as several people pointed out these rules are sadly wrong in the
presence of dodgy Eq/Ord instances. :-(

> now, I would also like to see (and it might turn out to be more useful),
> 
> fastNub, which is a nub that uses Ord and sets to be just as fast, but
> works on infinite lists. accidentally evaluating a whole list in memory
> is the quickest way to a space leak and 'sort' is the most common
> culprit. this is why 'nub' can often be _faster_ than sortNub when you
> only partially evaluate a list, with ordNub, you get the benefits of
> both!

Yes. I guess I'm convinced. :-)

Duncan