ANN: Edison 1.2RC4

[Robert Dockins]

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