[Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library

[wren ng thornton]

On 2/24/11 3:05 AM, Joachim Breitner wrote:
> Hi,
>
> 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[1] (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.


[1] 
http://hackage.haskell.org/packages/archive/list-extras/0.4.0.1/doc/html/Data-List-Extras-LazyLength.html

-- 
Live well,
~wren