[Haskell-cafe] lazy skip list?

[Evan Laforge]

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.