ANN: Edison 1.2RC4
robdockins at fastmail.fm
Fri Jun 2 10:34:38 EDT 2006
On Jun 1, 2006, at 11:57 PM, Jim Apple wrote:
>> I am pleased to announce the 4th (and with any luck, final)
>> release candidate
>> for Edison 1.2. Edison is a library of efficient data structures for
> Based on Exercise 10.2 of Okasaki's book
> "Reimplement AltBinaryRandomAccessList so that cons, head, and tail
> all run in O(1) amortized time, using the type
> data RList a =
> | One a (RList (a,a))
> | Two a a (RList (a,a))
> | Three a a a (RList (a,a))"
> and the source for BinaryRandList at
> , I don't think the constant time bounds in the documentation are
> correct for this sequence type.
Ah, I see. I know we've discussed this implementation before, but it
didn't quite become apparent to me that the documentation was in
error. 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...
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Libraries