[Haskell-cafe] lazy skip list?

[Felipe Lessa]

On Fri, Aug 20, 2010 at 12:49 AM, Ivan Lazar Miljenovic
<ivan.miljenovic at gmail.com> wrote:
> How about fromList [1..] like Evan's original email had (which I think
> is going to be a problem here as well)?

The only "problem" is that the Element's sizes will be forced up to
the point you need, but not anymore.

*Main> (fromList [1..] :: SkipList Z Int) `index` 100
Just 101

Probably this small problem could be removed if the code was polished.

Alas, the idea is simple.  Each 'Element' contains up to 2^(s-1) data.
 For example, with an 'Element Z a' you can't store anything.  With an
'Element (S Z) a' you may store zero or one datum.  With an 'Element
(S (S Z)) a', you may store between 0 and 4 data, and so forth.

Then we just create an SkipList so that the Elements have an
increasing capacity.  When you 'Cons', the 'Element' of tail of the
SkipList will have twice more capacity than the 'Element' of the head.

However, I haven't thought about how operations such as 'cons' and
'tail' would be implemented =).  OP just asked about indexing ;-).

Cheers! =D

-- 
Felipe.