Status of nubOrd (Proposal #2629)

[Bart Massey]

Isaac Dupree <isaacdupree <at> charter.net> writes:
> Bart Massey wrote:
> > 2) Stick (non-StopList) nubWith in Data.List.
> 
> >    Disadvantages:  Sticking nubOrd in Data.Set is weird.
> 
> indeed a weird location.  Would it be better to 
> stick it in a new module e.g. Data.Set.Nub?

Another possibility I considered is to stick nubOrd in Data.List.Nub.  As far as
I know, since containers depends on base and Data.Set depends on Data.List,
there's nothing preventing us from putting Data.List.Nub in containers even
though Data.List is in base.  Does someone know otherwise?

> only an import-line needs to 
> change if someone invents a super-duper nubOrd that's even 
> faster but depends on more libraries.

I believe that, given sufficient effort, I could prove that the nubOrd as given
is optimal in asymptotic complexity. The constant factors seem really good and
entirely dependent on those of the Set implementation.  So I'm not so worried
about a faster nubOrd. :-)


Leaving nubOrd in Data.Set does make a weird kind of sense; we put the various
nub* in whatever module their underlying stop list representation is in.  Thus
nubIx might go in Data.Array.  Also, it's less of a change to the existing
structure.

If we made a Data.List.Nub, presumably as more nub* implementations were added,
they would all pile in there.  One problem with this plan is that if someone
decides to write a nub* using a stop list from a module in a different package
that depends on containers, we're going to end up with the same circular
dependency problem we have now.


However, getting back to your original suggestion, I think it's also a little
weird to potentially have a bunch of modules with a special submodule containing
one function, so I guess I'd probably rather just stick it in Data.Set and be
done with it.  What do others think?