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