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 Haskell.
Based on Exercise 10.2 of Okasaki's book
Roughly: "Reimplement AltBinaryRandomAccessList so that cons, head, and tail all run in O(1) amortized time, using the type
data RList a = Nil | One a (RList (a,a)) | Two a a (RList (a,a)) | Three a a a (RList (a,a))"
and the source for BinaryRandList at http://www.eecs.tufts.edu/~rdocki01/edison/_darcs/current/edison- core/src/Data/Edison/Seq/BinaryRandList.hs , 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...
Jim
Thanks, Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG