nubOrd (Re: Performance horrors)

[Bart Massey]

IMHO the right way to think about nub is that it filters the
given list with a "stop list".  This code captures that
intuition, and allows new kinds of nubs to be quickly
constructed.  Don't know if anyone wants it, but I thought
I'd show it off, anyhow.

    nubWrt :: (StopList e s) => s -> [e] -> [e]
    nubWrt s [] = []
    nubWrt s (e : es) | memberS e s = nubWrt s es
    nubWrt s (e : es) = e : nubWrt (insertS e s) es

    nub :: (Eq e) => [e] -> [e]
    nub = nubWrt []

    nubOrd :: (Ord e) => [e] -> [e]
    nubOrd = nubWrt S.empty

    nubInt :: [Int] -> [Int]
    nubInt = nubWrt IS.empty

I've omitted the StopList class and instances, which are of
course crucial, but are kind of obvious.  Get the whole code at
  http://svcs.cs.pdx.edu/gitweb?p=nub.git;f=Nub.hs;hb=master
to see the details.

A day of painful fiddling with how to do benchmark timing
(there are three packages in Hackage and I couldn't figure
out how to use any of them) tells me that this version of
nub is about the same speed as the nub in Prelude
(unsurprisingly). This nubOrd is capable of running a list
of 10^7 elements, all different, in about 23 seconds on
my box; nubInt runs that list in about 5 seconds.  Plain old
nub runs a list of 10^5 elements, all different, in
about 70 seconds.  For small lists, or lists where many of
the elements are the same, everything's good: all the
functions are fast and about the same speed.  They all run
lists of 10^8 identical elements in around 5s, although it
turns out that the IntSet member test is close to twice as
fast as list elem.

I haven't QuickCheck tested anything, but my little tests
with ghci make me think the code is probably correct.

Hope this helps.

    Bart Massey
    bart at cs.pdx.edu