Isaac Dupree wrote:
[...]
Well Chris Okasaki called them "Skew Binary Random-Access Lists", which is even longer :)
:)
hmm.. IndexableList? (just a thought, not sure whether I like it any better)
RAList? IList? <- (will I be sued by a large computer company for that?)
[...]
Yes, I wasn't happy with that one either. The view-concept of Data.Sequence is a good idea.
yeah, it's a good idea, although I'm not sure how much I like the particular syntax of how it's done in Data.Sequence (the view-types' constructor names, mostly)
I now have data View a = Empty | Cons a (RandomAccessList a) and view :: RandomAccessList a -> a additionally, I renamed "extractHead" to "uncons" (which is OK, because I also have "cons") but still left "head" and "tail" with the typical list-like behaviour (causing an error on empty lists).
[Monad vs. Maybe]
That's quite convincing, most of all that "fail" has rather strange definitions for many Monads (because it originally does not belong to monads, does it?).
[...]
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.
sounds good
[...]
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.
okay, that sounds like a fair optimization, since zipping same-size lists is a nice thing to do anyway. But the asymptotic speed ideally should still be O(min(m,n)), if possible?
Well... I guess that's possible converting the shorter one into a list and using fold for zipping. I'll have a close look at this! -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr