[Haskell-cafe] lazy skip list?

[Michael D. Adams]

Could you be more specific about what operations you want and their
properties (e.g. performance laziness, etc.)?  For example, do you
need to be able to cons onto the front or is the list generated once
and never consed onto?  Do you need to be able to insert/remove
elements from the middle?  Do you need the tail sharing property that
regular cons lists have?

Michael D. Adams

On Thu, Aug 19, 2010 at 9:22 PM, Evan Laforge <qdunkan at gmail.com> wrote:
> Is there a data type that's spine lazy like a list, but can be seeked (sought?)
> efficiently?  IntMap and Sequence are spine strict so if you take the head
> element all the elements are forced even if their contents are not.  E.g.,
> 'Sequence.index (Sequence.fromList [0..]) 0' will diverge, but obviously 'head
> [0..]' won't.  I can get what I want from a list of lists where the outer list
> is is 'iterate (drop n)' on the inner one... this is a kind of skip list,
> right?
>
> It seems like it should be possible to generalize this to multiple levels with
> increasing skip amounts, then I can seek relatively efficiently and won't force
> the spine beyond where I seek.  Effectively, this is nested list like [[[a]]],
> where each level above the bottom is something like 'iterate (drop n)
> level_below'.
>
> Alternately, it should also be possible to do something fancy like a
> self-modifying
> data structure that constructs its index as you force bits of it, but this
> would require some hairy unsafePerformIO, I think.
>
> Has anyone heard of a data structure like this, either the plain list of lists
> or the self modifying magic one?  Surely efficiently indexing a lazy list is
> something someone else has thought about?
>
> It looks like Luke Palmer's data-inttrie might be doing this, though it's not
> clear from the documentation.  It looks like it lacks emptiness, so it doesn't
> apply to finite structures.
>
> lazyarray looks like it might be doing the magic self-modifying thing, though
> it wants a a static bounds right off the bat, which isn't much help when the
> whole point is to avoid having to figure out how long the input is.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>