[Haskell-cafe] Re: [Haskell] ANN: random-access-list-0.1

[Ross Paterson]

On Wed, Jun 11, 2008 at 08:56:17PM -0400, Isaac Dupree wrote:
> Stephan Friedrichs wrote:
>> I've implemented Chris Okasaki's random-access list[1] which provides  
>> typical list operations (cons, head, tail) in O(1) and yet offers  
>> indexed random-access in O(log n). It's uploaded on hackage[2].
>>
>> It's still an early version which I'll extend, but especially at this  
>> eary stage I'd appreciate your feedback concerning what's still missing 
>> / to be fixed / to be improved.
>
> Great to see it, it deserved implementing, IIRC!  I don't remember  
> enough about it.. (and don't have Okasaki anywhere handy). Can it be  
> lazy or infinitely long? (Data.Sequence can't, but it's fast on both  
> ends and has fast concatenation.)  Anyway, document that.  If it can't  
> be lazy/infinite, does it have any advantage over using  
> Data.Sequence?(constant factor of speed?, possible operations?,  
> something I'm forgetting?)

The O(1) size function settles the finiteness question.

In tests we did for the finger tree paper, we found that skew binary
random access lists are 1.6-1.7 times faster than Data.Sequence for
stack operations and indexing, but not much faster for updates.

foldr is defined using foldr' on lists, introducing strictness without
the user asking for it.  In any case, it would be better to define
the Foldable instance directly over the internal structure.  Then you
wouldn't need toList.  A similar Traversable instance would also be a
good idea.

> Why is zip slow with unbalanced lists?  Obviously, it could be  
> implemented O(min(m,n)*(log m + log n)) just indexing each one, which  
> would be faster for really unbalanced-size lists...

It could be made O(min(m,n)) by toListing the longer one and traversing
the shorter one adding corresponding elements from the list.

I agree about using Maybe instead of Monad, and would generally prefer
view functions to null/head/tail combinations.