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 <[email protected]> wrote: > On Sat, Aug 21, 2010 at 6:52 PM, Michael D. Adams <[email protected]> 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! > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
