[Haskell-cafe] lazy skip list?

[Michael D. Adams]

In that case do you also need fast insert and delete?  I think both a
pure functional cons list and a pure functional skip list take O(N) to
insert an element or remove an element at position N (because you have
to re-cons the elements in front of it).  Also do suffixes need to
also be lists?  (e.g. the suffix of a cons list is always a list, but
getting suffix of an array requires allocating a whole new array.)

On Sat, Aug 21, 2010 at 5:00 PM, Evan Laforge <qdunkan at gmail.com> wrote:
> 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!
>