Re: ANN: Edison 1.2RC4

On Jun 2, 2006, at 10:31 AM, Jim Apple wrote:

On 6/2/06, Robert Dockins wrote:

...

Does Okasaki say what the bounds should be for this implementation? I imagine it's O(log n), but my lazy-amortized- complexity-analysis-fu isn't very good...

I don't have the book out from the library anymore. Anybody?

There's also a paper & a thesis he wrote covering much of the same material. Some of the bounds might be in there.

I'll look around and see what I can find. As I recall, he doesn't specifically mention the bounds for these operations for this implementation, but it's been a little while since I looked.

We should probably also check the other exercises in the book to make sure the other bounds listed in the Haddock documentation for the other data structures are correct.

That's a good idea. I'll do a quick audit before the release to see if I can spot any other obvious errors.

Jim

Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG