Re: [Haskell-cafe] lazy skip list?

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 wrote:

On Sat, Aug 21, 2010 at 6:52 PM, Michael D. Adams 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!