On 16/07/2013, at 3:21 PM, Clark Gaebel wrote: > > I'm still against having an Ord version, since my intuition tells me > that hash-based data structures are faster than ordered ones.
There are at least four different things that "an Ord version" might mean: - first sort a list, then eliminate duplicates - sort a list eliminating duplicates stably as you go (think 'merge sort', using 'union' instead of 'merge') - build a balanced tree set as you go - having a list that is already sorted, use that to eliminated duplicates cheaply. These things have different costs. For example, if there are N elements of which U are unique, the first as O(N.log N) cost, the third has O(N.log U) cost, and the fourth has O(N) cost. What I want is more often ordNubBy than ordNub, though. > 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? Since Ord has Eq as a superclass, and since 0 is a functionally correct hash value for anything, if you can implement Ord you can obviously implement Hashable/Eq. Whether it is *useful* to do so is another question. It turns out that it _is_ possible to define good quality hash functions on sets, but most code in the field to do so is pretty bad. (Just a modular sum or exclusive or.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
