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