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

Isaac Dupree isaacdupree at charter.net
Wed Jun 11 20:56:17 EDT 2008

Stephan Friedrichs wrote:
> Hello,
> 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?)

Is "RandomAccessList" the best name for something that's not O(1), just 
O(log n)?  Or just that "RandomAccessList" is just much longer than "[]"?

don't use those unorthodox infix function names.. `cons` is hardly worse 
than .:. , `append` or `mappend` than .+. , and .!. than, hmm.. . 
Export a ++ and ! (!! ?) if you're really dedicated. But I'd prefer an 
`at` that's the same partial indexing operation, rather than the name 
.!. (I think this "at" was a new name being put somewhere else? partly 
because "!" is trying to be gradually used only to refer to strictness?)

"extractHead" is an ugly name for a nevertheless standardish-meaning 
function... what is it usually called? uncons? headTail? (Data.Sequence, 
which is meant to be left-right symmetric, calls it "viewr"... except 
your version doesn't have the Maybe, it's partial instead, fails on 
empty lists)

For "index", don't use Monad, use Maybe (I think that's what the recent 
libraries at haskell.org discussion concluded, in the context of switching 
Data.Map back to Maybe).  Also, Data.List has genericLength etc, to 
support.  Isn't "index" (like Data.List.genericIndex) supposed to be a 
name for a partial operation, not one that returns a Maybe?  Shouldn't 
"size" be named "length" (or exported as both names, since e.g. 
Data.Map.size, .List.length) (why is it O(1) not O(log n)? Is it 
possible for these RandomAccessLists to be longer than maxBound::Int?)?

for e.g. toList, is the O(n) cost spread over traversing/demanding the 
items of the generated list, or all up-front, or somewhere in between?

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...  Obviously, I don't 
understand the implementation.  BTW, looking at the file,
data RandomAccessList a
         = RandomAccessList {-# UNPACK #-} !Int ![(Int, CBTree a)]
Marking a list strict like that doesn't have much effect because it only 
makes the first (:) or [] strict. Did you mean for an element-strict or 
spine-strict(which would necessarily be non-infinite) list?


> Regards,
> Stephan
> [1] Chris Okasaki: "Purely Functional Data Structures"
> [2] 
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/random-access-list 

More information about the Haskell-Cafe mailing list