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

[Bertram Felgenhauer]

Neil Mitchell wrote:
[snip]
> I think its important when you are using an algorithm to say "I want
> to use an O(n log n) algorithm instead of an O(n^2) one" and have the
> compiler obey you unconditionally. If the compiler wants to replace
> the O(n^2) one as well, that is just groovy, but your big-O shouldn't
> depend on compiler specific rules.

I'd like to second Neil's opinion. In fact I think that switching
compilers shouldn't change the asymptotic complexity of programs. This
is already difficult enough in Haskell because it depends on what common
subexpressions a compiler decides to share.

In addition to this, I view Data.List as a rather low level library;
to me, writing 'nub xs' specifies an algorithm rather than a result.
Lists are a fundamental data structure for Haskell programs and fine
grained control about how they're processed is often essential. In
particular there may be cases where you actually want the naive
algorithm for nub, as we've seen in the discussion so far.

Another point is that Haskell is also meant to be a teaching language,
and list processing is likely a starting point for new coders. As such,
adding more magic to Data.List seems wrong to me, because it makes
understanding the library harder.

Personally, I'd like to see a sortNub function and a nubOrd function
(which doesn't change the order). Maybe rules for changing algorithms
could go to a different module, say  Data.List.Magic - for people who
want them.

Thanks for reading,

Bertram