[Haskell-cafe] ordNub

AntC anthony_clayden at clear.net.nz
Sun Oct 13 20:42:13 UTC 2013

> Niklas Hambüchen <mail <at> nh2.me> writes:
> In sets, the order does not matter, while for nub it does.

Let's be careful here!. Niklas, when you say "order", do you mean:
* the _ordering_ from the Ord instance? Or
* the relative sequence of elements in the list?

> ... the fact that Set is used inside my proposed 
> ordNub implementation is a detail not visible to the caller.

If you use the Set library, that fact may be very visible!
Because Set re-sequences the whole list, as per its Ord instance.

But List.nub preserves the list sequence (except for omitting duplicates).

Furthermore, the Ord instance might compare two elements as EQ, even 
though their Eq instance says they're not equal.

So a Set-based ordNub could end up returning:
* not the same elements as List.nub
* and/or not in the same list sequence

I'd call that very much *visible* to the caller.

> That's why it looks like a Data.List function to me.

[BTW I am still less than convinced that overall a Set-based ordNub is 
significantly more efficient. I suspect it depends on how big is your 

More information about the Haskell-Cafe mailing list