mail at nh2.me
Sun Oct 13 22:25:31 UTC 2013
On 13/10/13 21:42, AntC wrote:
>> 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).
I mean *exactly* what you say here.
ordNub behaves has the same behaviour as nub, while (Set.toList .
> [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
What do you mean?
ordNub is clearly in a different complexity class, and the benchmarks
that I provided show not only this, but also that ordNub is *always*
faster than nub, even for singleton lists.
More information about the Haskell-Cafe