Isaac Dupree wrote:
[...]
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?
No, it has to be finite as it's actually a list of complete binary trees whose size depend on the skew binary representation of the list's size. I'll document this.
[...]
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 "[]"?
Well Chris Okasaki called them "Skew Binary Random-Access Lists", which is even longer :)
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?) Good point!
"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) Yes, I wasn't happy with that one either. The view-concept of Data.Sequence is a good idea.
For "index", don't use Monad, use Maybe (I think that's what the
recent libraries@haskell.org discussion concluded, in the context of switching Data.Map back to Maybe). I was just copying the idea from Data.Map and it's usually a good thing to have functions as general as possible, or why is it not?
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
At the moment, I'm using the Int type for size and indexing only for one reason: I haven't found a proper way to generalize it. I'd really like to use the Ix class, but it doesn't provide enough functionality, it only works on fixed-size intervals (i. e. for arrays, which don't change their size, but a list does). Maybe someone has an idea of how to realize lists with a variable starting index and size? possible for these RandomAccessLists to be longer than maxBound::Int?)? The size function is in O(1) because I cache it, otherwise it would be size (RandomAccessList xs) = sum (map fst xs) which is O(log n). I consider the caching useful, as most applications will check 0 <= i < size quite often.
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
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)
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 If two lists have exactly the same size, all the complete binary trees holding the data have the same size as well. This can be zipped directly and is a bit (~5% in my tests) faster. list? Oh, you're right, I just meant to mark the Int strict. It obviously was too late yesterday! Thanks for this feedback! //Stephan -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr