[Haskell-cafe] lazy skip list?

[Evan Laforge]

On Sat, Aug 21, 2010 at 6:52 PM, Michael D. Adams <mdmkolbe at gmail.com> wrote:
> 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?

Good questions.  It's just generated in one long iterative process (as
a complex but lazy transformation of another long list), and then I
want to seek to various points and read sequentially (think about
music, seeking to a particular spot and then playing).  Sections are
then recomputed and spliced in (i.e., if you modify a bit of music in
the middle, it recomputes that range of time and splices it in).  The
laziness is that I don't want to compute too far into the future, and
it will be common to recompute the entire tail, but never actually
need that tail before it needs to be tossed and recomputed again.

Currently, I think I've solved my problem by just using a list of
chunks.  I already use the chunks as the units of recomputation, and
since each one accounts for n seconds, seeking to a particular spot or
replacing a chunk out of the middle should be plenty fast with a plain
list.  If each chunk is 5 sec, 3 hours of music is still only a list
of 2160 elements, and '[0..] !! 2160' is basically instant.  It looks
like I need to get up to around 5120000 or so before I can even notice
the delay, in plain old interpreted ghci.  Lists are fast!