[Haskell-cafe] ordNub

[Niklas Hambüchen]

On 14/10/13 03:20, AntC wrote:
> Thanks Niklas, I hadn't spotted those benchmarks back in July.

No worries :)

> I'm surprised at that result for singletons 
> (and for very small numbers of elements which are in fact each different).

I think one of the main reasons for the performance difference is that a
list node and a Set binary tree node have pretty much the same
performance, with the difference that in


http://hackage.haskell.org/package/containers-0.5.2.1/docs/src/Data-Set-Base.html

   data Set a = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) | Tip

there are strictness and unpack annotations, while for

   data [a] = [] | a : [a] -- pseudo syntax

there are not.

Good for us in this case, I guess.

> It seems to me that for small numbers, the Set-based approach still 
> requires comparing each element to each other.

This I don't understand.

> Then here's a further possible optimisation, instead of making separate 
> calls to `member` and `insert`:

This I understand again. Where do you get insert' from? containers
doesn't seem to have it. Do you suggest adding it?

Niklas