[Haskell-cafe] ordNub

Niklas Hambüchen 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 .
Set.fromList) doesn't.

> [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 
> list.]

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 mailing list