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/Dat... -- Live well, ~wren