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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
