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 <dons@galois.com> wrote:
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