On Wed, 28 May 2008, Don Stewart wrote:
by an unboxed array with a cursor to the next element to be evaluated and a function that generates the next element. Whenever an element with an index beyond the cursor is requested, sufficiently many new elements are written to the array and the cursor is advanced. This would still allow the nice tricks for recursive Fibonacci sequence definition. This will obviously save memory, but can we also expect that it is noticeably faster than (StrictList a) ?
That sounds a lot like the semi-eager structure, Lazy ByteStrings, which do cache sized chunks of evaluation before suspending. With the cursor in place, it would behave more like the buffer abstraction to lazy bytestrings in Data.Binary?
Can you code fibs = 0 : 1 : zipWith (+) fibs (tail fibs) with hte 'buffer'? I'm afraid you cannot simultaneously read and write from 'buffer', cannot 'drop' and so on, right? What I have in mind is some combination of a 'Data.Stream' for generating the data (playing the role of the unevaluated thunk), a memory chunk for buffering calculated data and a wrapper which provides a view on a sub-array. Ideally 'fibs' would be translated to something like int *p = malloc ...; int *p0 = p; *p = 0; p++; int *p1 = p; *p = 1; p++; int *p2 = p; int i=n; while (i>0) { *p2 = *p0 + *p1; p0++; p1++; p2++; i--; } I'm not sure, whether the compiler can eliminate the last bit of laziness that would remain in a 'cursor array'.