[Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
wren ng thornton
wren at freegeek.org
Fri Feb 25 00:49:57 CET 2011
On 2/24/11 3:05 AM, Joachim Breitner wrote:
> Am Mittwoch, den 23.02.2011, 20:06 -0500 schrieb wren ng thornton:
>> On 2/23/11 4:42 PM, Sterling Clover wrote:
>>> A quick grep of some of my own source reveals that I've used M.size and S.size only to test for sizes equal to 1. So, for my purposes at least, an O(1) isSingleton operation would be just as useful as an O(1) size.
>> I agree, a fast isSingleton function would cover a very common use
>> case--- especially for set-like containers.
> would ghc’s rule system be strong enough to replace "size m == 1" by
> "isSingleton m"? It would be nice if programmers get the advantage even
> when they did not notice that a isSingleton function is provided.
Not really. I mean, yes, you could use rules for that; but it would be
fragile and susceptible to breakage due to refactoring.
Since maps are finite, you shouldn't get any changes in the domain
semantics (i.e., I believe that whether you hit bottom or not cannot
change based on whether rules fire), but you could get asymptotic
changes (since size is O(n) times whatever loop you're in) and you can
get memory leak changes as well (depending on whether CSE fires or not).
For me, allowing that much semantic variability based on whether rules
fire or not is unacceptable. This is why I disabled the rewrite rules in
Data.List.Extras.LazyLength (which, granted, is even worse since
infinite lists means that you can get domain semantic differences as well).
I'd rather advocate for having smart/lazy size comparison functions like
Data.List.LazyLength offers, advertising them well, and then relying on
users to say what they mean.
More information about the Haskell-Cafe