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

[Stephan Friedrichs]

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