[Haskell-cafe] ordNub

[Clark Gaebel]

I'm procrastinating something else, so I wrote the patch to
unordered-containers. Feel free to comment on the github link:

https://github.com/tibbe/unordered-containers/pull/67

I'm still against having an Ord version, since my intuition tells me
that hash-based data structures are faster than ordered ones. Someone
else can write the patch, though!

As a tangent, can anyone think of a data structure for which you can
write an Ord instance but Hashable/Eq is impossible (or prove
otherwise)? How about the converse?

Regards,
  - Clark

On Mon, Jul 15, 2013 at 10:40 PM, John Lato <jwlato at gmail.com> wrote:
> On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic
> <ivan.miljenovic at gmail.com> wrote:
>>
>> On 16 July 2013 11:46, John Lato <jwlato at gmail.com> wrote:
>> > In my tests, using unordered-containers was slightly slower than using
>> > Ord,
>> > although as the number of repeated elements grows unordered-containers
>> > appears to have an advantage.  I'm sure the relative costs of comparison
>> > vs
>> > hashing would affect this also.  But both are dramatically better than
>> > the
>> > current nub.
>> >
>> > Has anyone looked at Bart's patches to see how difficult it would be to
>> > apply them (or re-write them)?
>>
>> If I understand correctly, this function is proposed to be added to
>> Data.List which lives in base... but the proposals here are about
>> using either Sets from containers or HashSet from
>> unordered-containers; I thought base wasn't supposed to depend on any
>> other package :/
>
>
> That was one of the points up for discussion: is it worth including a subset
> of Set functionality to enable a much better nub in base?  Is it even worth
> having Data.List.nub if it has quadratic complexity?
>
> As an alternative, Bart's proposal was for both including ordNub in
> containers and an improved nub (with no dependencies outside base) in
> Data.List.  Unfortunately the patches are quite old (darcs format), and I
> don't know how they'd apply to the current situation.