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