[Haskell-cafe] sort . nub (was Re: how to generate source code from TH Exp?)

[Daniel Fischer]

On Sunday 15 May 2011 15:32:03, Herbert Valerio Riedel wrote:
> On Thu, 2011-05-12 at 19:31 +0200, Daniel Fischer wrote:
> > > Minor nitpick:  instead of doing 'sort . nub', please use 'import
> > > qualified Data.Set as S' and do 'S.toAscList . S.fromList'.  This
> > > should be a lot faster.
> > 
> > Or `map head . group . sort', which may be faster than building an
> > intermediate Set (haven't benchmarked, may be faster, slower or mkae
> > no difference).
> 
> if the input list has _many_ duplicates, wouldn't using 'map head .
> group . sort' require more memory than going the 'toAscList . fromList'
> way?

Good point. Yes, it would (consider `replicate maxBound 1').
So `map head . group . sort' might be faster for lists with few duplicates, 
but it has worse worst-case complexity, so it's safer to use `toAscList . 
fromList'. Even in the where it's slower, it probably wouldn't make too 
much of a difference.