[Haskell-cafe] Re: [Haskell] ANN: random-access-list-0.1
deduktionstheorem at web.de
Fri Jun 13 11:38:48 EDT 2008
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
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
| Cons a (RandomAccessList a)
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
More information about the Haskell-Cafe