Re: [Haskell-cafe] ordNub

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 wrote:

On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic wrote:

...

On 16 July 2013 11:46, John Lato 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.