Apologies!
I was, in point of fact, working on such a patch, but I think I've been
convinced that it's a legitimate position for a package to take. (I'm also
curious, Johann, about the approach you figured out that didn't cost a word
per node!)
That said, I've been working with somewhat similar structures for my TrieMap
package, and I hadn't honestly considered the possibility of having size run
in anything but O(1). (When I was comparing benchmarks with
bytestring-trie, I didn't realize for a few hours that all of my benchmarks
called size, so O(W) operations were being benchmarked at O(n). That threw
me off..)
Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis
On Tue, Feb 22, 2011 at 4:28 PM, Don Stewart
bos:
On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman <[1]wasserman.louis@gmail.com> wrote:
size takes O(n). That's just depressing. Really.
That's rather thoughtless wording for some code that's (a) free (b) faster than anything else currently available (c) in its very first release and (d) available in source form for you to improve as you see fit. Just depressing. Really.
Agreed. This is open source: patches or it stays at O(n).
-- Don