On Thu, Feb 17, 2011 at 7:27 AM, John Lato <[email protected]> wrote: > Does anyone know of a purely functional equivalent to a circular buffer? > I'm looking for something that supports efficient insertion and lookup, and > doesn't rely upon mutable data. I don't want to use mutable data because > I'd like to embed this in CCA, which to my knowledge doesn't yet support > Kleisli arrows. > So far the best I've found is Data.Sequence.Seq, which in my tests > outperforms mutable vectors, but only for reads from the head or tail of the > sequence. Indexing into the middle of the sequence is relatively slow. > Alternative approaches are also welcome.
I've thought about this a little. It seems to me that there is a pattern in step-based programs that I think should be exploitable to maintain pure semantics while keeping the advantages of mutable structures. As a general-purpose language, of course Haskell has to do the most general thing and assume that previously used memory may be referred to in the future as long as there remains a reference to it. However, there is this common pattern in media- or simulation-oriented programs (like games too): 1. Initialize state. 2. Update state based on initial state. 3. Update state based on state 2. 4. Update state based on state 3. ... or more succinctly.. t=0. Initialize state. t=t+1. Update state based on state t-1. It seems to me that if it can be proven that state t depends only on state t-n, then memory for states before t-n can be reused. If n is known at compile time, which can be true for a lot of signal processing applications, this should be feasible. If states t-n to t are treated as immutable, then it could be considered as pure from an outside perspective, something like the ST monad for instance. So, as for circular buffers: if the program never refers to delayed values more than n steps in the past, then a mutable circular buffer is a perfect acceptable data structure for a functional simulation. It is merely an optimization of a delay that happens to knows how to efficiently reuse unreferenced memory. If the amount of memory needed on each iteration is exactly the same (not growing arbitrarily), then no allocations or GC are needed. Of course this is a subset of possible Haskell programs, so it demands a domain-specific language. I guess this is already what some DSLs do that generate code for embedded signal processing applications. Steve _______________________________________________ haskell-art mailing list [email protected] http://lists.lurk.org/mailman/listinfo/haskell-art
